09 Collision Handling
Collision Handling¶
eliminates collisions in hashing
| Collision | Search Complexity | Disadvantage | |
|---|---|---|---|
| Separate Chaining | array with \(N\) buckets pointing to linked lists | \(O(n)\) | memory wastage |
| Linear Probing | \((i + j )\% N\) | \(O(1)\) | clustering |
| Quadratic Probing | \((i + j^2) \% N\) | some elements may not be able to stored | |
| Double Hashing |
Problem with probing is the possibility of full bucket
Linear Probing Search¶
-
Compute \(i = h(k)\)
-
Start at array cell \(a[i]\)
-
Probe consecutive locations until
| return | case |
|---|---|
| present | |
| not present | empty cell |
something more
Double Hashing¶
use a secondary hash function \(d(k)\)
Hashing¶
\[ \begin{aligned} h(k) &= k \% N \\ d(k) &= q - k \% q \\ \end{aligned} \]
where
- \(q\) is prime and \(q < N\)
- \(N\) is the no of elements
Bucket Placement¶
\[ \begin{aligned} \text{index} = \Big( i+ jd(k) \Big) \% N \\ i &= h(k) \\ j &= 0, 1,\dots \end{aligned} \]
Load Factor¶
\[ \lambda = \frac{n}{N} \]
- \(n\) is the no of keys
- \(N\) is the no of buckets
Load Factor should preferably be \(\lambda < 0.75\), or atleast \(\lambda < 1\)