8.2 常见散列函数

散列表

Content

散列技术简介1常见散列函数2

冲突处理技术3

PART TWO

常见散列函数选择“好”的散列函数，尽量减少冲突

什么是好的散列函数

•确定性：同一值总被映射到同一地址

•快速：最好是O(1)

•满射：尽可能充分覆盖整个散列表存储空间

•均分布：为了充分利用散列空间和降低冲突，要使映射到各个位置的概率接近，避免很多元素扎堆聚集的现象。

除留余数法

h(key)=key%M(M为散列表表长)模值取不超过M的素数P会更好例：M=1000,P=997

关键字内部编码散列地址KEYA11052501756 KEYB11052502757 AKEY01110502864 BKEY021********对于素数P, 0

例如M=10的情况，如果关键字恰好是5,10,15,…

这种情况建议模值设为7

除留余数法的不足

1.存在不动点h(0)=0，与均分布相悖

2.相邻的关键字散列到相邻地址上

除留余数法的改进MAD

h(key)=(key◊a+b)%P

P为不超过M的最大素数，a>0，b>0，a%P≠0例：M=1000,P=997,a=15,b=87

关键字内部编码散列地址

KEYA11052501460

KEYB11052502475 AKEY01110502546 BKEY021********b作为偏移量，消除了不动点

a作为间隔量，原本相邻地址变成间隔为a

平方取中法

h(key)=(key)2的中间若干位k

其中：位数k应满足：10k-1＜n≤10k，n为集合中元素个数。例：n=765,103-1<765 103,故k=3

关键字(内部编码）2散列地址

KEYA122157778355001778

KEYB122157800460004800

AKEY001233265775625265

BKEY004454315775625315

1.把关键字值自左到右，分成位数相等的几部分；每部分位数与散列表地址位数相同，最后一部分的位数可以短些

2.把这些部分的数据叠加起来，得到该关键字的散列地址。

例：设关键字key=12320324111220，散列地址取3位，

则key被划分位5段：123 203 241 112 20

123 203 241 112＋20

699移位法

123 302 241 211＋20

897分界法

例：设关键字key=12320324111220，散列地址取3位，则key被划分位5段：123 203 241 112 20

数字分析法位 1 2 3 4 5 6

关键字9 4 2 1 4 89 4 2 3 5 69 4 2 5 7 29 4 2 6 6 49 4 3 3 9 59 4 2 4 7 29 4 2 7 3 19 4 1 2 8 79 4 2 3 4 5观察关键字编码组合规律，取分布均匀的若干位。可以看出第4、5、6位取值分布均匀，故取第4、5、6三位为散列函数值

END NEXT：冲突处理技术