Hashing

Basics

• N: number of elements
• m: size of hash table

Collision Handling

Separate Chaining

• Linked list

Open Addressing

1. To inert a key $k$, compute $h_0(k)$
2. If $T[h_0(k)]$ is empty, insert it here
3. If collision occurs, probe alternative cell in the following order: $h_1(k),h_2(k),\dots$, until an empty cell is found
4. $h_i(k)=(hash(k)+f(i))\mathrm{mod}m$, where the function $f$ determines the collision resolution strategy and $f(0)=0$
5. Different open addressing methods differ in the definition in the function $f()$

Linear probing

$$\begin{array}{rl}& f(i)=i\\ & h_i(k)=(hash(k)+i)\mathrm{mod}m\end{array}$$

• Can always insert unless the table is full
• Worst case for insertion is O(n)
• Insertion can merge 2 cluster, making subsequent insertion slower
• Each insertion must increase size of cluster by 1

Quadratic probing

$$\begin{array}{rl}& f(i)=i^2\\ & h_i(k)=(hash(k)+i^2)\mathrm{mod}m\end{array}$$

• Different home positions will have different probe sequences
• If the table size is prime, then a new key can always be inserted if the table is at least half empty
• To avoid secondary clustering, the probe sequence need to be a function of the original key value, not the home position (double hashing)

Double hashing

$$\begin{array}{rl}& f(i)=i\times has{h}_2(k)\\ & h_i(k)=(hash(h)+i\times has{h}_2(k))\mathrm{mod}m\end{array}$$

e.g. $has{h}_2(k)=R-(k\mathrm{mod}R)$, where $R<m$ and $R$ is prime

• hash2 cannot be zero
• For any key $h$, $has{h}_2(k)$ must be relatively prime to the table size $m$, otherwise we will only be able to examine a fraction of the table entries

Lazy Deletion

• load factor $\alpha =N/m$