# 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.

# Randomized QuickSort and Randomized Select Analysis

## Randomized QuickSort

Randomized QuickSort is an efficient sort algorithm requiring only $\Theta(n\log n)$ expected time on any input.

## Randomized Select

Randomized Select is an efficient algorithm to find $i$th smallest element of Array[low…high] with only linear expected time on any input.