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)