散列表
散列表的查找
散列函数的基本概念
散列函数和散列地址:
在记录的存储位置p和其关键字key之间建立一个确定的对应关系H，使p=H(key)，称这个对应关系H为散列函数，p为散列地址
散列表:
一个有限连续的地址空间，用以存储按散列函数计算得到相应散列地址的数据记录
冲突和同义词:
对不同的关键字可能得到同一散列地址，即\(key_1
= key_2\)，而\(H(key_1) =
H(key_2)\)，这种现象成为冲突。具有相同函数值的关键字对该散列函数来说称作同义词
散列函数构造方法
构造一个"好"的散列函数遵循以下原则
- 函数计算简单，每一个关键字只能有一个散列地址与之对应
- 函数的值域需在表长的范围内，计算出的散列地址的分布应均匀，尽可能减少冲突
常用构造方法:
- 数字分析法: 适用于事先必须明确知道所有的关键字每一位上各种数字的分布情况
- 平方取中法: 适用于不能事先了解关键字的所有情况，或难于直接从关键字中找到取值较分散的几位
- 折叠法: 适用于适合于散列地址的位数较少，而关键字的位数较多，且难于直接从关键字中找到取值较分散的几位
- 除留余数法: 适用范围非常广，是最常用的构造散列函数的方法
如何处理冲突
开放地址法
把记录都存储在散列表数组中，当某一记录关键字key的初始散列地址\(H_0=H(key)\)发生冲突时，以\(H_0\)为基础，采取合适方法计算得到另一个地址\(H_1\)，如果\(H_1\)仍然发生冲突，以\(H_1\)为基础再求下一个地址\(H_2\)，若\(H_2\)仍然冲突，再求得\(H_3\)。依次类推，直至\(H_k\)不发生冲突为止，则\(H_k\)为该记录在表中的散列地址
链地址法
把具有相同散列地址的记录放在同一个单链表中，称为同义词链表。有m个散列地址就有m个单链表，同时用数组HT[0…m−1]存放各个链表的头指针，凡是散列地址为i的记录都以结点方式插入到以HT[i]为头结点的单链表中
| 比较项目 处理方法 | 开放地址法 | 链地址法 | |
|---|---|---|---|
| 空间 | 无指针域，存储效率高 | 附加指针域，存储效率低 | |
| 时间 | 查找 | 有二次聚集现象，查找效率低 | 无二次聚集现象，查找效率高 |
| 插入、删除 | 不易实现 | 易于实现 | |
| 使用情况 | 表的大小固定，适于表长无变化的情况 | 结点动态生成，适于表长经常变化的情况 | |