![](https://csdnimg.cn/release/download_crawler_static/86311954/bg3.jpg)
版权所有 张玉帅 数据结构与算法
存放,即“存储位置 = h(key)”。
散列方法中使用的计算函数称为“散列函数” (也称哈希函数),按这个思想构造的表称
为“散列表”,所以它也是一种存储方法。
在查找某数据对象时,用同样的方法“存储位置 = h(key)”计算出地址,将 key 与该地
址单元中数据对象关键字进行比较,确定查找是否成功。
可能将不同的关键字映射到同一个散列地址上,即 h(key
i
) = h(key
j
)(当 key
i
≠key
j
), 这
种现象称为“冲突(Collision)”, key
i
和 key
j
称为“同义词(synonym)”。
通常关键词的值域(允许取值的范围)远远大于表空间的地址集,所以说,冲突不可能
避免,只能尽可能减少。
11.2 散列函数的构造方法
一个“好”的散列函数一般应考虑下列两个因素:
1. 计算简单,以便提高转换速度;
2. 关键词对应的地址空间分布均匀,以尽量减少冲突。
11.2.1 数字关键词的散列函数构造
1.直接定址法:取关键词的某个线性函数值为散列地址,即 h(key)=a×key+b(a、b 为常
数)。
2.除留余数法:散列函数为:h(key) = key mod p。为了地址空间分布均匀,一般 p 取
素数。
3.数字分析法:分析数字关键字在各位上的变化情况,取比较随机的位作为散列地址。
比如:取 11 位手机号码 key 的后 4 位作为地址:散列函数为:h(key) = atoi(key+7)
4.折叠法:把关键词分割成位数相同的几个部分,然后叠加。
例如 56793542,则做以下处理:(542)+(793)+(056)=1391,取 391 作为关键字。
5.平方取中法:例如 56793542,则计算 56793542×56793542=3225506412905764,那
么就取中间的 641 作为关键字。
11.2.2 字符串关键词的散列函数构造
1.一个简单的散列函数——ASCII 码加和法
对字符型关键词 key 定义散列函数如下:
h(key) = (Σkey[i]) mod TableSize
这种方法也会有比较严重的冲突!
2.简单的改进——前 3 个字符位移法
h(key)=(key[0] + key[1]×27 + key[2]×27
2
)mod TableSize
缺点:仍然冲突:string、 street、strong、structure 等等;空间浪费:3000/26
3
≈ 30%
3.好的散列函数——移位法
设计关键词所有 n 个字符,并且分布得很好。如图
3 所示的公式。