哈希表的魔力

哈希表与字典

普遍存在一种误解，认为“哈希表”和“字典”这两个术语可以互换。这种观念从根本上是不准确的，至少在计算机科学领域是如此。

字典是将键映射到值的数据结构的一般概念。而哈希表是字典的具体实现。

本质上，字典扮演着一个总体“cookie cutter”的角色，塑造了抽象概念。哈希表只是该概念的实际实现。现在我们解决了这个问题，让我们深入研究哈希表的机制及其运作方式。

哈希表基础知识

哈希表是编程领域使用最广泛的数据结构之一。事实上，如果你做过一些基本的编程，你可能已经使用过哈希表。例如，在 Python 中，内置的“字典”数据结构（不要与前面提到的字典的“概念”定义混淆）实际上在底层使用了哈希表。以下是使用这些 Python 字典的一些代码。

python# Create a dictionary of student grades
student_grades = {"John": 85,"Emily": 92,"Michael": 78,"Jessica": 95,"Ryan": 88
}# Updating a value in the Python dictionary
student_grades["Michael"] = 82# Adding a new entry to the Python dictionary
student_grades["Sarah"] = 90# Removing an entry from the Python dictionary
del student_grades["Ryan"]

从高层次上讲，哈希表是一种实现键和值查找系统的数据结构。由于每个值都与一个键相关联，因此我们可以在哈希表上执行数据操作，例如插入或删除。值得注意的是，键和值基本上可以是任何数据类型。虽然通常使用字符串，但只要您有哈希函数，几乎任何东西都可以。

等等，什么是哈希函数？

让我们稍微绕个弯来了解一下哈希函数是什么。为此，我们将探索一种类似的数据结构，该结构也存储了键和值的集合- 直接访问表。

直接访问表

与哈希表类似，直接访问表也使用键值对。每个键唯一地指向元素范围内某个槽的索引，这些元素可能包含数据，也可能不包含数据。

呃，等等——这听起来就像一个数组……？

你说的非常正确！直接访问表只是数组的一个特定实现。事实上，哈希表也是数组的另一种特定实现——准确地说是关联数组。等等，让我猜猜你在想什么……

术语太多了。我正经历一场史诗级的术语灾难！我可怜的大脑正以平均每秒 5cm³ 的速度融化，并威胁要罢工。救救我吧，不要让我遭受这种术语引发的灾难！

好的，好的，我明白了。让我帮你形象化一下我们刚才讨论的所有事物之间的关系。

如果你想要非常分类，教科书上对字典和关联数组的定义可能会有细微的差别。但是，在大多数情况下，你可以认为它们是类似的。
在直接访问表中，键表示与每个slot关联的索引。为了真正理解这一点，让我们想象所有键都存在于一个单一的“key universe”中。

“密钥宇宙”中的每个密钥都唯一地指向数组中的一个槽位。因此，这意味着数组的大小等于“密钥宇宙”中密钥的总数。

对于直接访问表，插入、删除和搜索都是常数时间操作，即 O(1)。换句话说，无论输入大小如何，执行这些操作所需的时间将保持不变。

那么如果直接访问表已经如此神奇了，我们为什么还需要哈希表呢？

让我们来看看其中的一些原因。

1. 内存使用情况

还记得我之前提到过数组中的槽位可能包含数据，也可能不包含数据吗？这意味着槽位不一定需要包含值，而可以为空。

请记住，键指向的是槽的索引，而不是槽的值。这意味着槽不一定需要包含数据。

那么为什么这个属性很重要？

考虑一个“密钥宇宙”非常巨大的场景。为了演示目的，我们假设它包含 100 亿个密钥。由于每个密钥都链接到数组中的一个槽位，因此数组的大小也将是 100 亿。换句话说，必须消耗内存才能容纳 100 亿个槽位。

但是，如果实际只使用了 10 个插槽怎么办？在这种情况下，数组将有太多冗余插槽，以至于超过 99.9% 的插槽都是空的，从而导致内存浪费和效率极低。

2. 内存不足

现在让我们想象一下，我们分配了 10 个内存单元来创建直接访问表。

由于数组的固有特性，每个槽位都会占用一定量的内存。为了演示目的，我们假设每个槽位占用 2 个内存单位。因此，如果“键宇宙”中有 5 个或更多键，我们就已经超出了内存限制：

2 个单位× 5 个槽位 = 10 个单位

这意味着直接访问表对于数据存储来说不是一个可行的选择，因为没有足够的内存来创建具有所有必要槽的数组。换句话说，如果“键域”的大小大于数组的最大大小，则无法使用直接访问表。那么，我们如何解决这个问题呢？

输入哈希表。

哈希表简介（finally……）

有了哈希表，这两个问题都可以通过引入所谓的哈希函数来解决。哈希函数可以看作是表中键和槽之间的中介。哈希函数不会直接使用键作为索引，而是将每个键转换为称为“哈希输出”的唯一标识符，该标识符决定了将存储键值对的特定槽。

注意：在哈希表中，键可以是任何数据类型，只要它们是“可哈希的”。

散列输出用作索引来确定应在数组中的何处存储相应的值。

动态内存使用

与数组具有预定义大小的直接访问表不同，哈希表可以根据存储的键数调整其大小。这种动态分配优化了内存使用率，使哈希表能够处理更大范围的键，而不会浪费不必要的内存。

碰撞

由于“密钥宇宙”现在没有预先定义的限制，因此它有可能包含无限数量的不同密钥。然而，这种开放性引入了多个密钥生成相同“散列输出”的可能性，导致不同的密钥最终被分配给数组中的同一个位置。这就是所谓的碰撞。

冲突通常被认为是不利的，原因有很多，包括性能下降、搜索时间增加以及密钥分布不均匀等。几秒钟后，我们将讨论如何处理这些情况。

良好的哈希函数

选择或设计一个精心设计的哈希函数对于创建高效的哈希表至关重要。我们不会在这里讨论所有细节，但一个好的哈希函数往往具有两个关键特征：

1. 快速计算运行时间

   哈希函数应设计为快速生成给定键的哈希值。通过最小化计算哈希值所需的时间，可以显著提高哈希表中插入、删除和检索操作的效率。这在处理大型数据集或时间敏感的应用程序时尤为重要。

2. 通过最大化随机性来最小化碰撞
   另一个重要特性是能够尽可能为不同的密钥生成不同的哈希值，从而最大限度地减少冲突的发生。好的哈希函数应该对输入密钥的哪怕是微小的变化都很敏感，从而导致计算出的哈希值发生显著变化。
   
   这种特性称为雪崩效应，它确保密钥的微小变化会产生截然不同的哈希输出。通过这样做，多个密钥生成相同哈希输出的可能性大大降低。

处理碰撞的方法

链式

链接是一种广泛采用的哈希表冲突处理方法。它涉及使用链接列表将每个数组槽转换为 值链。

将每个“链环”视为一个不同的键值对，形成一个从数组槽中悬挂的连接链。在这个类比中，链代表链接列表，而单个“链环”则代表键值对。当发生冲突时，新的键值对会简单地附加到该槽的链中，从而有效地解决冲突。

每个“链”代表一个链表，每个“链环”代表链表中的一个节点。

链表中的每个节点都包含一个键值对。要从链式槽中检索值，需要使用哈希函数来计算索引，然后遍历与该索引关联的链表，直到找到所需的键值对。链式方法确保即使多个值存储在同一个索引中，也可以通过遵循链表结构单独访问它们。

开放寻址

开放寻址是处理哈希表中冲突的另一种替代方法。与使用链表的链接不同，开放寻址旨在将所有键值对直接存储在数组本身中。

那么这是如何实现的呢？

简而言之，当两个键被哈希到同一个数组索引时，算法会浏览数组以找到下一个可用或“开放”的插槽来存储键值对。这是通过应用特定的探测序列来完成的，该序列决定了算法检查数组插槽的顺序。

虽然所有形式的开放寻址都避免使用链接列表，但它可能会导致聚类，即数组中的连续位置被占用，这可能会导致更长的探测序列和性能下降。我们马上就会看到如何缓解这种聚类效应。

在此图中，左侧的红色箭头表示已将某个键散列到与现有键值对“cat”相同的槽位。为了使用开放寻址解决此冲突，我们遍历数组，直到找到一个空槽位。

上图是开放寻址类型的示例，称为线性探测。其他值得注意的探测序列包括二次探测和双重哈希。在深入研究后两者之前，让我们先看看线性探测。

1. 线性探测

正如我们已经看到的线性探测，如果在特定槽位发生碰撞，算法会检查数组中的每个连续槽位并继续，直到遇到空槽位或遍历整个数组。

在上面的例子中，向右移动 3 步后找到一个空槽。在下面的例子中，遍历整个数组，从发生碰撞的“WJ931”槽开始，直到回到同一位置，但最终没有找到空槽。

在上面的例子中，我开始使用整数而不是字符串来重新强调哈希表中的键和值可以是任何数据类型，只要它们是可哈希的。

2. 二次探测
与线性探测类似，二次探测是解决开放寻址冲突的另一种方法。当在特定时隙发生冲突时，该算法不会简单地检查连续的时隙。相反，它会遵循二次序列来确定下一个要检查的时隙。

该算法不是像线性探测那样检查连续的槽位，而是遵循二次序列。在这种情况下，该算法在几步之后成功找到一个空槽位，从而解决了冲突。

通过使用这个二次序列，该算法会随着探测的继续探索相距较远的槽。这有助于在整个哈希表中更均匀地分布值，从而减少前面提到的聚类效应。

3. 双重哈希

除了线性和二次探测之外，另一种先进的开放寻址技术是双重散列。双重散列引入了二次散列函数。二次散列函数获取原始散列值并对其执行单独的散列运算。

然后使用这个新的哈希值版本来确定下一次探测的步长。这个步长被添加到当前槽位索引中，算法继续探测直到找到一个空槽位。

观察示例 1 和示例 2 中的冲突如何通过不同的步长解决。这是因为辅助哈希函数为每个冲突计算不同的步长，因此允许它找到空槽而无需进行广泛的聚类。

使用双重散列有助于在散列表中更均匀地分布密钥，从而再次降低聚类的可能性。通过结合不同的散列函数来确定步长，双重散列提供了更加多样化的探测序列。

重新讨论

到目前为止，我们已经探索了各种冲突缓解技术，包括高质量哈希函数、链接和开放寻址。我们将要讨论的最后一个技术是重新哈希。

当哈希表变得太满或冲突次数超过某个阈值时，就会触发重新哈希。此过程涉及创建一个新的、更大的哈希表，并根据新的大小重新计算每个元素的哈希值。

当原始 20 个槽位的哈希表变得太满时，会触发“调整大小和重新哈希”事件。具体来说，当 12 个或更多槽位被填满时，元素将重新哈希到新的 40 个槽位的表中。通过重新哈希，元素分布得更均匀，从而减少冲突次数并提高整体性能。

需要注意的是，重新散列可能是一项资源密集型操作，因为它需要分配一个新的哈希表，重新散列所有元素，并将它们复制到新表中。然而，这是保持哈希表平衡并维持检索和插入操作效率的必要步骤。

哈希的应用

1. 消息摘要

消息摘要是消息内容的固定大小数字表示。这些“摘要”消息基本上是哈希输出，由单向加密哈希函数计算得出。该算法旨在保护传输消息的完整性。

一个例子就是从互联网上下载开源软件时。通常，除了软件之外，你还会找到一个称为签名的配套文件。此签名表示原始文件的哈希值，换句话说，就是消息摘要。它起着至关重要的作用，允许用户独立计算下载文件的哈希值并将其与提供的签名进行比较。此过程可确保下载的文件未被篡改。

2. 加密密码

哈希函数的另一个重要应用是密码加密。您是否曾经想过，为什么当您在网站上忘记密码并尝试恢复时，该网站通常会告诉您设置新密码，而不是简单地提醒您原来的密码？这种方法背后的原因是网站不存储您的实际密码；而是存储其哈希值。

此安全措施可防止未经授权的个人在访问网站数据库时获取您的密码。由于哈希函数通常是单向函数，因此几乎不可能从其哈希值中检索原始密码。因此，使用哈希可为用户密码提供额外的保护。

总结一下……

虽然很多理论上学到的数据结构在现实生活中从未真正投入使用，但哈希表却并非如此。哈希表看似神奇的效率、动态内存分配能力以及对各种数据类型的多功能性，使其成为每个程序员和计算机科学家都应该掌握的工具中的中心。理解哈希表并了解其优点和局限性是掌握算法和数据结构的关键里程碑。

你可能会问：“那么下一步是什么？”

以下是为您准备的一项有趣的家庭挑战：

使用您选择的编程语言来实现您自己的哈希表的任务，而不依赖于任何预制的数据结构库。

愿你的编程之旅继续充满冒险和启迪！

参考文档
https://forreya.medium.com/the-magic-of-hash-tables-f0a8086c820a