哈希表是如何工作的？

这里有一个通俗易懂的解释。

假设您想用书籍填满图书馆，而不仅仅是将它们塞进那里，而是希望在需要时能够轻松地再次找到它们。

因此，您决定如果想要阅读一本书的人知道书名和要引导的确切标题，那么这就是它应该采取的一切。有了书名，在图书管理员的帮助下，该人应该能够轻松快速地找到这本书。

那么，你怎么能这样做呢？好吧，显然您可以保留某种列表，列出每本书的放置位置，但是您会遇到与搜索图书馆相同的问题，您需要搜索列表。当然，列表会更小更容易搜索，但您仍然不想从库（或列表）的一端到另一端按顺序搜索。

你想要的东西，加上书名，可以立刻给你正确的位置，所以你所要做的就是走到正确的书架上，拿起书。

但怎么可能呢？好吧，当你填满图书馆时，有一点深谋远虑，当你填满图书馆时，需要做很多工作。

与其只是开始从一端到另一端填满库，不如设计一个聪明的小方法。你取这本书的标题，通过一个小型计算机程序运行它，它会在那个架子上输出一个书架号和一个槽号。这是你放置书的地方。

这个程序的美妙之处在于，后来当有人回来看书时，你再次通过程序输入书名，并取回与你最初给出的相同的书架号和槽号，这就是书的位置。

正如其他人已经提到的那样，该程序称为哈希算法或哈希计算，通常通过将输入的数据（在这种情况下为书名）并从中计算出一个数字来工作。

为简单起见，假设它只是将每个字母和符号转换为一个数字并将它们加起来。实际上，它比这要复杂得多，但让我们暂时搁置它。

这种算法的美妙之处在于，如果你一次又一次地向它输入相同的输入，它每次都会输出相同的数字。

好的，这就是哈希表的工作原理。

技术内容如下。

首先，数字的大小。通常，这种散列算法的输出在一个很大的数字范围内，通常比您在表中的空间大得多。例如，假设我们在图书馆里正好有 100 万本书的空间。哈希计算的输出可能在 0 到 10 亿之间，这要高得多。

那么我们该怎么办？我们使用一种叫做模数计算的东西，它基本上是说，如果你数到你想要的数字（即十亿个数字）但又想保持在一个小得多的范围内，每次你达到那个较小范围的限制时，你就会回到0，但你必须跟踪你在大序列中走了多远。

假设哈希算法的输出在 0 到 20 的范围内，并且您从特定标题中获得值 17。如果图书馆的大小只有 7 本书，你数 1、2、3、4、5、6，当你数到 7 时，你从 0 开始。因为我们需要数 17 次，所以我们有 1， 2, 3, 4, 5, 6, 0, 1, 2, 3, 4, 5, 6, 0, 1, 2, 3，最后的数字是3。

当然模数计算不是这样完成的，它是用除法和余数完成的。 17 除以 7 的余数是 3（7 在 14 处乘以 2 到 17，17 和 14 之间的差是 3）。

因此，您将书放在 3 号插槽中。

这导致了下一个问题。碰撞。由于该算法无法将书籍隔开，以便它们准确地填满图书馆（或者如果你愿意的话，也可以使用哈希表），它总是会最终计算出一个以前使用过的数字。在图书馆的意义上，当你到达书架和你想放书的槽位时，那里已经有一本书了。

存在各种碰撞处理方法，包括将数据运行到另一个计算中以获得表中的另一个位置 (double hashing)，或者只是找到一个接近给定位置的空间（即紧邻上一本书，假设插槽可用，也称为 linear probing）。这意味着当您稍后尝试查找这本书时，您需要进行一些挖掘工作，但这仍然比简单地从图书馆的一端开始要好。

最后，在某些时候，您可能希望将比图书馆允许的更多的书放入图书馆。换句话说，你需要建立一个更大的库。由于图书馆中的确切位置是使用图书馆的确切和当前大小计算的，因此如果您调整图书馆的大小，您可能最终不得不为所有书籍找到新位置，因为计算完成以找到它们的位置已经改变。

我希望这个解释比桶和函数更脚踏实地:)

---

用法和行话：

哈希表用于快速存储和检索数据（或记录）。使用散列键将记录存储在存储桶中 散列键是通过将散列算法应用于记录中包含的选定值（键值）来计算的。这个选择的值必须是所有记录的公共值。每个存储桶可以有多个按特定顺序组织的记录。

现实世界的例子：

Hash & Co. 成立于 1803 年，缺乏任何计算机技术，共有 300 个文件柜来保存其大约 30,000 名客户的详细信息（记录）。每个文件夹都清楚地标有其客户编号，从 0 到 29,999 的唯一编号。

当时的备案文员不得不为工作人员快速获取和存储客户记录。工作人员决定使用散列方法来存储和检索他们的记录会更有效。

为了归档客户记录，归档文员将使用写在文件夹上的唯一客户编号。使用这个客户编号，他们将哈希键调制 300 以识别它所在的文件柜。当他们打开文件柜时，他们会发现它包含许多按客户编号排序的文件夹。在确定了正确的位置后，他们就会简单地把它塞进去。

为了检索客户记录，归档文员将在纸条上获得客户编号。使用这个唯一的客户编号（哈希键），他们会将其调整 300，以确定哪个文件柜有客户文件夹。当他们打开文件柜时，他们会发现里面有许多按客户编号排序的文件夹。通过搜索记录，他们会很快找到客户文件夹并检索它。

在我们的实际示例中，我们的存储桶是文件柜，我们的记录是文件夹。

要记住的重要一点是，计算机（及其算法）处理数字比处理字符串更好。因此，使用索引访问大型数组比顺序访问要快得多。

正如西蒙所提到的，我认为非常重要的是散列部分是转换一个大空间（任意长度，通常是字符串等）并将其映射到一个小空间（已知大小，通常是数字）以进行索引。记住这一点很重要！

所以在上面的例子中，大约 30,000 个可能的客户端被映射到一个更小的空间。

这样做的主要思想是将整个数据集划分为多个部分，以加快通常耗时的实际搜索。在我们上面的示例中，300 个文件柜中的每一个都将（从统计上）包含大约 100 条记录。搜索 100 条记录（无论顺序如何）比处理 30,000 条记录要快得多。

您可能已经注意到有些人实际上已经这样做了。但是，在大多数情况下，他们不会设计散列方法来生成散列密钥，而是简单地使用姓氏的第一个字母。因此，如果您有 26 个文件柜，每个文件柜都包含一个从 A 到 Z 的字母，那么理论上您只是对数据进行了分段并增强了归档和检索过程。

希望这可以帮助，

杰奇！

---

事实证明这是一个相当深的理论领域，但基本轮廓很简单。

从本质上讲，散列函数只是一个从一个空间（比如任意长度的字符串）获取事物并将它们映射到对索引有用的空间（比如无符号整数）的函数。

如果您只有一小部分要散列的东西，您可能只需将这些东西解释为整数就可以了，您就完成了（例如 4 字节字符串）

但是，通常情况下，您的空间要大得多。如果您允许作为键的事物空间大于您用于索引的事物空间（您的 uint32 或其他），那么您不可能为每个事物设置唯一值。当两个或更多事物哈希到相同的结果时，您必须以适当的方式处理冗余（这通常称为冲突，您如何处理它或不处理它取决于您是什么使用哈希）。

这意味着您希望它不太可能具有相同的结果，并且您可能还真的希望散列函数更快。

平衡这两个属性（以及其他一些属性）让许多人忙得不可开交！

在实践中，您通常应该能够找到一个已知适用于您的应用程序的函数并使用它。

现在让它作为一个哈希表工作：想象一下你不关心内存使用情况。然后，您可以创建一个数组，只要您的索引集（例如，所有 uint32）。当你向表中添加一些东西时，你对它的键进行散列并查看该索引处的数组。如果那里什么都没有，你就把你的价值放在那里。如果那里已经有东西了，你把这个新条目添加到那个地址的东西列表中，连同足够的信息（你的原始密钥，或者一些聪明的东西）来找到哪个条目实际上属于哪个密钥。

所以当你走很长的路时，你的哈希表（数组）中的每个条目要么是空的，要么包含一个条目，或者一个条目列表。检索很简单，例如对数组进行索引，然后返回值，或者遍历值列表并返回正确的值。

当然在实践中你通常不能这样做，它浪费了太多的内存。因此，您基于稀疏数组执行所有操作（其中唯一的条目是您实际使用的条目，其他所有内容都隐含为空）。

有很多计划和技巧可以使这项工作更好，但这是基础。

---

很多答案，但没有一个是非常直观的，并且哈希表在可视化时可以轻松“点击”。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，经过几次插入后，它可能会在内存中排列如下，其中 () 括起来的数字是文本/名称的哈希值。

bucket#  bucket content / linked list

[0]      --> "sue"(780) --> null
[1]      null
[2]      --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3]      --> "mary"(73) --> null
[4]      null
[5]      --> "masayuki"(75) --> "sarwar"(105) --> null
[6]      --> "margaret"(2626) --> null
[7]      null
[8]      --> "bob"(308) --> null
[9]      null

几点：

每个数组条目（索引 [0]、[1]...）都称为存储桶，并开始一个 - 可能为空 - 链表的值（又名元素，在本例中为人名）

每个值（例如带有哈希 42 的“fred”）都从存储桶 [hash % number_of_buckets] 链接，例如 42 % 10 == [2]； % 是模运算符 - 除以桶数时的余数

多个数据值可能会在同一个存储桶上发生冲突并链接起来，这通常是因为它们的哈希值在模运算后发生冲突（例如 42 % 10 == [2] 和 9282 % 10 == [2]），但偶尔会因为哈希值是相同的（例如“fred”和“jane”都显示为上面的哈希 42）大多数哈希表处理冲突 - 性能略有降低但没有功能混淆 - 通过比较一个值的完整值（此处为文本）在散列存储桶的链表中寻找或插入已经存在的每个值

大多数哈希表通过将正在查找或插入的值的完整值（此处为文本）与已在哈希存储桶的链表中的每个值进行比较来处理冲突 - 性能略有降低但没有功能混淆

链表长度与负载因子有关，而不是值的数量

如果表大小增加，如上实现的哈希表倾向于调整自身大小（即创建更大的存储桶数组，从中创建新/更新的链表，删除旧数组）以保持值与存储桶的比率（也称为负载因子）在 0.5 到 1.0 范围内的某个位置。

Hans 在下面的评论中给出了其他负载因子的实际公式，但对于指示性值：使用负载因子 1 和加密强度哈希函数，1/e (~36.8%) 的桶往往是空的，另外 1/e (~36.8%) 有一种元素，1/(2e) 或~18.4% 两种元素，1/(3!e) 约 6.1% 三种元素，1/(4!e) 或~1.5% 四种元素，1/ (5!e) ~.3% 有五个等.. - 无论表中有多少元素（即是否有 100 个元素和 100 个桶，或 1 亿个），非空桶的平均链长度为 ~1.58元素和 1 亿个桶），这就是为什么我们说查找/插入/擦除是 O(1) 常数时间操作。

哈希表如何将键与值关联起来

当我们这样做时，我们将哈希表用作 associative container aka map，它存储的值可以被视为由 key（名称）和一个或多个仍称为其他字段的字段组成- 令人困惑 - value（在我的示例中，只是年龄）。用作映射的哈希表实现称为哈希映射。

这与此答案前面的示例形成对比，在该示例中，我们存储了诸如“sue”之类的离散值，您可以将其视为自己的键：这种用法称为哈希集。

还有其他实现哈希表的方法

并非所有哈希表都使用链表（称为 separate chaining），但大多数通用哈希表都使用链表，因为主要的替代方案 closed hashing (aka open addressing) - 特别是支持擦除操作时 - 对于易发生冲突的键/哈希函数具有不太稳定的性能属性。

关于散列函数的几句话

强哈希...

一个通用的、最坏情况冲突最小化散列函数的工作是随机有效地将键喷洒在散列表桶周围，同时始终为相同的键生成相同的散列值。理想情况下，即使密钥中任何位置的一位更改 - 随机 - 翻转结果哈希值中大约一半的位。

这通常与数学太复杂，我无法理解。我将提到一种易于理解的方式 - 不是最可扩展的或缓存友好的，但本质上是优雅的（例如使用一次性填充的加密！） - 因为我认为它有助于将上述理想品质带回家。假设您正在散列 64 位 double - 您可以创建 8 个表，每个表有 256 个随机数（代码如下），然后使用 double 的内存表示的每个 8 位/1 字节切片来索引另一个表，对您查找的随机数进行异或运算。使用这种方法，很容易看出 double 中任何位置的位（在二进制数字意义上）更改会导致在其中一个表中查找不同的随机数，以及完全不相关的最终值。

// note caveats above: cache unfriendly (SLOW) but strong hashing...
std::size_t random[8][256] = { ...random data... };
auto p = (const std::byte*)&my_double;
size_t hash = random[0][p[0]] ^
              random[1][p[1]] ^
              ... ^
              random[7][p[7]];

弱但经常快速的哈希...

许多库的散列函数通过不变传递整数（称为平凡或恒等散列函数）；这是上述强散列的另一个极端。在最坏的情况下，身份哈希非常容易发生冲突，但希望在整数键的相当常见的情况下，往往会增加（可能有一些间隙），它们将映射到连续的桶中，留下比随机散列更少的空离开（我们在前面提到的负载因子 1 时约为 36.8%），因此与随机映射相比，碰撞更少，碰撞元素的更长链表也更少。节省生成强哈希所需的时间也很棒，如果按顺序查找键，它们将在内存中附近的存储桶中找到，从而提高缓存命中率。当密钥不能很好地增加时，希望它们足够随机，它们不需要强大的哈希函数来完全随机地将它们放置到桶中。

---

你们非常接近完全解释这一点，但缺少一些东西。哈希表只是一个数组。数组本身将在每个插槽中包含一些东西。至少，您将在此插槽中存储散列值或值本身。除此之外，您还可以存储在此插槽上发生冲突的值的链接/链式列表，或者您可以使用开放寻址方法。您还可以存储一个或多个指向要从此插槽中检索的其他数据的指针。

需要注意的是，哈希值本身通常不指示放置值的槽。例如，哈希值可能是负整数值。显然负数不能指向数组位置。此外，哈希值往往比可用槽数大很多倍。因此哈希表本身需要执行另一个计算来确定值应该进入哪个槽。这是通过模数数学运算完成的，例如：

uint slotIndex = hashValue % hashTableSize;

该值是该值将进入的槽。在开放寻址中，如果槽已经被另一个哈希值和/或其他数据填充，则将再次运行模运算以找到下一个槽：

slotIndex = (remainder + 1) % hashTableSize;

我想可能还有其他更高级的方法来确定槽索引，但这是我见过的常见方法……会对其他性能更好的方法感兴趣。

使用模数方法，如果您有一个大小为 1000 的表，则任何介于 1 和 1000 之间的哈希值都将进入相应的插槽。任何负值和任何大于 1000 的值都可能是冲突槽值。发生这种情况的机会取决于您的散列方法，以及您添加到散列表中的总项目数。通常，最佳做法是使散列表的大小使得添加到其中的值的总数仅等于其大小的大约 70%。如果您的哈希函数在均匀分布方面做得很好，您通常会遇到很少甚至没有桶/槽冲突，并且它会非常快速地执行查找和写入操作。如果事先不知道要添加的值的总数，请使用任何方法进行良好的猜测，然后在添加到其中的元素数量达到容量的 70% 时调整哈希表的大小。

我希望这有帮助。

PS - 在 C# 中，GetHashCode() 方法非常慢，并且在我测试过的很多条件下都会导致实际值冲突。为了获得真正的乐趣，构建自己的哈希函数并尝试让它永远不会与您正在哈希的特定数据发生冲突，运行速度比 GetHashCode 快，并且分布相当均匀。我已经使用 long 而不是 int 大小的哈希码值完成了这项工作，并且它在哈希表中多达 3200 万个整数哈希值上运行良好，并且冲突为 0。不幸的是，我无法共享代码，因为它属于我的雇主……但我可以透露某些数据域是可能的。当你能做到这一点时，哈希表会非常快。 :)

---

在我的理解中，它是这样工作的：

这是一个示例：将整个表想象为一系列桶。假设您有一个带有字母数字哈希码的实现，并且每个字母都有一个存储桶。此实现将哈希码以特定字母开头的每个项目放入相应的存储桶中。

假设您有 200 个对象，但其中只有 15 个具有以字母“B”开头的哈希码。哈希表只需要查找和搜索“B”桶中的 15 个对象，而不是所有 200 个对象。

就计算哈希码而言，它没有什么神奇之处。目标只是让不同的对象返回不同的代码，并让相同的对象返回相同的代码。您可以编写一个始终返回与所有实例的哈希码相同的整数的类，但您实际上会破坏哈希表的有用性，因为它只会变成一个巨大的桶。

---

简短而甜蜜：

哈希表包装了一个数组，我们称之为 internalArray。项目以这种方式插入到数组中：

let insert key value =
    internalArray[hash(key) % internalArray.Length] <- (key, value)
    //oversimplified for educational purposes

有时两个键会散列到数组中的相同索引，并且您希望保留这两个值。我喜欢将这两个值存储在同一个索引中，通过使 internalArray 成为链表数组来编写代码很简单：

let insert key value =
    internalArray[hash(key) % internalArray.Length].AddLast(key, value)

所以，如果我想从我的哈希表中检索一个项目，我可以这样写：

let get key =
    let linkedList = internalArray[hash(key) % internalArray.Length]
    for (testKey, value) in linkedList
        if (testKey = key) then return value
    return null

删除操作与编写一样简单。如您所知，从我们的链表数组中插入、查找和删除几乎是 O(1)。

当我们的 internalArray 太满时，可能在 85% 左右的容量，我们可以调整内部数组的大小并将所有项目从旧数组移动到新数组中。

---

它甚至比这更简单。

哈希表只不过是包含键/值对的向量数组（通常是 sparse 之一）。此数组的最大大小通常小于存储在哈希表中的数据类型的可能值集中的项目数。

哈希算法用于根据将存储在数组中的项目的值生成该数组的索引。

这是在数组中存储键/值对向量的地方。由于可以作为数组中索引的值集通常小于该类型可以具有的所有可能值的数量，因此您的哈希值可能算法将为两个单独的键生成相同的值。一个好的散列算法会尽可能地防止这种情况（这就是为什么它通常被归为类型，因为它具有一般散列算法不可能知道的特定信息），但这是不可能防止的。

因此，您可以拥有多个生成相同哈希码的密钥。发生这种情况时，将遍历向量中的项目，并在向量中的键和正在查找的键之间进行直接比较。如果找到，则返回与该键关联的值，否则不返回任何内容。

---

你拿了一堆东西和一个数组。

对于每一件事，你为它建立一个索引，称为哈希。哈希的重要之处在于它“分散”很多。您不希望两个相似的事物具有相似的哈希值。

你把你的东西放在哈希指示的位置的数组中。一个给定的哈希值可能不止一个东西，所以你将这些东西存储在数组或其他适当的东西中，我们通常称之为桶。

当您在哈希中查找内容时，您会执行相同的步骤，找出哈希值，然后查看该位置的存储桶中的内容并检查它是否是您要查找的内容。

当你的散列运行良好并且你的数组足够大时，在数组中的任何特定索引处最多只会有一些东西，所以你不必看太多。

对于奖励积分，请使其在访问您的哈希表时将找到的东西（如果有）移动到存储桶的开头，所以下次它是第一个检查的东西。

---

到目前为止，所有答案都很好，并且涉及哈希表如何工作的不同方面。这是一个可能有帮助的简单示例。假设我们想要存储一些带有小写字母字符串的项目作为键。

正如 simon 所解释的，散列函数用于从大空间映射到小空间。对于我们的示例，哈希函数的一个简单、朴素的实现可以获取字符串的第一个字母，并将其映射到一个整数，因此“alligator”的哈希码为 0，“bee”的哈希码为 1，“斑马”将是 25 等。

接下来我们有一个由 26 个桶组成的数组（在 Java 中可能是 ArrayLists），我们将项目放入与我们的键的哈希码匹配的桶中。如果我们有多个项目的键以相同的字母开头，它们将具有相同的哈希码，因此所有项目都将进入该哈希码的桶中，因此必须在桶中进行线性搜索以找到一个特定的项目。

在我们的示例中，如果我们只有几十个项目的键跨越字母表，它会很好地工作。但是，如果我们有一百万个项目或所有键都以“a”或“b”开头，那么我们的哈希表将不理想。为了获得更好的性能，我们需要一个不同的哈希函数和/或更多的桶。

---

基本理念

为什么人们使用梳妆台来存放他们的衣服？除了看起来时尚和时尚，他们的优势在于每件衣服都有它应该在的地方。如果您正在寻找一双袜子，您只需检查袜子抽屉。如果你正在寻找一件衬衫，你可以检查一下里面有你的衬衫的抽屉。当你在寻找袜子时，你有多少件衬衫或你拥有多少条裤子都没关系，因为你不需要看它们。您只需查看袜子抽屉并期望在那里找到袜子。

在高层次上，哈希表是一种存储东西的方式（有点像），就像衣服的梳妆台一样。基本思想如下：

你会得到一些可以存放物品的位置（抽屉）。

你想出了一些规则，告诉你每个项目属于哪个位置（抽屉）。

当您需要查找某些东西时，您可以使用该规则来确定要查看的抽屉。

像这样的系统的优势在于，假设您的规则不太复杂并且您有适当数量的抽屉，您只需在正确的位置查找即可很快找到您要查找的内容。

当你把衣服收起来时，你使用的“规则”可能是“袜子放在左上方的抽屉里，衬衫放在中间的大抽屉里，等等”。但是，当您存储更多抽象数据时，我们会使用一种称为哈希函数的方法来为我们执行此操作。

考虑散列函数的一种合理方式是作为一个黑盒。你把数据放在一边，一个叫做哈希码的数字从另一边出来。从示意图上看，它看起来像这样：

              +---------+
            |\|   hash  |/| --> hash code
   data --> |/| function|\|
              +---------+

所有散列函数都是确定性：如果您将相同的数据多次放入函数中，您总是会从另一端得到相同的值。一个好的散列函数应该看起来或多或少是随机的：输入数据的微小变化应该给出截然不同的散列码。例如，字符串 "pudu" 和字符串 "kudu" 的哈希码可能会彼此完全不同。 （再说一遍，它们可能是相同的。毕竟，如果哈希函数的输出看起来或多或少是随机的，那么我们有可能两次获得相同的哈希码。）

您究竟是如何构建散列函数的？现在，让我们继续“体面的人不应该想太多”。数学家已经想出了更好和更差的方法来设计散列函数，但为了我们的目的，我们真的不需要太担心内部结构。把散列函数想象成一个函数就好了

确定性（相等的输入给出相等的输出），但是

看起来是随机的（很难预测给定另一个哈希码）。

一旦我们有了哈希函数，我们就可以构建一个非常简单的哈希表。我们将制作一系列“桶”，您可以将其视为类似于我们梳妆台中的抽屉。要将项目存储在哈希表中，我们将计算对象的哈希码并将其用作表中的索引，这类似于“选择该项目进入哪个抽屉”。然后，我们将该数据项放入该索引处的存储桶中。如果那个桶是空的，那就太好了！我们可以把物品放在那里。如果那个桶是满的，我们可以做一些选择。一种简单的方法（称为 chained hashing）是将每个存储桶视为项目列表，就像您的袜子抽屉可能存储多个袜子一样，然后只需将项目添加到该索引处的列表中。

要在哈希表中查找某些内容，我们使用基本相同的过程。我们首先计算要查找的项目的哈希码，它告诉我们要查找哪个桶（抽屉）。如果项目在表中，它必须在那个桶中。然后，我们只需查看存储桶中的所有项目，看看我们的项目是否在其中。

这样做有什么好处？好吧，假设我们有大量的桶，我们希望大多数桶中不会有太多的东西。毕竟，我们的散列函数看起来有点像随机输出，所以项目在所有桶中均匀分布。事实上，如果我们形式化“我们的哈希函数看起来有点随机”的概念，我们可以证明每个桶中的预期项目数是项目总数与桶总数的比率。因此，我们无需做太多工作就可以找到我们正在寻找的项目。

细节

解释“哈希表”的工作原理有点棘手，因为哈希表有很多种。下一节将讨论所有哈希表共有的一些通用实现细节，以及不同风格的哈希表如何工作的一些细节。

出现的第一个问题是如何将哈希码转换为表槽索引。在上面的讨论中，我只是说“使用哈希码作为索引”，但这实际上不是一个好主意。在大多数编程语言中，散列码都适用于 32 位或 64 位整数，您不能直接将它们用作存储桶索引。相反，一种常见的策略是创建一个大小为 m 的存储桶数组，为您的项目计算（完整的 32 位或 64 位）哈希码，然后根据表的大小对它们进行修改以获得介于 0 和m-1，包括在内。模数的使用在这里效果很好，因为它速度很快，并且可以很好地将全范围的哈希码传播到更小的范围内。

（您有时会看到此处使用的按位运算符。如果您的表的大小是 2 的幂，例如 2k，那么计算哈希码的按位与，然后计算 2k - 1 相当于计算模数，这很重要快点。）

下一个问题是如何选择正确数量的桶。如果你选择了太多的桶，那么大多数桶将是空的或只有很少的元素（有利于速度 - 你只需要检查每个桶的几个项目），但你会使用一堆空间来简单地存储桶（不是这样太好了，虽然也许你买得起）。另一面也适用——如果桶太少，那么平均每个桶会有更多的元素，这使得查找需要更长的时间，但你会使用更少的内存。

一个好的折衷方案是在哈希表的生命周期内动态更改存储桶的数量。哈希表的负载因子，通常表示为 α，是元素数与桶数的比率。大多数哈希表选择一些最大负载因子。一旦负载因子超过此限制，哈希表就会增加其槽数（例如，通过加倍），然后将旧表中的元素重新分配到新表中。这称为重新散列。假设表中的最大负载因子是一个常数，这确保了，假设你有一个好的散列函数，进行查找的预期成本仍然是 O(1)。由于定期重建表的成本，插入现在的摊销预期成本为 O(1)，就像删除一样。 （如果负载因子太小，删除同样可以压缩表。）

哈希策略

到目前为止，我们一直在讨论链式哈希，这是构建哈希表的许多不同策略之一。提醒一下，链式散列有点像衣服梳妆台 - 每个桶（抽屉）可以容纳多个物品，当您进行查找时，您会检查所有这些物品。

但是，这不是构建哈希表的唯一方法。还有另一类哈希表使用称为 open addressing 的策略。开放寻址背后的基本思想是存储一个 slots 数组，其中每个 slot 可以是空的，也可以只容纳一个项目。

在开放寻址中，当您执行插入时，像以前一样，您会跳转到某个插槽，其索引取决于计算的哈希码。如果该插槽是免费的，那就太好了！你把物品放在那里，你就完成了。但是如果插槽已经满了怎么办？在这种情况下，您可以使用一些辅助策略来找到一个不同的空闲槽来存储该项目。执行此操作的最常见策略使用称为 linear probing 的方法。在线性探测中，如果您想要的插槽已满，您只需转移到表中的下一个插槽。如果那个插槽是空的，太好了！你可以把物品放在那里。但是，如果该槽已满，则您将移至表中的下一个槽，依此类推（如果您到达表的末尾，则返回到开头）。

线性探测是构建哈希表的一种非常快速的方法。 CPU 缓存针对 locality of reference 进行了优化，因此在相邻内存位置的内存查找往往比在分散位置的内存查找快得多。由于线性探测插入或删除通过击中某个数组槽然后线性向前移动来工作，因此它会导致很少的缓存未命中并且最终比理论通常预测的要快得多。 （而且理论预测它会非常快！）

最近流行的另一种策略是cuckoo hashing。我喜欢将杜鹃散列视为散列表的“冻结”。我们有两个哈希表和两个哈希函数，而不是一个哈希表和一个哈希函数。每个项目都可以恰好位于两个位置中的一个 - 它要么位于第一个哈希函数给出的第一个表中的位置，要么位于第二个哈希函数给出的第二个表中的位置。这意味着查找是最坏情况高效的，因为您只需检查两个点即可查看表中是否有内容。

杜鹃散列中的插入使用与以前不同的策略。我们首先查看可以容纳该项目的两个插槽中的任何一个是否空闲。如果是这样，太好了！我们只是把物品放在那里。但如果这不起作用，那么我们选择一个插槽，将项目放在那里，然后踢出曾经在那里的项目。该物品必须放在某个地方，因此我们尝试将其放在另一张桌子的适当位置。如果这行得通，那就太好了！如果没有，我们将一个项目踢出该表并尝试将其插入另一个表。这个过程一直持续到一切都平静下来，或者我们发现自己陷入了一个循环。 （后一种情况很少见，如果发生这种情况，我们有很多选择，例如“将其放入辅助哈希表”或“选择新的哈希函数并重建表。”）

杜鹃散列有许多改进可能，例如使用多个表，让每个插槽容纳多个项目，以及制作一个“存储”以容纳其他任何地方都无法容纳的项目，这是一个活跃的研究领域！

然后是混合方法。 Hopscotch hashing 是开放寻址和链式哈希之间的混合，可以认为是采用链式哈希表并将每个存储桶中的每个项目存储在项目想要去的位置附近的插槽中。这种策略与多线程配合得很好。 Swiss table 利用一些处理器可以用一条指令并行执行多个操作的事实来加速线性探测表。 Extendible hashing 专为数据库和文件系统而设计，并混合使用 trie 和链式哈希表，以便在加载各个存储桶时动态增加存储桶大小。 Robin Hood hashing 是线性探测的一种变体，其中项目可以在插入后移动，以减少每个元素可以居住的离家多远的差异。

延伸阅读

有关哈希表基础知识的更多信息，请查看 these lecture slides on chained hashing 和 these follow-up slides on linear probing and Robin Hood hashing。您可以了解有关 cuckoo hashing here 和 theoretical properties of hash functions here 的更多信息。

---

这是另一种看待它的方式。

我假设您了解数组 A 的概念。它支持索引操作，无论 A 有多大，您都可以一步到达第 I 个元素 A[I]。

因此，例如，如果你想存储一组碰巧有不同年龄的人的信息，一个简单的方法是有一个足够大的数组，并使用每个人的年龄作为数组的索引。通过这种方式，您可以一步访问任何人的信息。

但是当然可能有不止一个人具有相同的年龄，因此您在每个条目中放入的数组是所有具有该年龄的人的列表。因此，您可以通过一个步骤以及在该列表（称为“存储桶”）中的一点点搜索来获取个人信息。只有当人太多以至于水桶变大时，它才会放慢速度。然后你需要一个更大的数组，以及其他一些方法来获取更多关于这个人的识别信息，比如他们姓氏的前几个字母，而不是使用年龄。

这是基本的想法。可以使用产生良好传播价值的人的任何功能，而不是使用年龄。这就是哈希函数。就像您可以将人名的 ASCII 表示的每三分之一位按某种顺序打乱一样。重要的是你不希望太多人散列到同一个桶，因为速度取决于桶保持小。

---

哈希表完全适用于实际计算遵循随机访问机器模型的事实，即内存中任何地址的值都可以在 O(1) 时间或恒定时间内访问。

所以，如果我有一个键域（我可以在应用程序中使用的所有可能键的集合，例如学生的卷号，如果它是 4 位数字，那么这个域是一组从 1 到 9999 的数字），以及将它们映射到一组有限大小的方法我可以在我的系统中分配内存，理论上我的哈希表已经准备好了。

通常，在应用程序中，键域的大小比我要添加到哈希表的元素数量大得多（我不想浪费 1 GB 内存来散列，比如 10000 或 100000 个整数值，因为它们是 32二进制表示中的位长）。所以，我们使用这种散列。这是一种混合的“数学”运算，它将我的大宇宙映射到我可以在内存中容纳的一小组值。在实际情况下，哈希表的空间通常与（元素数*每个元素的大小）具有相同的“顺序”（big-O），因此，我们不会浪费太多内存。

现在，一个大集合映射到一个小集合，映射必须是多对一的。因此，不同的键将被分配相同的空间（？？不公平）。有几种方法可以解决这个问题，我只知道其中流行的两种：

使用要分配给该值的空间作为对链表的引用。这个链表将存储一个或多个值，这些值在多对一映射中驻留在同一个槽中。链接列表还包含帮助来搜索的人的键。就像很多人在同一个公寓里，当一个送货员来的时候，他会去房间里专门找那个人。

在数组中使用双哈希函数，每次都给出相同的值序列，而不是单个值。当我去存储一个值时，我会查看所需的内存位置是空闲的还是被占用的。如果它是免费的，我可以在那里存储我的值，如果它被占用，我从序列中获取下一个值，依此类推，直到我找到一个空闲位置并将我的值存储在那里。在搜索或检索该值时，我返回与序列给出的相同路径，并在每个位置询问是否存在该值，直到我找到它或搜索数组中的所有可能位置。

CLRS 的算法简介提供了关于该主题的非常好的见解。

---

哈希的计算方式通常不取决于哈希表，而是取决于添加到其中的项目。在 .net 和 Java 等框架/基类库中，每个对象都有一个 GetHashCode()（或类似）方法，该方法返回该对象的哈希码。理想的哈希码算法和准确的实现取决于对象中所代表的数据。

---

直接地址表

https://i.stack.imgur.com/DrxLD.png

直接地址表直接使用键作为数组中槽的索引。 Universe 键的大小等于数组的大小。在 O(1) 时间内访问此密钥非常快，因为数组支持随机访问操作。

但是，在实现直接地址表之前有四个注意事项：

要成为有效的数组索引，键应该是整数。键的范围相当小，否则，我们将需要一个巨大的数组。不是两个不同的键映射到数组中的同一个槽Universe键的长度等于数组的长度

事实上，现实生活中并没有很多情况符合上述要求，所以哈希表来拯救

哈希表

哈希表不是直接使用密钥，而是首先应用数学哈希函数将任意密钥数据一致地转换为数字，然后使用该哈希结果作为密钥。

Universe 键的长度可以大于数组的长度，这意味着两个不同的键可以散列到同一个索引（称为散列冲突）？

实际上，有几种不同的策略来处理它。这是一个常见的解决方案：我们不是将实际值存储在数组中，而是存储一个指向链表的指针，该链表包含散列到该索引的所有键的值。

如果您仍有兴趣了解如何从头开始实施哈希图，请阅读following post

https://i.stack.imgur.com/KzcEM.png

---

对于所有寻找编程术语的人来说，这是它的工作原理。高级哈希表的内部实现对于存储分配/解除分配和搜索有许多复杂性和优化，但顶层的想法将非常相似。

(void) addValue : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   if (bucket) 
   {
       //do nothing, just overwrite
   }
   else   //create bucket
   {
      create_extra_space_for_bucket();
   }
   put_value_into_bucket(bucket,value);
}

(bool) exists : (object) value
{
   int bucket = calculate_bucket_from_val(value);
   return bucket;
}

其中 calculate_bucket_from_val() 是所有唯一性魔法必须发生的散列函数。

经验法则是：对于要插入的给定值，存储桶必须是唯一的并且可以从它应该存储的值中派生。

Bucket 是存储值的任何空间 - 因为在这里我将它保存为 int 作为数组索引，但它也可能是一个内存位置。

---

里面的哈希表包含存储密钥集的罐子。哈希表使用哈希码来决定密钥对应该计划到哪个。从 Key 的 hashcode 中获取容器区域的能力称为 hash work。原则上，散列工作是一种容量，当给定一个键时，它会在表中创建一个地址。哈希工作始终返回项目的数字。两个等效的项目将始终具有相似的数字，而两个不一致的对象通常可能不会具有不同的数字。当我们将对象放入哈希表时，可以想象各种对象可能具有相同/相同的哈希码。这被称为碰撞。为了确定冲突，哈希表使用了各种列表。映射到单个数组索引的集合存储在列表中，然后列表引用存储在索引中。

---