# CS 577 Study Group (Hashing)
## Important Definition/Notation
* A hash function maps element from a universal set $\mathcal{U}$ to a range of integers $0, 1, 2, \cdots, m-1$, often denoted as $[m]$.
* A universal hash function family is a collection of hash functions. When we pick unifromly random from the set of hash functions, we have for any two distinct elements $x, y$, the probability that $h(x) = h(y)$ is at most $\frac{1}{m}$.
**Remark** The randomness comes from the choice of hash function, not from the elements in the universe. Besides, $m$ here denotes the size of the range of **output**, not the size of the universe.
* A 2-universe hash family satisfies $Pr(h(x) = i, h(y) = j) = \frac{1}{m^2}$.
* Perfect Hashing
Process of generating a hash function with 0 collision among a given set of input. Notice that different from the hash function used in practice, here all the input data is given before we even initialize the hash function. This is not really a problem as the analysis is almost the same if we first use a default hash function, and switch to other function (re-hashing) if a collision is detected.

## Hashing Exercise (All thanks to Jerry Jongho Park!)
### Universal v.s 2-Universal (Pairwise-Independence)

### 2-1 mapping hash function