Summary of Hash Tables: Efficient Dictionary Data Structures

## Introduction Hash functions are rules that map keys from a large universe into a smaller set of numbers. Good hash functions spread keys evenly so operations that rely on hashing behave predictably. This material focuses on designing and reasoning about randomized hash-function families, particularly universal and $k$-universal families, and shows how these families help with authentication. > **Definition:** A family $\mathcal{H}$ of hash functions mapping a universe $U$ to $\{0,1,\dots,m-1\}$ is called *$k$-universal* if for every fixed sequence of $k$ distinct keys $\langle x^{(1)},x^{(2)},\dots,x^{(k)}\rangle$ and a uniformly random $h$ chosen from $\mathcal{H}$, the vector $\langle h(x^{(1)}),\dots,h(x^{(k)})\rangle$ is uniformly distributed among the $m^{k}$ possible vectors. ## 1. From 2-universal to universal ### Key idea - A family is *universal* if for every pair of distinct keys $k,l\in U$, the collision probability $\Pr_{h\in\mathcal{H}}[h(k)=h(l)] \le 1/m$. ### Reasoning (short) - If $\mathcal{H}$ is 2-universal, then for any distinct keys $k,l$ the pair $\langle h(k),h(l)\rangle$ is equally likely to be any of the $m^{2}$ ordered pairs. Therefore exactly $m$ of these pairs have equal components (those of the form $\langle y,y\rangle$ for $y\in\{0,\dots,m-1\}$). Hence $$\Pr[h(k)=h(l)] = \frac{m}{m^{2}} = \frac{1}{m},$$ so 2-universal implies universal. > **Definition (universal):** A family $\mathcal{H}$ is universal if for every distinct $k,l\in U$, $\Pr_{h\in\mathcal{H}}[h(k)=h(l)] \le 1/m$. ## 2. A linear-family example over $\mathbb{Z}_{p}$ (not 2-universal) ### Construction - Let $p$ be prime and let keys be $n$-tuples from $\mathbb{Z}_{p}$: $x=\langle x_{0},\dots,x_{n-1}\rangle$. For a fixed $a=\langle a_{0},\dots,a_{n-1}\rangle\in\mathbb{Z}_{p}^{n}$ define $$h_{a}(x)=\left(\sum_{j=0}^{n-1} a_{j} x_{j}\right)\bmod p.$$ - Let $\mathcal{H}=\{h_{a}: a\in\mathbb{Z}_{p}^{n}\}$. ### Why $\mathcal{H}$ is universal - Fix distinct keys $x\neq y$. Consider the difference vector $d=x-y$, which is nonzero in at least one coordinate. The equation $h_{a}(x)=h_{a}(y)$ over $\mathbb{Z}_{p}$ is equivalent to $\sum_{j} a_{j} d_{j} \equiv 0 \pmod p$, a nontrivial linear equation in the $a_{j}$. For uniformly random $a$, the probability this equation holds is exactly $1/p$. Since $p>m$ in typical setups and the final hash may be reduced modulo $m$, the collision probability can be bounded by $1/m$ with appropriate choices, so this class can be arranged to be universal in the standard construction (see later comments in universal hashing literature). ### Why $\mathcal{H}$ is not 2-universal - Find a nonzero key $z$ such that for every $a$ we have $h_{a}(z)=0$ (mod $p$) or some constant; e.g., if all keys are scalar multiples of a fixed vector in a degenerate construction, different $a$ choices may produce the same pair outputs for two chosen keys. More concretely, if one chooses the same linear form for all $a$ without an additive random shift, then pairs of distinct keys might map in a dependent way so that $\langle h_{a}(x),h_{a}(y)\rangle$ is not uniform over $\mathbb{Z}_{p}^{2}$. > Example: For $n=1$ with $h_{a}(x)=a x\bmod p$ and keys $x=0$ and any $y$, we have $h_{a}(0)=0$ for all $a$, so the pair distribution is not uniform and the family fails 2-universality. ## 3. Making the family 2-universal: add an independent offset ### Modified construction - For $a\in\mathbb{Z}_{p}^{n}$ and $b\in\mathbb{Z}_{p}$ define $$h'_{a,b}(x)=\left(\sum_{j=0}^{n-1} a_{j} x_{j} + b\right)\bmod p.$$ - Let $\mathcal{H}'=\{h'_{a,b}\}$. ### Why this is 2-universal - Fix distinct keys $x\neq y$ so the difference vector $d=x-y$ has some coordinate $d_{i}\neq 0$. For uniformly random $(a,b)$, consider the pair $\langle h'_{a,b}(x),h'_{a,b}(y)\rangle$. For any fixed target values $s,t\in\mathbb{Z}_{p}$, the system $$\sum_{j} a_{j} x_{j} + b \equiv s \pmod p$$$$\sum_{j} a_{j} y_{j} + b \equiv t \pmod p$$ is equivalent to $$\sum_{j} a_{j}