1.除留余数法
h(key)=key mod M (M为散列表长度)一般取不超过M的素数P会更好。
例:M=1000,P=997
关键字 内部编码 散列地址
KEYA 11052501 756
KEYB 11052502 757
AKEY 01110502 864
BKEY 02110502 873
2.平方取中法
h(key)=(key)2的中间若干位k
其中:位数k应满足:10k-1<n≤10k ,n为集合中元素个数。
例:n=765, k取3。
103-1<765<=103 , 故k=3, 即取k=3。
关键字 (内部编码)2 散列地址
KEYA 122157778355001 778
KEYB 122157800460004 800
AKEY 001233265775625 265
BKEY 004454315775625 315
3.折叠法
把关键字值自左到右,分成位数相等的几部分,每一部分
位数与散列表地址的位数相同,只有最后一部分的位数可
以短些。把这些部分的数据叠加起来,得到该关键字的散
列地址。
(1)移位法:把各部分最后一位对齐相加
(2)分界法:沿各部分的分界来回折叠,然后对齐相加
4.数字分析法
取分布均匀的若干位。
例如,一组关键字如下:
位 1 2 3 4 5 6
关键字 9 4 2 1 4 8
9 4 2 3 5 6
9 4 2 5 7 2
9 4 2 6 6 4
9 4 3 3 9 5
9 4 2 4 7 2
9 4 2 7 3 1
9 4 1 2 8 7
9 4 2 3 4 5
通过分析,可以看出第4、5、6位分布均匀,故取第4、5、6位这三位为散列函数的值。
以上几个就是常用的散列函数,但是散列函数只能减少冲突,并不能解决,后面的文章给大家介绍怎么解决冲突。