¡EDouble hashing
         h(k) , h(k) + u , h(k) + 2u , .......    u = g(k) = h2(k)
 
 
Key A S E A R C H I N G E X A M P L E
Hash  1 1 0 5 1 18 3 8 9 14 7 5 5 1 13 16 12 5
Hash 2 16 15 12 16 16 14 9 8 3 10 12 10 16 4 1 5 12
 
 
 
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
A
S A
S A E
S A E A
S A E A R
S A C E A R
S A C E H A R
S A C E H I A R
S A C E H I N A R
S A C E G H I N A R
S A C E G H I E N A R
S A C E G H I E N X A R
S A C E G H I E A N X A R
S A C E G H I E A M N X A R
S A C E G H I E A M N X P A R
S A C E G H I E A L M N X P A R
S A C E E G H I E A L M N X P A R
ÂŦâ²Ê±×Åé¦rªí¥Ü²Ä¤@¦¸¥X²{©Î¬O¥X²{ Collision
 
 
 
Performance Unsuccessful successful
Separate chaing 1 + (£\/ 2) (£\+ 1) / 2
Linear probing (1/2) + (1/ 2(1 - £\)^2) (1/2) + (1/2(1 - £\))
Double Hashing 1 / ( 1 - £\) - ln(1 - £\) / £\
£\ = N / M ( load factor)