【数据结构】散列查找

1. 散列表的定义

散列表（Hash Table），又称哈希表。是一种数据结构，通过“散列函数（哈希函数）”：Addr=H(key)，使数据元素的关键字与其存储地址直接相关。

若不同的关键字通过散列函数映射到同一个值，则称它们为“同义词”。

通过散列函数确定的位置已经存放了其他元素，则称这种情况为“冲突”。

2. 处理冲突的方法—拉链法

拉链法（又称连接法、链地址法）处理“冲突”：把所有“同义词”存储在一个链表中。

示例：

有一堆数据元素，关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79}，散列函数H(key)=key%13。

说明：首先将每个数和13取余，得到在数组中存放的位置。如果冲突，则将“同义词”存储在该位置的链表中。

3. 散列查找

1. 查找方法

方法步骤：通过散列函数计算目标元素存储地址：Addr=H(key)。27%13=1，那么就在存储位置为1的位置查找，总共查找3次即可找到。27的查找长度=3。

2. 查找长度

查找长度：在查找运算中，需要对比关键字的次数称为查找长度。

比如：查找21，落到8的位置，没有元素，查找长度为0。查找66，落到1的位置，没有查找到，但是4个数据都查了一遍，查找长度为4。

3. 查找效率分析

4. 常见散列函数

设计目标：让不同关键字的冲突尽可能少。

1. 除留余数法

除留余数法——H(key)=key%p

其中，散列表表长为m，取一个不大于m但是最接近或等于m的质数p。

例如：散列表表长为15，散列函数H(key)=key%13。因为13是离15最近的质数。

用质数取模，分布更均匀，冲突更少。参见《数论》。

2. 直接定址法

直接定址法——H(key)=key或H(key)=a*key+b。

其中，a和b是常数。这种方法计算最简单，且不会产生冲突。它适合关键字的分布基本连续的情况，若关键字分布不连续，空位较多，则会造成存储空间的浪费。

例如：存储同一个班级的学生信息，班内学生学号为（1120112176-1120112205）。H(key)=key-1120112176。

3. 数字分析法

数字分析法——选取数码分布较为均匀的若干位作为散列地址。

设关键字是r进制数（如十进制数），而r个数码在各位上出现的频率不一定相同，可能在某些为上分布均匀一些，每种数码出现的机会均等；而在某些位上分布不均匀，只有某几种数码经常出现，此时可选取数码分布较为均匀的若干位作为散列地址。这种方法适合于已知的关键字集合，若更换了关键字，则需要重新构造新的散列函数。

例如：以“手机号码”作为关键字设计散列函数，以手机号后四位作为散列地址，因为后4位出现更均匀。

4. 平法取中法

平方取中法——取关键字的平方值的中间几位作为散列地址。

具体取多少位要视实际情况而定。这种方法得到的散列地址与关键字的每位都有关系，因此使得散列地址分布比较均匀，适用于关键字的每位取值都不够均匀或均小于散列地址所需的位数。

例如：要存储整个学校的学生信息，以“身份证号”作为关键字设计散列函数。

散列查找是典型的“用空间换时间”的算法，只要散列函数设计的合理，则散列表越长，冲突的概率越低。

5. 开放定址法

开放定址法——是指可存放新表项的空闲地址既向它的同义词表向开放，又向它的非同义词表项开放。其数学递推公式为

1. 线性探测法：di=0,1,2,3,...,m-1；即发生冲突时，每次往后探测相邻的下一个单元是否为空。

示例：

有一堆数据元素，关键字分别为{19,14,23,1,68,20,84,27,55,11,10,79}，散列函数H(key)=key%13。

说明：数据10对13取模得到10，本应该存在10的位置，但是由于已经保存了23，经过两次冲突存到12的位置。

线性探测法的查找：

说明：27对13取模算的1，从1的位置开始查找，经过4次冲突查找到4的位置，所以查找路径为4。

说明：21对13取模算的8，从8的位置开始查找，经过5次冲突没有查找到，第6次查找到了空节点，查找失败，所以查找路径为6。

线性探测法的删除：

采用“开放定址法”时，删除结点不能简单地将被删除结点的空间值为空，否则将截断在它之后填入散列表的同义词结点的查找路径，可以做一个“删除标记”，进行逻辑删除。

说明：79之前的数据被删除了，而79对13取模为1，那么从1的位置开始查找，查找路径为9。

线性探测法的查找效率分析：

说明：算出每个数据查找成功的查找路径，除以数据数据元素数量，得到查找成功ASL。

初次探测的地址H0只有可能在[0,12]，得出查找失败ASL。

线性探测法很容易造成同义词、非同义词的“聚集（堆积）现象”，严重影响查找效率。

产生原因——冲突后在探测一定是放在某个连续的位置。

2. 平方探测法。

对于线性探测法的冲突，解决方法就是平方探测法。

注意负数的模运算，(-3)%27=24，而不是3。

平方探测法：比起线性探测法，更不易产生“聚集（堆积）”的问题。

3. 伪随机序列法 伪随机序列法。di是一个伪随机序列，如d=0,5,24,11,...

6. 再散列法（在哈希法）

除了原始的散列函数H(key)之外，多准备几个散列函数，当散列函数冲突时，用下一个散列函数计算一个新地址，直到不冲突为止。

5. 小结