# Universal and Perfect Hashing

Though hash table is one of the most efficient data structures, it has some weaknesses.

For any hash function $\mathbf{h}$, a set of keys exist that can cause the average access time of a hash table to skyrocket. I.e. all keys from $\{k\in\mathcal{U} : \mathbf{h}(k) = i\}$ for some slot $i$.

#### Approach:

Choose the hash function at random, independently of the keys.