
  Hash Function
           
h(key)  ¡÷
{ 0, 1, 2 ...... , M - 1}
     *similar to random number
generator
     *h(abc)  ¡÷ 
1 + 2 + 3 mod M = 6
 Collision : different keys hash to same
address .
                  
exp : x ¡Ú y , h(x) =  h(y) .
 
    *Separate chaining
  
 
    *Open addressing
           
k  ¡÷ h1(k)
, h2(k) ....... , hM(k)
        1) Linear probing
:  hi+1(k) = hi(k)
+ 1 mod M
        2) Double
Hashing :  hi+1(k) = hi(k)
+ u mod M , u = g(k)
 
            
*u ¡Ú 0
            
*( u , M ) ¡× 1
            
*u ¡Ú h(k)
            
*u ¡× M - 2 - k mod (M - 2)  
*T ¡× Const
( average)
           
N       (worst)