Hashing Collision Resolution - Double Hashing Formula & Example

<<Previous - Quadratic Probing

Next - Graph>>

Double Hashing

Double Hashing is a hashing collision resolution technique where we use 2 hash functions.

Double Hashing - Hash Function 1

where

• F(i) = i * hash₂(X)
• X is the Key or the Number for which the hashing is done
• i is the i^th 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 hash₂(X), 2 * hash₂(X) and so on.

Double Hashing - Hash Function 2

We use second hash function as

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

  Next - Graph >>

  
  
  

  ---