Compression Function

Compression function $h_2$: $\text{integers}\to [0,N-1]$ We need to ensure the probability of two different keys getting hashed to the same bucket is $\frac{1}{N}$. We can use:

• Division: $h_2(y)=y\mathrm{mod}N$ where $N$ is usually chosen to be a prime
• Multiply, Add and Divide: $h_2(y)=[(ay)+b)\mathrm{mod}p]\mathrm{mod}N$ Where $N$ is the size of the bucket array, $p$ is a prime number greater than $N$, and $a$ / $b$ are integers chosen at random from the interval $[0,p-1]$ with $a>0$.