首页 > 代码库 > hash function 3种方法 1不好 2一般 3好

hash function 3种方法 1不好 2一般 3好

1. h(k) =  k mod m    

its is really bad in the practical. if m = even and k is all even....

( m is size of hash table,  

modulo

[‘m?djul?u

)

 

2. multiplication method. 好一点

a multiplice the k and sum mod 2^w  w is the bit length integer.  two power of two.

 

3. Universal hashing.

h(k) = [(a*k + b) mod p] mod m         p is a prime number.  p>m   a,b random from 0-p-1

 h(k1)=h(k2)    probability <= 1/m

hash function 3种方法 1不好 2一般 3好