Hashing Collision Resolution - Double Hashing Formula & Example
<<Previous - Quadratic Probing
Double Hashing
Double Hashing is a hashing collision resolution technique where we use 2 hash functions.
Double Hashing - Hash Function 1
hi = ( Hash(X) + F(i) ) % Table Size
where
- F(i) = i * hash2(X)
- X is the Key or the Number for which the hashing is done
- i is the ith time that hashing is done for the same value. Hashing is repeated only when collision occurs
- Table size is the size of the table in which hashing is done
This F(i) will generate the sequence such as hash2(X), 2 * hash2(X) and so on.
Double Hashing - Hash Function 2
We use second hash function as
hash2(X) = R - (X mod R)
A Closed Hash Table using Double Hashing
where
- R is the prime number which is slightly smaller than the Table Size.
- X is the Key or the Number for which the hashing is done
Double Hashing Example - Closed Hash Table
Let us consider the same example in which we choose R = 7.

Key | Hash Function h(X) | Index | Collision | Alt Index |
---|---|---|---|---|
79 | h0(79) = ( Hash(79) + F(0)) % 10 = ((79 % 10) + 0) % 10 = 9 | 9 | ||
28 | h0(28) = ( Hash(28) + F(0)) % 10 = ((28 % 10) + 0) % 10 = 8 | 8 | ||
39 | h0(39) = ( Hash(39) + F(0)) % 10 = ((39 % 10) + 0) % 10 = 9 | 9 | first collision occurs | |
h1(39) = ( Hash(39) + F(1)) % 10 = ((39 % 10) + 1(7-(39 % 7))) % 10 = (9 + 3) % 10 =12 % 10 = 2 | 2 | 2 | ||
68 | h0(68) = ( Hash(68) + F(0)) % 10 = ((68 % 10) + 0) % 10 = 8 | 8 | collision occurs | |
h1(68) = ( Hash(68) + F(1)) % 10 = ((68 % 10) + 1(7-(68 % 7))) % 10 = (8 + 2) % 10 =10 % 10 =0 | 0 | 0 | ||
89 | h0(89) = ( Hash(89) + F(0)) % 10 = ((89 % 10) + 0) % 10 = 9 | 9 | collision occurs | |
h1(89) = ( Hash(89) + F(1)) % 10 = ((89 % 10) + 1(7-(89 % 7))) % 10 = (9 + 2) % 10 =10 % 10 = 0 | 0 | Again collision occurs | ||
h2(89) = ( Hash(89) + F(2)) % 10 = ((89 % 10) + 2(7-(89 % 7))) % 10 = (9 + 4) % 10=13 % 10 =3 | 3 | 3 |
<<Previous - Quadratic Probing