Hashing
 
*Scramble Keys

*Compute address in Hash table
 
 
 

  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)