8.3 哈希查找

一、基本概念

哈希函数：一个把查找表中的关键字映射成该关键字对应的地址的函数，记为：

地址可以是数组下标、索引或内存地址。

哈希表：根据关键字直接进行访问的数据结构。

哈希表建立了关键字和存储地址之间的一种直接映射关系。

理想情况下对哈希表进行查找的时间复杂度是，即与表中元素的个数无关。

二、哈希函数的构造方法

构造哈希函数时应注意：
（1）哈希函数的定义域必须包含全部需要存储的关键字，而值域的范围则依赖于哈希表的大小或地址范围；
（2）哈希函数计算出来的地址应能等概率、均匀的分布在整个地址空间中，减少冲突的发生；
（3）哈希函数应尽量简单，能够在较短时间内计算出任一关键字对应的哈希地址.

1.直接定址法

即取关键码的某个线性函数值为散列地址，这类函数是一一对应函数，不会产生冲突。

此法仅适合于：地址集合的大小与关键字集合的大小相等的情况。

2. 数字分析法

假设关键字集合中的每个关键字都是由 s 位数字组成，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。

此法仅适合于：已知关键字集合，能预先估计出全体关键字的每一位上各种数字出现的频度。

3. 平方取中法

取关键字的平方值的中间几位作为哈希地址。

此方法适合于：关键字中的每一位都有某些数字重复出现频度很高的现象。

4. 除留余数法

假设哈希表表长为m，取一个不大于m但最接近m的质数p，构造哈希函数：

该方法最简单也最常用。

三、处理冲突

考虑发生冲突时，应为产生冲突的关键字寻找下一个空哈希地址并填入。

1.开放定址法

可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放，递推公式为：

m表示哈希表的表长，为增量序列。

（1）线性探测法

取值：取

特点：冲突发生时，顺序查看表中下一个地址（到表尾时回到表首），直到找到空地址或遍历全表

缺点：易造成大量元素在相邻地址“二次聚集”，降低了查找效率

（2）平方探测法

取值：，

特点：有效避免堆积问题

缺点：有部分地址探测不到

（3）双哈希法

当通过第一个哈希函数得到的地址冲突时，使用第二个哈希地址计算该关键字的地址增量

（4）伪随机序列法

取值：为伪随机数序列

2. 拉链法

也叫链地址法，这种方法的基本思想是将所有散列地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在散列表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况 。

特点：不易产生冲突的“聚集”；易于删除记录。

四、性能分析

查找过程和建表过程一致。