哈希表

1. Introduction

哈希表是一种数据结构,用于将键映射到值(也称为表或映射抽象数据类型/ADT)。它使用一个哈希函数将大的或甚至非整数键映射到一个小的整数索引范围(通常是[0..hash_table_size-1])。


两个不同的键碰撞到同一个索引的概率相对较高,每一次可能的碰撞都需要解决以维护数据完整性。


在这个可视化中将会强调几种碰撞解决策略:开放寻址(线性探测,二次探测,和双重哈希)和闭散列(分离链接)。尝试点击 Search(7) 查看在使用分离链接技术的随机创建的哈希表中搜索特定值7的示例动画(允许重复)。

2. 动机

散列是一种算法(通过散列函数),将大型可变长度数据集(称为键,不一定是整数)映射为固定长度的较小整数数据集。
哈希表是一种数据结构,它使用哈希函数有效地将键映射到值(表或地图ADT),以便进行高效的搜索/检索,插入和/或删除。
散列表广泛应用于多种计算机软件中,特别是关联数组,数据库索引,缓存和集合。
在这个电子讲座中,我们将深入讨论表ADT,哈希表的基本概念,讨论哈希函数,然后再讨论哈希表数据结构本身的细节。

2-1. 表ADT

表ADT必须至少支持以下三种操作,并且尽可能高效:

  1. 搜索(v) - 确定v是否存在于ADT中,
  2. 插入(v) - 将v插入ADT,
  3. 删除(v) - 从ADT中删除v。

哈希表是这个表ADT的一个可能的好实现(另一个是这个)。


PS1:对于Table ADT的两个较弱的实现,您可以单击相应的链接:未排序数组排序数组来阅读详细讨论。


PS2:在现场课程中,您可能想要比较Table ADT和List ADT的要求。

2-2. 直接寻址表

当整数键的范围很小时,例如 [0..M-1],我们可以使用大小为M的初始空(Boolean)数组A,并直接实现以下表ADT操作:

  1. 搜索(v):检查A [v]是true(填充)还是false(空),
  2. 插入(v):将A [v]设置为true(填充),
  3. 移除(v):将A [v]设置为false(空白)。

就是这样,我们使用小整数键本身来确定数组A中的地址,因此称为直接寻址。 很明显,所有三种主要的ADT操作都是O(1)

题外话:这个想法在其他地方也有使用,例如在计数排序中。

2-3. DAT的例子

在新加坡(截至2023年4月),公交路线编号从[2..991]。


并非所有[2..991]之间的整数都在当前使用,例如,没有989号公交路线 - Search(989)应返回false。可能会引入新的公交路线x,即Insert(x),或者可能会停止现有的公交路线y,即Remove(y)。


由于可能的公交路线范围,为了记录公交路线号码是否存在的数据,我们可以使用一个大小为1000的布尔数组的DAT(通常,最好在当前最大的公交车号991之上再多给几个缓冲单元格)。

2-4. 带数据的DAT示例

请注意,我们总是可以添加卫星数据,而不仅仅是使用布尔数组来记录键的存在。


例如,我们可以使用关联字符串数组A来将公交路线号映射到其运营商名称,例如,

A[2] = "Go-Ahead Singapore",
A[10] = "SBS Transit",
A[183] = "Tower Transit Singapore",
A[188] = "SMRT Buses", 等等。

讨论:你能想到其他一些现实生活中的DAT例子吗?

2-5. 答案

[This is a hidden slide]

2-6. DAT的局限性

键必须是(或可以轻松映射到)非负整数值。 请注意基本的DAT在前面两张幻灯片的例子的完整版本中存在问题,因为在新加坡实际上有公交路线号有一些变种,例如, 96B,151A,NR10等
键的范围必须很小。 如果我们有(非常)大范围的话,内存使用量会(非常的)大。
键必须密集,即键值中没有太多空白。 否则DAT将包含太多的空的(浪费的)单元。
我们将用哈希来克服这些限制。

3. 散列:想法

使用哈希,我们可以:

  1. 将(一些)非整数(例如字符串)键映射成整数键,
  2. 将大整数映射成较小的整数。

3-1. 电话号码示例

例如,我们有 N = 400个新加坡电话号码(新加坡电话号码有8位数字,所以新加坡最多有10^8 = 1亿个可能的电话号码)。


我们可以使用以下简单的哈希函数 h(v) = v%997,而不是使用DAT并使用一个最大为 M = 1亿的巨大数组。


这样,我们将8位电话号码 6675 23786874 4483 映射到最多3位的 h(6675 2378) = 237h(6874 4483) = 336。因此,我们只需要准备一个大小为 M = 997(997是一个质数)的数组,而不是 M = 1亿的数组。

3-2. 哈希表预览

使用散列,我们现在可以使用整数数组(而不是布尔数组)执行下面的表ADT操作,如下所示:
  1. 搜索(v):检查A [h(v)]!= -1(假设 v≥0,我们对空单元使用-1)
  2. 插入(v):设置A [h(v)] = v(我们把 v 散列到h(v)中,所以我们需要以某种方式记录键 v),
  3. 删除(v):设置A [h(v)] = -1 --- 将进一步阐述。

3-3. 带数据的哈希表

如果我们有映射到卫星数据的键,并且我们也想记录原始键,我们可以使用如下一对(整数,卫星数据类型)数组实现哈希表:

  1. 搜索(v):返回A [h(v)],它是一对v,卫星数据),可能是空的,
  2. 插入(v,卫星数据):设置A [h(v)] =对(v,卫星数据)
  3. 删除(v):设置A [h(v)] =(空对) - 将进一步详细阐述。

但是,现在你应该注意到有些地方是不完整的......

3-4. 冲突

散列函数可能且很可能将不同的键(整数或不是)映射到同一个整数槽中,即多对一映射而不是一对一映射。
例如,早些时候三张幻灯片中的h(6675 2378)= 237,如果我们想插入另一个电话号码6675 4372,我们也会遇到问题,因为h(6675 4372)= 237
这种情况称为碰撞,即两个(或更多)键具有相同的散列值

3-5. 冲突的概率

生日(冯米塞斯)悖论问:'在一个大小为365个座位(单元)的房间(哈希表)中,必须有多少人(键的数量),才能有人同一天生日(碰撞,两个键被哈希到同一个单元)的概率变得>50%(即比不发生更有可能)?

Reveal这个答案对我们中的一些人来说可能令人惊讶。
我们来做一些计算吧。

3-6. 计算

假设Q(n)是房间中n个人不同生日的概率。
Q(n)= 365/365×364/365×363/365×...×(365-n + 1)/ 365,
即第一人的生日可以是365天中的任何一天,第二人的生日可以是除第一人的生日之外的任何365天,等等。
P(n)为房间中 n 个人的相同生日(碰撞)的概率。P(n)= 1-Q(n)
我们计算P(23) = 0.507> 0.5(50%)。
因此,我们只需要在有365人的座位(单元格)的房间(哈希表)中有23人(少量键),发生碰撞事件(该房间中两个不同人的生日 是365天/插槽之一)就会超过50%。

3-7. 两个重要的问题

问题1:我们已经看到了一个简单的散列函数,如电话号码示例中使用的h(v)= v%997,它将大范围的整数键映射到整数键的较小范围内,但非整数键的情况如何? 如何有效地做这样的散列?
问题2:我们已经看到,通过将大范围散列或映射到更小范围,很可能会发生碰撞。 如何处理它们?

4. 哈希函数

如何用这些理想的属性创建一个好的散列函数?
  1. 快速计算,即在O(1)中,
  2. 尽可能使用最小插槽/散列表的大小M,
  3. 尽可能均匀地将键分散到不同的基地址∈[0..M-1],
  4. 尽可能减少碰撞。

4-1. 初步措施

假设我们有一个大小为 M 的散列表,其中键用于标识卫星数据,并且使用特定的散列函数来计算散列值。
使用散列函数从键v计算键v的散列值/散列码以获得范围从0到M-1的整数。 该散列值用作卫星数据的散列表条目的基址/归位索引/地址。

4-2. 不好的哈希函数的例子

使用电话号码示例,如果我们定义h(v) = floor(v/1 000 000)
即,我们选择电话号码的前两位数字。

h(66 75 2378) = 66
h(68 74 4483) = 68

讨论:当你使用这个哈希函数时会发生什么?提示:参见这个

4-3. 答案

[This is a hidden slide]

4-4. 完美的哈希函数

在讨论现实之前,让我们讨论理想的情况:完美的散列函数
完美的散列函数是键和散列值之间的一对一映射,即根本不存在冲突。 如果事先知道所有的键是可能的。 例如,编译器/解释器搜索保留关键字。 但是,这种情况很少见。
当表格大小与提供的关键字数量相同时,实现最小的完美散列函数。 这种情况更为罕见。
如果你有兴趣,你可以探索GNU gperf,这是一个用C++编写的免费可用的完美哈希函数生成器,可以从用户提供的关键字列表中自动构建完美的函数(C++程序)。

4-5. 散列整数 - 最佳实践

人们已经尝试过各种方法,尽可能均匀地将大范围的整数散列到更小范围的整数中。 在这个电子讲座中,我们直接跳到最好的和最受欢迎的版本之一:h(v)= v%M,即将v 映射到大小为M个插槽的哈希表中。 (%)是一个模运算符,给出了除法后的余数。 这显然很快,即O(1)假设v不超过自然整数数据类型限制。
哈希表大小M被设置为不接近2的幂的相当大的素数,大约比将在哈希表中使用的期望的键的数量N大2倍以上。 这样,负载因子α= N / M <0.5 稍后我们将看到具有低负载因子,从而牺牲空闲空间,有助于提高哈希表性能。
讨论:如果我们将M设置为10(十进制)的幂或2(幂的二进制),那该怎么办?

4-6. 答案

[This is a hidden slide]

4-7. 散列串 - 最佳实践

人们也尝试了各种方法将字符串尽可能均匀地散列到一个小范围的整数中。在这个电子讲座中,我们直接跳到最好和最受欢迎的版本,如下所示:

int hash_function(string v) { // 假设 1: v 只使用 ['A'..'Z']
int sum = 0; // 假设 2: v 是一个短字符串
for (auto& c : v) // 对于 v 中的每个字符 c
sum = ((sum*26)%M + (c-'A'+1))%M; // M 是表大小
return sum;
}

交互式 (M = ∞),即,模运算没有效果
v = , hash_string(v) = 0.


讨论:在实际课堂中,讨论上述哈希函数的组成部分,例如,为什么要遍历所有字符?,这会比 O(1) 慢吗?,为什么要乘以26?,如果字符串 v 使用的不仅仅是大写字符怎么办?,等等。

4-8. 答案

[This is a hidden slide]

5. 冲突解决方案

有两个主要的思想:开放寻址闭散列方法。


在开放寻址中,所有哈希键都位于一个数组中。键的哈希码给出了其基地址。通过根据某种规则在表中检查/探测多个备选地址(因此得名开放)来解决冲突。


在闭散列中,哈希表看起来像一个邻接列表(一种图数据结构)。键的哈希码给出了其固定/闭合的基地址。通过在基地址标识的辅助数据结构(通常是任何形式的列表ADT)内追加冲突的键来解决冲突。

5-1. 开放寻址法(OA)

在这个可视化中,我们讨论了三种开放寻址 (OA) 冲突解决技术:线性探测 (LP),二次探测 (QP) 和双重哈希 (DH)。


要在这三种模式之间切换,请点击相应的标题。


设:
M = HT.length = 当前哈希表的大小,
base = (key%HT.length),
step = 当前的探测步骤,
secondary = smaller_prime - key%smaller_prime (为了避免零 —— 很快会详细说明)

我们很快就会看到,这三种模式的探测序列是:
线性探测:i=(base+step*1) % M,
二次探测:i=(base+step*step) % M,和
双重哈希:i=(base+step*secondary) % M。


所有三种 OA 技术都要求负载因子 α = N/M < 1.0 (否则无法进行更多的插入)。如果我们可以将 α 限制在一个小的常数 (如果我们知道我们的哈希表应用中预期的最大 N,以便我们可以相应地设置 M,最好 < 0.5 对于大多数 OA 变体),那么所有使用开放寻址的 Search(v),Insert(v) 和 Remove(v) 操作都将是 O(1) —— 详细信息省略。

5-2. 分离链接法(SC)

分离链接 (SC) 冲突解决技术很简单。我们使用M个辅助数据结构的副本,通常是双向链表。如果两个键ab都有相同的哈希值i,那么它们都将被添加到双向链表i的(前/后)(在这个可视化中,我们在O(1)的帮助下添加到尾部)。就是这样,键将被插入的位置完全取决于哈希函数本身,因此我们也称分离链接为封闭地址冲突解决技术。


如果我们使用分离链接,负载因子α = N/MM个列表的平均长度(不像在开放寻址中,α可以是"稍微超过1.0"),并且它将决定Search(v)的性能,因为我们可能需要平均探索α个元素。由于Remove(v)也需要Search(v),所以它的性能与Search(v)相似。Insert(v)显然是O(1)。


如果我们可以将α限制为一个小常数(如果我们知道我们的哈希表应用中预期的最大N,那么我们可以相应地设置M),那么使用分离链接的所有Search(v),Insert(v)和Remove(v)操作都将是O(1)。

6. 可视化

查看上面的哈希表可视化。


在这个可视化中,我们允许插入重复的键(即,一个集)。由于多集比集合更通用,如果你只想看哈希表如何处理不同的整数键,只需在这个可视化中插入不同的整数即可。


由于屏幕空间有限,我们在你想要可视化哈希表大小M ∈ [46..90] 的OA技术时,从默认(1.0x)比例切换到0.5x比例。对于SC技术,限制稍低,即M ∈ [20..31]。


哈希表像数组一样水平可视化,其中索引0位于第一行的最左边,索引M-1位于最后一行的最右边,但是当我们可视化开放寻址(通常跨多行)与分离链(只有顶行)冲突解决技术时,细节有所不同。

6-1. 开址法版本

在这个可视化中,我们讨论了三种开放寻址冲突解决技术:线性探测 (LP),二次探测 (QP) 和双重哈希 (DH)。


对于所有三种技术,每个哈希表单元格都显示为一个顶点,单元格值 [0..99] 显示为顶点标签(在 0.5x 缩放中,顶点标签显示在较小的黑点上方)。在不失一般性的情况下,我们在这个可视化中不显示任何卫星数据,因为我们只关注键的排列。我们保留值 -1 来表示一个 '空单元格'(可视化为一个空白顶点)和 -2 来表示一个 '已删除单元格'(可视化为一个带有缩写标签 "DEL" 的顶点)。范围从 [0..M-1] 的单元格索引显示为每个顶点下方的红色标签(在 1.0x 缩放中为 15 行索引,或在 0.5x 缩放中为 25 行索引)。

6-2. 分离链接版本

对于分离链接 (SC) 冲突解决技术,第一行包含 M 个 "H" (头) 指针,这些指针指向 M双向链表


然后,每个双向链表 i 包含所有被哈希到 i 的键,顺序是任意的(在0.5x的比例下,顶点标签显示在较小的黑点上方)。从数学上讲,所有可以表示为 i (mod M) 的键 — 包括所有 i 的重复项 — 都被哈希到 DLL i。再次强调,我们在这个可视化中不存储任何卫星数据。

7. 线性探测

在线性探测冲突解决方法中,每当发生冲突时,我们会一次扫描一个索引,以查找下一个空/被删除的插槽(当我们到达最后一个插槽时再重新环绕)。
例如,我们假设我们以表格大小M = HT.length = 7的空的散列表 HT开始,如上所示,使用索引0到 M-1 = 7-1 = 6。请注意,7是素数。 (主)散列函数很简单,h(v)= v%M
此演练将向您展示使用线性探测作为冲突解决技术时Insert(v),Search(v)和Remove(v)操作所采取的步骤。

7-1. 插入([18,14,21])

现在点击 Insert([18,14,21]) —— 一条命令中的三个单独插入。


回顾(在您点击上面的按钮后显示)。


正式地,我们将线性探测索引 i描述为 i = (base+step*1) % M,其中base是键v的(主)哈希值,即h(v)step是从1开始的线性探测步骤。


提示:要快速计算一个(小)整数VM的模,我们只需将V减去最大的M的倍数≤V,例如,18%7 = 18-14 = 4,因为14是 ≤ 18 的7的最大倍数。

7-2. 插入([1,35])

现在点击Insert([1,35])(在上一张幻灯片中插入的前三个值的顶部)。
回顾(在点击上面的按钮后显示)

7-3. 搜索(35)和搜索(8)

现在我们说明使用线性探测作为碰撞解析技术的Search(v)操作。 所采取的步骤与 Insert(v)操作非常相似,即我们从(主)散列键值开始,检查是否已找到v,否则我们一次向前移动一个索引(如果遇到结尾则从开头重新开始)并重新检查。 当我们遇到一个空单元时,我们就停止,这意味着v完全不在哈希表中(因为之前的Insert(v)操作会将v放在那里)。

现在点击Search(35) - 你应该看到探测序列[0,1,2,3(找到键35)]。

现在单击Search(7) - [1,2,3,4,5(空单元格,因此在哈希表中找不到键8)]。

7-4. 删除(v) - 初步措施

现在我们来讨论移除(v)操作。
如果我们直接设置HT [i] = EMPTY单元,其中i是包含v的索引(在必要时进行线性探测之后),您是否意识到我们会导致问题? 为什么?

提示:查看以前的三张幻灯片,了解插入(v)和搜索(v)的行为。

7-5. 答案

[This is a hidden slide]

7-6. 删除(21)

现在让我们看看完整的删除(v)。 如果我们在索引 i 处找到 v(必要时在线性探测之后),我们必须设置 HT [i] = DELETED(在此可视化中缩写为DEL),其中DEL是一个特殊符号(通常你只能在你的应用程序种没有使用过的使用一个特殊符号)指示该单元格可以在将来的搜索(v)需要时绕过,但可以被将来的插入(w)覆盖。 这种策略被称为懒惰删除。
现在点击Remove(21) - [0,1(找到关键21,我们设置H [1] = DEL)]。
然后请继续讨论下一张幻灯片。

7-7. 再次搜索(35)

现在点击Search(35) - [0,1(绕过那个DELETED cell),2,3(找到键35)]。
想象一下,如果我们错误地设置H [1] = EMPTY,会发生什么。

7-8. 插入(28) - 覆盖DEL

现在单击Insert(28) - 您应该看到探测序列[0,1(使用DEL符号找到一个单元格)],因此,实际上可以用新值覆盖,而不会影响将来搜索(v)的正确性。 因此,我们把28放在索引1中。

7-9. 初级聚类,第一部分

尽管我们可以用线性探测来解决冲突,但这并不是最有效的方法。


我们定义一个为一组连续的占用槽。覆盖键的基地址的簇被称为键的主簇


现在注意到线性探测可以创建大的主簇,这将使Search(v)/Insert(v)/Remove(v)操作的运行时间超过宣传的O(1)。


看看上面的一个例子,其中M = 31,我们已经插入了15个键[0..14],使它们占用单元格[0..14] (α = 15/31 < 0.5)。现在看看 Insert(31) (第16个键)有多么"慢"。

7-10. 线性探测顺序

线性探测的探测序列可以正式描述如下:

 h(v) // 基地址
(h(v) + 1*1) % M // 如果有冲突,第1步探测
(h(v) + 2*1) % M // 如果仍然有冲突,第2步探测
(h(v) + 3*1) % M // 如果仍然有冲突,第3步探测
...
(h(v) + k*1) % M // 第k步探测,等等...

在 Insert(v) 过程中,如果有冲突但哈希表中仍有空(或 DEL)槽位,我们可以确保在最多 M 步线性探测后找到它,即在 O(M) 中。当我们找到它时,冲突将被解决,但键 v 的主簇将因此扩展,未来的哈希表操作也会变慢。尝试在与上一张幻灯片相同的哈希表上使用慢速 Search(31),但有许多 DEL 标记(假设 {4, 5, 8, 9, 10, 12, 14} 刚刚被删除)。

7-11. 初级聚类,第二部分

在上一张幻灯片中(主要聚类,第1部分),我们打破了哈希函数应该将键均匀分布在 [0..M-1] 周围的假设。在下一个例子中,我们将展示即使哈希函数将键分布到 [0..M-1] 周围的几个相对较短的主要聚类中,主要聚类的问题仍然可能发生。


在屏幕上,看到 M = 31,插入了15个在 [0..99] 之间的随机整数(有几个随机但短的主要聚类)。如果我们接着插入这4个键 {2, 9, 12, 1},前三个键将“插入”三个空单元格,并意外地合并那些相邻的(但以前是分离的)聚类成为一个(非常)长的主要聚类。因此,下一个插入键1的操作将在这个长的主要聚类的开始处进行,最终需要进行几乎 O(M) 的探测步骤才能找到一个空单元格。尝试 Insert([2,9,12,1])

8. 二次探测(QP)

为了减少主聚类,我们可以将探针序列修改为:

  h(v)//基地址
(h(v)+ 1 * 1)%M //第一个探测步骤,如果发生碰撞
(h(v)+ 2 * 2)%M //第2次探测步骤,如果仍有冲突
(h(v)+ 3 * 3)%M //第三次探测步骤,如果仍有冲突
...
(h(v)+ k * k)%M //第k个探测步骤等...
就是这样,探针按照二次方跳转,根据需要环绕哈希表。
由于这是一种不同的二次探测,所以一个非常常见的错误就是:做H(V),(H(v)的1)%M,(H(v)的+ 1 + 4)%M,(H(V)+ 1 + 4 + 9)%M,...

8-1. 插入(38)

假设我们已经调用 Insert(18)和Insert(10)到大小为M = HT.length = 7的初始空Hash表中。由于18%7 = 4和10%7 = 3,18和3不会相互碰撞, 如上所示分别位于指数4和3中。
现在,我们点击Insert(38)
回顾(点击上面的按钮后显示)。

8-2. 移除(18), 再次搜索(38)

删除(x)和搜索(y)操作的定义类似。 只是这次我们使用二次探测而不是线性探测。
例如,假设我们在上一张幻灯片之后调用了Remove(18),并且标记了HT [4] = DEL。 如果我们调用Search(38),我们将使用与上一张幻灯片相同的二次探测序列,但是会通过标记为DELETED的HT [4]。

8-3. 比线性探测更好?

一目了然,二次探测(Quadratic Probing)能够快速解决我们之前对线性探测的主要聚类问题,但它是完美的碰撞解决技术吗?
尝试Insert([12,17])
你意识到刚刚发生了什么吗?

8-4. 细节

我们可以很容易地插入12,因为h(12)= 12%7 = 5 以前是空的(见上文)。
但是,即使我们仍然有3个空槽,我们仍然存在主要问题:h(17)= 17%7 = 3已被键10占用,(3 + 1 * 1)%7 = 4已被占用 (3 + 2 * 2)%7 = 0已被键38占用,(3 + 3 * 3)%7 = 5已被键12占用,(3 + 4 * 4)%7 = 5 (3 + 5 * 5)%7 = 0再次被键38占据,(3 + 6 * 6)%7 = 4又被键18占据,(3 + 7 * 7)%7 = 3再次被键10占用,如果我们继续二次探测,它将永远循环...
尽管我们仍然有几个(3)空单元格,但我们无法将此新值17插入到哈希表中。

8-5. 定理

如果 α < 0.5 并且 M 是一个质数(> 3),那么我们总是可以使用(这种形式的)二次探测找到一个空的插槽。回忆:α 是负载因子,M 是哈希表的大小(HT.length)。


如果满足上述两个要求,我们可以证明,包括基地址 h(v) 在内的前 M/2 个二次探测索引都是不同且唯一的。


但是超过这个范围就不能保证了。因此,如果我们想使用二次探测,我们需要确保 α < 0.5(在这个可视化中没有强制执行,但我们在 M 步后会中断循环以防止无限循环)。

8-6. 证明

我们将通过矛盾使用证据。 我们首先假设两个二次探测步骤:x和y,x!= y(假设x
h(v) + x*x = h(v) + y*y (mod M)
x*x = y*y (mod M)//从两边敲出h(v)
x*x - y*y = 0 (mod M) //将y * y移动到左边
(x-y)*(x+y) = 0 (mod M)//重新排列公式

现在,(x-y)或(x + y)必须等于零。 我们的假设是x != y,  那么(x-y)不能为0. 由于0≤ x
矛盾!
因此,第一个M / 2二次探测步骤不能产生相同的地址模M(如果我们将M设置为大于3的质数)。
讨论:我们可以使二次探测能够使用其他约50%的表格单元吗?

8-7. 更好的二次探测

[This is a hidden slide]

8-8. 二次聚类

在二次探测中,集群是沿着探测路径形成的,而不是像线性探测那样围绕基地址形成的。这些集群被称为次级集群,与困扰线性探测的主要集群相比,它们“不那么明显”。


次级集群是由于碰撞键使用相同的探测模式而形成的,即,如果两个不同的键有相同的基地址,那么它们的二次探测序列将会是相同的。


为了说明这一点,看看屏幕上M = 31。我们只用10个键填充了这个哈希表(所以负载因子 α = 10/31 ≤ 0.5),哈希表看起来“稀疏足够”(没有明显的大的主要集群)。然而,如果我们接着插入 Insert(62,93),尽管有很多(31-10 = 21)空单元格和62 != 93(最终散列到索引0的不同键),我们最终在这个“不那么明显”的次要聚集中进行了10次探测步骤(注意,{62, 93}都遵循类似的二次探测序列)。


二次探测中的次级集群并不像线性探测中的主要集群那么糟糕,因为一个好的哈希函数理论上应该将键分散到不同的基地址∈ [0..M-1]中。

9. 双倍散列(DH)

为了减少主要和次要群集,我们可以修改探针序列为:

  h(v)//基地址
(h(v)+ 1 * h2(v))%M //第一个探测步骤,如果有碰撞
(h(v)+ 2 * h2(v))%M //第2次探测步骤,如果仍有冲突
(h(v)+ 3 * h2(v))%M //第三次探测步骤,如果仍有冲突
...
(h(v)+ k * h2(v))%M //第k个探测步骤等...
就是这样,探测器根据第二个散列函数h2(v)的值跳转,根据需要环绕散列表。

9-1. 次要散列函数h2(v)

如果h2(v)= 1,则双散列(Double Hashing)的工作方式与线性探测(Linear Probing)完全相同。 所以我们通常希望h2(v)> 1来避免主聚类。
如果h2(v)= 0,那么Double Hashing不起作用的原因很明显,因为任何探测步数乘以0仍然是0,即我们在碰撞期间永远停留在基地址我们需要避免这种情况。
通常(对于整数键),h2(v)= M' - v%M'其中M'是一个小于M的质数。这使得h2(v)∈[1..M'],它足够多样 二次聚类。
二次散列函数的使用使得理论上难以产生主要或次要群集问题。

9-2. 插入([35,42])

点击Insert([35,42])插入35,然后插入42到上面的当前哈希表。
回顾(点击上面的按钮后显示)。

9-3. 移除(17), 再次搜索(35)

删除(x)和搜索(y)操作的定义类似。 只是这次我们使用双散列(Double Hashing)而不是线性探测或二次探测。
例如,假设我们在上一张幻灯片之后调用了Remove(17),并且标记了HT [3] = DEL。 如果我们调用Search(35),我们将使用与前一张幻灯片相同的双哈希序列,但是会通过标记为DELETED的HT [3]。

9-4. 好的OA冲突解决方案

总的来说,一个好的开放寻址冲突解决技术需要:

  1. 如果存在空槽,总是能找到,
  2. 最小化聚类(任何类型),
  3. 当2个不同的键发生冲突时,给出不同的探测序列,
  4. 快速,O(1)。

现在,让我们看看之前困扰二次探测的同一测试用例。现在再试一次 Insert(62,93)。虽然 h(62) = h(93) = 0 并且它们与已经占据索引 0 的 31 发生冲突,但它们的探测步骤不同:h2(62) = 29-62%29 = 25 不同于 h2(93) = 29-93%29 = 23。


讨论:双重哈希似乎符合要求。但是...双重哈希策略是否足够灵活,可以作为哈希表的默认库实现?让我们看看...

10. 分离链接(SC)

尝试 Insert([9,16,23,30,37,44]),看看如果我们使用分离链接作为冲突解决技术,Insert(v) 操作是如何工作的。在这样的随机插入中,性能是好的,每次插入明显是 O(1)。


然而,如果我们尝试 Insert([68,90]),注意到所有的整数 {68,90} 都是 2 (模 11),所以它们都将被追加到双向链表 2 的后面。我们将在该列表中有一个长链。请注意,由于屏幕限制,我们将每个双向链表的长度限制在最多 6。

10-1. Search(35) 和 Remove(35)

尝试 Search(35),可以看到 Search(v) 的运行时间可以达到 O(1+α)。


尝试 Remove(35),可以看到 Remove(v) 的运行时间也可以达到 O(1+α)。


如果 α 很大,分离链接的性能实际上并不是 O(1)。然而,如果我们大致知道我们的应用程序可能会使用的最大键值数量 N,那么我们可以相应地设置表大小 M,使得 α = N/M 是一个非常低的正(浮点)数,从而使分离链接的性能预期为 O(1)。

10-2. 闭散列法 vs 分离链接法?

讨论:在所有这些解释之后,两种冲突解决方法的哪一种更好?

10-3. (当前)答案

[This is a hidden slide]

11. 额外的

您已经完成了这个哈希表数据结构的基本工作,我们鼓励您在探索模式中进一步探索。

但是,我们仍然会为您提供一些本节中概述的更有趣的哈希表的挑战。

11-1. (重新散列)Rehash

当负载因子α变高时,哈希表的性能会降低。 对于(标准)二次探测冲突解决方法,当哈希表的α> 0.5时,插入可能失败。
如果发生这种情况,我们可以重新散列(rehash)。 我们用一个新的散列函数构建另一个大约两倍的散列表。 我们遍历原始哈希表中的所有键,重新计算新的哈希值,然后将键(及其卫星数据)重新插入新的更大的哈希表中,最后删除较早的较小哈希表。
一个经验法则是,如果使用开放寻址,并且当α>小的常数(根据需要接近1.0),如果使用单独链接,当α≥0.5时重新散列。
如果我们知道可能的最大键数,我们可以始终将α作为一个低的数字。

11-2. 哈希表的实现

但是,如果您需要使用C ++, Python或Java实现哈希表,并且您的键(Keys)是整数或字符串,则可以使用内置的C ++ STL,Python标准库或Java API。 他们已经有了整数或字符串默认散列函数的内置实现。
请参阅C ++ STL unordered_mapunordered_set, Python dict, set, 或 Java HashMapHashSet
请注意,multimap / multiset实现也存在(允许重复键)。
对于OCaml, 我们可以用 Hashtbl

这里是我们分离链接法的实现: HashTableDemo.cpp | py | java.

11-3. 数据结构组合?

[This is a hidden slide]

11-4. 对于表ADT的 备选数据结构

如果(整数或字符串)键只需要映射到卫星数据,则散列表是实现Table ADT的非常好的数据结构,对于Search(v),Insert(v)和Remove( v)如果哈希表设置正确,则执行时间复杂度为O(1)。
但是,如果我们需要更多地使用 键,我们可能需要使用另一种数据结构。

11-5. 在线小测试

关于这个数据结构的一些更有趣的问题,请在哈希表培训模块上练习(不需要登录,但是只需短暂且中等难度设置)。
但是,对于注册用户,您应该登录,然后转到主要培训页面以正式清除此模块,这些成果将记录在您的用户帐户中。

11-6. 在线评判练习

尝试解决一些基本的编程问题,就很可能需要使用哈希表(特别是如果输入大小很大的时候):

  1. Kattis - cd(输入已经被排序,因此存在替代的非哈希表解决方案; 如果未对输入进行排序,则在哈希表的帮助下最好解决此组交集问题),
  2. Kattis - oddmanout(我们可以将较大的邀请代码映射到较小范围的整数;这是整数散列(大范围)的一种做法),
  3. Kattis - whatdoesthefoxsay(我们把不是狐狸的声音放入无序集合;这是散列字符串的做法)。