[Data Structure] Hash Table - 3 | Double Hashing

Double Hashing is an open-addressing collision resolution technique that uses 2 different hash functions to compute bucket indices. 

Using hash functions h₁ and h₂, a key's index in the table is computed with the formula 

(h₁(key) + 𝑖 * h₂(key)) mod (tablesize)

 

Inserting a key uses the formula, starting with 𝑖 = 0, repeatedly search hash table buckets until an empty bucket is found.

Each time an empty bucket is not found, 𝑖 is incremented by 1. 

Iterating through sequential 𝑖 values to obtain the desired table index is called the probing sequence.

 

This is an example where h₁ = key % 10 and h₂ = 11 - key % 11. 

You can understand after slowly following the step of the probing sequence. 

 

---

Insertion, Search, and Removal 

 

Using double hasing, a hash table search algorithm probes each bucket using the probing sequence defined by the two hash functions as discussed above. 

The search continues until either (1) the matching item is found (returning the item), (2) an empty-since-start bucket is found (returning null), or (3) all buckets are probed without a match (returning null) 

Insertion and removal also operates similarly, probing each bucket using the probing sequence, either inserts in the first empty bucket found in the sequence, or deletes if the item is found following the seqeunce. 

 

Let's check one example for search probing sequence, where the hash functions are given as:

h₁ = key % 10 and h₂ = 7 - key % 7

 

From valsTable hash table, after removing 66 via HashRemove(valsTable, 66),
HashSearch(valsTable, 66) probes [     ] buckets

 

Let's follow the probing sequence, starting from 𝑖 = 0. 

(key % 10) = (66 % 10) = 6, (7 - key % 7) = (7 - 66 % 7) = 4

→ (h₁(key) + 𝑖 * h₂(key)) mod (tablesize) = (6 + 4𝑖) % 10

→ 𝑖 = 0: bucket = (6 + 4 * 0) % 10 = 6 ⇒ Empty-after-removal

→ 𝑖 = 1: bucket = (6 + 4 * 1) % 10 = 0 ⇒ Occupied by 60

→ 𝑖 = 2: bucket = (6 + 4 * 2) % 10 = 4 ⇒ Occupied by 104

→ 𝑖 = 3: bucket = (6 + 4 * 3) % 10 = 8 ⇒ Empty-after-removal

→ 𝑖 = 4: bucket = (6 + 4 * 4) % 10 = 2 ⇒ EMPTY-SINCE-START

So we can finally insert it into bucket index = 2. 😅