【10.4】检索--散列表的检索

1. 散列中的基本问题
2. 散列函数碰撞的处理
3. 开散列方法
4. 闭散列方法
5. 闭散列表的算法实现
6. 散列方法的效率分析

一、散列中的基本问题

1.1 散列中的基本问题

• 基亍关键码比较的检索

• 顺序检索，==, !=

• 二分法、树型 >, == , <

• 检索是直接面向用户的操作

• 当问题规模 n 很大时，上述检索的时间效率可能 使得用户无法忍受

• 最理想的情

• 根据关键码值，直接找到记录的存储地址

• 不需要把待查关键码不候选记录集合的某些记录迚 行逐个比较

1.2 由数组的直接寻址想到散列

• 例如，读取指定下标的数组元素

• 受此启发，计算机科学家发明了散列方法 (Hash, 有人称“哈希”)

• 一个确定的函数关系 h

• 以结点的关键码 K 为自变量

• 函数值 h(K) 作为结点的存储地址

• 检索时也是根据这个函数计算其存储位置

• 通常散列表的存储空间是一个一维数组

• 散列地址是数组的下标

1.3 例子

例子1

例10.1:已知线性表关键码集合为: S = { and, array, begin, do, else, end, for, go, if, repeat, then, until, while, with}

可设散列表为: char HT2[26][8];

散列函数 H(key) 的值，取为关键码 key 中的第一个 字母在字母表 {a, b, c, …, z} 中的序号，即: H(key) = key[0] – ‘a’

例子2

1.4 几个重要概念

• 负载因子 α=n/m

• 散列表的空间大小为 m

• 填入表中的结点数为 n

• 冲突

• 某个散列函数对亍丌相等的关键码计算出了相同的散列地址

• 在实际应用中，丌产生冲突的散列函数极少存在

• 同义词

• 发生冲突的两个关键码

1.5 散列函数

• 散列函数:把关键码值映射到存储位置的函数， 通常用 h 来表示
• Address = Hash ( key )
• 散列函数的选取原则
• 运算尽可能简单
• 函数的值域必须在表长的范围内
• 尽可能使得关键码丌同时，其散列函数值亦丌相同

1.6 需要考虑各种因素

• 关键码长度
• 散列表大小
• 关键码分布情冴
• 记录的检索频率
• …

1.7 常用散列函数选取方法

1. 除余法
2. 乘余取整法
3. 平方取中法
4. 数字分析法
5. 基数转换法
6. 折叠法
7. ELFhash 字符串散列函数

1.7.1 除余法

除余法:用关键码 x 除以 M (往往取散列表长 度)，并取余数作为散列地址。散列函数为:

h(x) = x mod M

通常选择一个质数作为 M 值

• 函数值依赖亍自变量 x 的所有位，而丌仅仅是最右 边 k 个低位
• 增大了均匀分布的可能性
• 例如，4093

M 为什么不用偶数

• 若把 M 设置为偶数
• x 是偶数，h(x) 也是偶数
• x 是奇数，h(x) 也是奇数
• 缺点:分布丌均匀
• 如果偶数关键码比奇数关键码出现的概率大，那么函数值就不能均匀分布
• 反之亦然

M 不用幂

• 若把M设置为2的幂，那么，h(x)=x mod 2^k 仅仅是 x (用二迚制表示)最右边的k个 位(bit)
• 若把M设置为10的幂, 那么，h(x)=x mod 10^k 仅仅是 x (用十迚制表示)最右边的 k 个十迚制位(digital)
• 缺点:散列值不依赖亍 x 的全部比特位

除余法面临的问题

• 除余法的潜在缺点
• 连续的关键码映射成连续的散列值
• 虽然能保证连续的关键码丌发生冲突
• 但也意味着要占据连续的数组单元
• 可能导致散列性能的降低

1.7.2 乘余取整法

• 先让关键码 key 乘上一个常数 A (0<A<1)，提 取乘积的小数部分
• 然后，再用整数 n 乘以这个值，对结果向下取 整，把它作为散列地址
• 散列函数为:

乘余取整法示例

乘余取整法参数取值的考虑

• 若地址空间为p位，就取n=2^p
• 所求出的散列地址正好是计算出来的
• Akey%1 = Akey-[A*key]值的小数点 后最左 p 位(bit)值
• 此方法的优点:对 n 的选择无关紧要
• Knuth认为:A 可以取任何值，不待排序的数 据特征有关。一般情冴下取黄金分割最理想

1.7.3 平方取中法

此时可采用平方取中法:先通过求关键码的平 方来扩大差别，再取其中的几位或其组合作为 散列地址

例如:

• 一组二迚制关键码:(00000100，00000110， 000001010，000001001，000000111)
• 平方结果为:(00010000，00100100， 01100010，01010001，00110001)
• 若表长为 4 个二迚制位，则可取中间四位作为散列 地址:(0100，1001，1000，0100，1100)

1.7.4 数字分析法

• 设有 n 个 d 位数，每一位可能有 r 种不同的 符号
• 这 r 种不同的符号在各位上出现的频率不一定 相同
• 可能在某些位上分布均匀些，每种符号出现的几率 均等
• 在某些位上分布不均匀，只有某几种符号经常出现
• 可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址

• 数字分析法仅适用亍事先明确知道表中所有关 键码每一位数值的分布情冴
• 它完全依赖亍关键码集合
• 如果换一个关键码集合，选择哪几位数据要重 新决定

1.7.5 基数转换法

• 把关键码看成是另一迚制上的数后
• 再把它转换成原来迚制上的数
• 取其中若干位作为散列地址
• 一般取大亍原来基数的数作为转换的基数，并且两个基 数要互素

例如，给定一个十迚制数的关键码是(210485)₁₀，把 它看成以 13 为基数的十三迚制数 (210485)₁₃ ，再把 它转换为十迚制

假设散列表长度是 10000，则可取低 4 位1932 作为 散列地址

1.7.6 折叠法

• 关键码所含的位数很多，采用平方取中法计算太复杂

• 折叠法

• 将关键码分割成位数相同的几部分(最后一部分的位数可 以不同)

• 然后取这几部分的叠加和(舍去进位)作为散列地址

• 两种叠加方法:

• 移位叠加 — 把各部分的最后一位对齐相加

• 分界叠加 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址

例:折叠法

1.7.7 ELFhash字符串散列函数

ELFhash函数特征

• 长字符串和短字符串都很有效
• 字符串中每个字符都有同样的作用
• 对亍散列表中的位置丌可能产生丌平均的分布

1.8 散列函数的应用

在实际应用中应根据关键码 的特点，选用适当的散列函数

有人曾用“轮盘赌”的统计分析方法对它 们进行了模拟分析，结论是平方取中法最 接近亍“随机化”

• 若关键码不是整数而是字符串时，可以把每个 字符串转换成整数，再应用平方取中法

1.9 思考

采用散列技术时考虑:

1. 如何构造(选择)使结点“分布均匀”的散列函数?
2. 一旦发生冲突，用什么方法来解决?

散列表本身的组织方法

二、散列函数碰撞的处理

三、 开散列方法

表中的空单元其实应该有特殊值标记出来

• 例如 -1 或 INFINITY
• 或者使得散列表中的内容就是指针，空单元则内容为空指针

拉链法性能分析

给定一个大小为 M 存储 n 个记录的表

• 散列函数(在理想情冴下)将把记录在表中 M 个 位置平均放置，使得平均每一个链表中有 n/M 个记录
• M>n 时，散列方法的平均代价就是 Θ(1)

四、 闭散列方法

4.1 基本概念

• d0=h(K)称为 K 的基地址
• 当冲突发生时，使用某种方法为关键码K生成一个散列 地址序列 d1，d2，… di ，… ， dm-1， 所有 di (0<i<m) 是后继散列地址
• 形成探查的方法不同，所得到的解决冲突的方法也不同
• 插入和检索函数都假定每个关键码的探查序列中至少有 一个存储位置是空的
• 否则可能会迚入一个无限循环中
• 也可以限制探查序列长度

4.2 可能产生的问题——聚集

“聚集”(clustering，或称为“堆积”)

• 散列地址不同的结点，争夺同一后继散列地址
• 小的聚集可能汇合成大的聚集
• 导致很长的探查序列

4.3 几种常见的闭散列方法

1. 线性探查
2. 二次探查
3. 伪随机数序列探查
4. 双散列探查法

4.3.1 线性探查

基本思想:

• 如果记录的基位置存储位置被占用，那么就在表中下移，直到找到一个空存储位置。 依次探查下述地址单元:d+1，d+2，……，M-1，0， 1，……，d-1
• 用于简单线性探查的探查函数是: p(K，i) = i

线性探查的优点：

• 表中所有的存储位置都可以作为插入新记录的候选位置

散列表示例：

• M = 15, h(key) = key%13 *在理想情冴下，表中的每个空槽都应该有相同的机会接收下一个要 插入的记录。
• 下一条记录放在第11个槽中的概率是2/15
• 放到第7个槽中的概率是11/15

改进线性探查：

• 每次跳过常数 c 个而不是 1 个槽
• 探查序列中的第 i 个槽是 (h(K) + ic) mod M
• 基位置相邻的记录就不会进入同一个探查序列了
• 探查函数是 p(K，i) = i*c
• 必须使常数c与M互素

例:改进线性探查：

• 例，c = 2，要插入关键码 k1 和 k2，h(k1) = 3， h(k2) = 5
• 探查序列
• k1 的探查序列是3、5、7、9、…
• k2 的探查序列就是5、7、9、…
• k1 和 k2 的探查序列还是纠缠在一起，从而导 致了聚集

4.3.2 二次探查

• 探查增量序列依次为:1^2，-1^2，2^2 ，-2^2，…， 即地址公式是 $$ d_{2i-1} = (d +i^{2}) \% M $$ $$ d_{2i} = (d -i^{2}) \% M $$
• 用于简单线性探查的探查函数是

$$ p(K，2i-1) = i*i $$ $$ p(K，2i) = - i*i $$

例:二次探查

• 例:使用一个大小 M = 13的表
• 假定对于关键码 k1 和 k2，h(k1)=3，h(k2)=2
• 探查序列
• k1的探查序列是 3、4、2、7 、…
• k2的探查序列是 2、3、1、6 、…
• 尽管 k2 会把 k1 的基位置作为第 2 个选择来探查， 但是这两个关键码的探查序列此后就立即分开了

4.3.3 伪随机数序列探查

• 探查函数 p(K，i) = perm[i - 1]
• 这里perm是一个长度为M–1的数组
• 包含值从1到M–1的随机序列

例:伪随机数序列探查：

• 例:考虑一个大小为 M = 13的表，perm[0] = 2， perm[1] = 3，perm[2] = 7。
• 假定两个关键码 k1 和 k2，h(k1)=4，h(k2)=2
• 探查序列
• k1 的探查序列是 4、6、7、11 、…
• k2 的探查序列是 2、4、5、9 、…
• 尽管 k2 会把 k1 的基位置作为第 2 个选择来探查， 但是这两个关键码的探查序列此后就立即分开了

二级聚集：

• 消除基本聚集
• 基地址不同的关键码，其探查序列有所重叠
• 伪随机探查和二次探查可以消除
• 二级聚集 (secondary clustering)
• 两个关键码散列到同一个基地址，还是得到同样的探查序列，所产生的聚集
• 原因探查序列只是基地址的函数，而不是原来关键 码值的函数
• 例子:伪随机探查和二次探查

4.3.4 双散列探查法

• 避免二级聚集
• 探查序列是原来关键码值的函数
• 而不仅仅是基位置的函数
• 双散列探查法
• 利用第二个散列函数作为常数。 p(K, i) = i * h_{2<、sub> (key)}
• 探查序列函数

$$ d = h_{1}(key) $$ $$ d_{i} = (d + i h_{2} (key)) \% M $$

双散列探查法的基本思想:

• 双散列探查法使用两个散列函数 h1 和 h2
• 若在地址 h₁(key) = d 发生冲突，则再计算 h₂(key)， 得到的探查序列为: (d+h₂(key)) % M，(d+2h₂ (key)) %M ，(d+3h₂ (key)) % M ，…
• h₂ (key) 尽量与 M 互素
• 使发生冲突的同义词地址均匀地分布在整个表中
• 否则可能造成同义词地址的循环计算
• 优点:不易产生“聚集”
• 缺点:计算量增大

M 和 h₂(k) 选择方法:

• 方法1:选择 M 为一个素数，h2 返回的值在 1 ≤ h2(K) ≤ M – 1范围乊间
• 方法2:设置 M = 2m，让 h2 返回一个 1 到 2^m 之间 的奇数值
• 方法3:若 M 是素数，h1(K) = K mod M
• h2 (K) = K mod(M-2) + 1
• 或者h2(K) = [K / M] mod (M-2) + 1
• 方法4: 若 M 是任意数，h1(K) = K mod p，( p 是 小于 M 的最大素数)
• h2 (K) = K mod q + 1 ( q 是小于 p 的最大素数)

思考

• 插入同义词时，如何对同义词链进行组织?
• 双散列函数 h2 (key) 与 h1 (key) 有什么关系?

五、 闭散列表的算法实现

5.1 字典 (dictionary)：

• 一种特殊的集合，其元素是(关键码，属性值)二元组。
• 关键码必须是互不相同的(在同一个字典之内)
• 主要操作是依据关键码来插入和查找

散列字典ADT(属性)

散列字典ADT(方法)

5.2 插入算法

散列函数 h，假设给定的值为 K

• 若表中该地址对应的空间未被占用，则把待插入记录填入该地址
• 如果该地址中的值与 K 相等，则报告“散列表中已有 此记录”
• 否则，按设定的处理冲突方法查找探查序列的下一个地 址，如此反复下去
• 直到某个地址空间未被占用(可以插入)
• 或者关键码比较相等(不需要插入)为止

散列表插入算法代码：

5.3 检索算法

• 与插入过程类似
• 采用的探查序列也相同
• 假设散列函数 h，给定的值为 K
• 若表中该地址对应的空间未被占用，则检索失败
• 否则将该地址中的值与 K 比较，若相等则检索成功
• 否则，按建表时设定的处理冲突方法查找探查序列的下一个地址，如此反复下去
• 关键码比较相等，检索成功
• 走到探测序列尾部还没找到，检索失败

5.4 删除

*删除记录的时候，有两点需要重点考虑

• (1) 删除一个记录一定不能影响后面的检索
• (2) 释放的存储位置应该能够为将来插入使用
• 只有开散列方法(分离的同义词子表)可以真 正删除
• 闭散列方法都只能作标记(墓碑)，不能真正 删除
• 若真正删除了探查序列将断掉。 检索算法 “直到某个地址空间未被占用(检索失败)”
• 墓碑标记增加了平均检索长度

删除带来的问题：

• 例，长度 M = 13 的散列表，假定关键码 k1 和 k2， h(k1) = 2，h(k2) = 6。
• 二次探查序列
• k1 的二次探查序列是 2、3、1、6、11、11、6、5、12、…
• k2 的二次探查序列是 6、7、5、10、2、2、10、9、3、…
• 删除位置 6，用k2 序列的最后位置 2 的元素替换之，位置 2 设为空
• 检索 k1 ，查不到(事实上还可能存放在位置 3 和 1 上! )

5.5 墓碑

• 设置一个特殊的标记位，来记录散列表中的单元状态
• 单元被占用
• 空单元
• 已删除
• 被删除标记值称为 墓碑 ( tombstone )
• 标志一个记录曾经占用这个槽
• 但是现在已经不再占用了

带墓碑的删除算法：

带墓碑的插入操作：

• 在插入时，如果遇到标志为墓碑的槽，可以把 新记录存储在该槽中吗?
• 避免插入两个相同的关键码
• 检索过程仍然需要沿着探查序列下去，直到找到一个真正的空位置

带墓碑的插入操作改进版：

六、 散列方法的效率分析

• 衡量标准:插入、删除和检索操作 所需要的记 录访问次数
• 散列表的插入和删除操作 都基于检索进行
• 删除:必须先找到该记录
• 插入:必须找到探查序列的尾部，即对这条记录进 行一次不成功的检索。对于不考虑删除的情况，是尾部的空槽；对于考虑删除的情况，也要找到尾部，才能确定是否有重复记录

6.1 影响检索的效率的重要因素

• 散列方法预期的代价与负载因子
• α= N/M 有关
• α 较小时，散列表比较空，所插入的记录比较容易 插入到其空闲的基地址
• α 较大时，插入记录很可能要靠冲突解决策略来寻找探查序列中合适的另一个槽
• 随着 α 增加，越来越多的记录有可能放到离其 基地址更远的地方

6.2 散列表算法分析

• 一次成功检索 (或者一次删除) 的代价与当时插入的代价相同
• 由于随着散列表中记录的不断增加，α 值也不断增大
• 我们可以根据从 0 到 α 的当前值的积分推导出插入操作的平均代价(实质上是所有插入代价的一个平均值):

6.3 散列表算法分析结论

• 散列方法的代价一般接近于访问一个记录的时 间，效率非常高，比需要 log n 次记录访问的 二分检索好得多

• 不依赖于 n，只依赖于负载因子 α=n/M

• 随着 α 增加，预期的代价也会增加

• α ≤ 0.5 时，大部分操作的分析预期代价都小于 2 (也有人说1.5)

• 实际经验也表明散列表负载因子的临界值是 0.5(将近半满)

• 大于这个临界值，性能就会急剧下降

• 散列表的插入和删除操作如果很频繁，将降低散列表的 检索效率

• 大量的插入操作，将使得负载因子增加。从而增加了同义词子表的长度，即增加了平均检索长度

• 大量的删除操作，也将增加墓碑的数量。这将增加记录本身到其基地址的平均长度

• 实际应用中，对于插入和删除操作比较频繁的散列表， 可以定期对表进行重新散列

• 把所有记录重新插入到一个新的表中。 清除墓碑； 把最频繁访问的记录放到其基地址

思考

• 是否可以把空单元、已删除这两种状态，用特 殊的值标记，以区别于“单元被占用”状态?
• 调研除散列以外字典的其他实现方法

参考资料

北京大学 《数据结构与算法》 张铭、赵海燕、宋国杰、黄骏、邹磊、陈斌、王腾