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

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

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

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

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

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

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

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

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

当整数键的范围很小时，例如 [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)。

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

在新加坡（截至2023年4月），公交路线编号从[2..991]。

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

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

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

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

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

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

使用哈希，我们可以：

1. 将（一些）非整数（例如字符串）键映射成整数键，
   
2. 将大整数映射成较小的整数。
   

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

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

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

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

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

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

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

假设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％。

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

1. 快速计算，即在O（1）中，
   
2. 尽可能使用最小插槽/散列表的大小M，
   
3. 尽可能均匀地将键分散到不同的基地址∈[0..M-1]，
   
4. 尽可能减少碰撞。
   

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

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

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

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

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

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 使用的不仅仅是大写字符怎么办？，等等。

There are two major ideas: Closed Addressing versus Open Addressing method.

In Closed Addressing, the Hash Table looks like an Adjacency List (a graph data structure). The hash code of a key gives its fixed/closed base address. Collision is resolved by appending the collided keys inside an auxiliary data structure (usually any form of List ADT) identified by the base address.

In Open Addressing, all hashed keys are located in a single array. The hash code of a key gives its base address. Collision is resolved by checking/probing multiple alternative addresses (hence the name open) in the table based on a certain rule.

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

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

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

在这个可视化中，我们讨论了三种开放寻址 (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) —— 详细信息省略。

View the visualization of Hash Table above.

In this visualization, we allow the insertion of duplicate keys (i.e., a multiset). Since a multiset is more general than a set, simply just insert distinct integers in this visualization if you want to see how Hash Table works on distict integer keys only.

Due to limited screen space, we switch from default (1.0x) scale to 0.5x scale whenever you want to visualize Hash Table size M ∈ [46..90] for OA techniques. The limit is a bit lower, i.e., M ∈ [20..31] for SC technique.

The Hash Table is visualized horizontally like an array where index 0 is placed at the leftmost of the first row and index M-1 is placed at the rightmost of the last row but the details are different when we are visualizing Separate Chaining (only the top row) versus Open Addressing (usually spans multiple rows) collision resolution techniques.

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

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

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

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

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

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

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

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

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

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

回顾（在您点击上面的按钮后显示）。

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

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

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

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

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

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

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

 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} 刚刚被删除）。

在上一张幻灯片中（主要聚类，第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])。

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

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

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

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

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

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

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

In summary, a good Open Addressing collision resolution technique needs to:

1. Always find an empty slot if it exists,
2. Minimize clustering (of any kind),
3. Give different probe sequences when 2 different keys collide,
4. Fast, O(1).

Now, let's see the same test case that plagues Quadratic Probing earlier. Now try Insert(62,93) again. Although h(62) = h(93) = 0 and their collide with 31 that already occupy index 0, their probing steps are not the same: h2(62) = 29-62%29 = 25 is not the same as h2(93) = 29-93%29 = 23.

Discussion: Double Hashing seems to fit the bill. But... Is Double Hashing strategy flexible enough to be used as the default library implementation of a Hash Table? Or in a more general sense, which of the two collision resolution technique (Separate Chaining versus Open Addressing: Double Hashing) is the better one?

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

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

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

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

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

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

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

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