哈希表是如何工作的？

Question

哈希表是如何工作的？

data-structureshashhashtablemodulo

541

我正在寻找一种简单易懂的方式解释哈希表的工作原理！

例如，我知道它需要获取键(key)，计算哈希值(我想知道如何计算)，然后执行某种取模运算，以确定其位于存储值的数组中的位置, 但我的知识就止步于此。

有没有人能够澄清这个过程呢？

编辑：我不是特别关心哈希码(hash code)如何计算，而是对哈希表的一般概述。

- Arec Barrwin

4

最近，我写了一篇文章(http://en.algoritmy.net/article/50101/Hash-table)，描述了几种存储和查找数据的方法，重点介绍了哈希表及其策略（分离链接、线性探测、双重哈希）。 - malejpavouk

1

你可以将哈希表看作是数组的扩展版本，它不仅限于连续的整数键。 - user253751

1

这是另一个链接：https://intelligentjava.wordpress.com/2016/10/19/introduction-to-hash-tables/ - nesvarbu

17个回答

110

用法和术语：

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

真实世界的例子：

Hash＆Co.成立于1803年，缺乏任何计算机技术，拥有300个文件柜，用于存放约30,000名客户的详细信息（即记录）。每个文件夹都用其客户号码清楚地标识，这是一个从0到29,999的唯一数字。

当时的归档员必须为工作人员快速提取和存储客户记录。工作人员决定使用哈希方法存储和检索他们的记录会更有效率。

为了归档客户记录，归档员将使用写在文件夹上的唯一客户号码。使用此客户号码，他们将通过300进行哈希键调制，以确定所包含的文件柜。打开文件柜后，他们将发现其中包含许多按客户号码排序的文件夹。在确定正确位置后，他们只需将其放入即可。

要检索客户记录，归档员会收到一张写有客户号码的纸条。使用此唯一客户号码（哈希键），他们将通过300进行调制，以确定哪个文件柜有客户文件夹。打开文件柜后，他们将发现其中包含许多按客户号码排序的文件夹。搜索记录时，他们会快速找到客户文件夹并检索它。

在我们的真实世界示例中，我们的桶是文件柜，我们的记录是文件夹。

需要记住的一件重要的事情是，计算机（及其算法）处理数字比字符串更快。所以使用索引访问大型数组比顺序访问要快得多。

正如Simon所提到的，我认为哈希部分将一个长度任意的大空间（通常是字符串等）映射到一个已知大小的小空间（通常是数字）进行索引非常重要。这一点非常重要！

因此，在上面的示例中，大约有30,000个可能的客户被映射到一个较小的空间。

这个思路的主要想法是将整个数据集划分成段，以加速通常耗时的实际搜索过程。在我们上面的示例中，每个300个文件柜（统计学上）会包含大约100个记录。通过100个记录进行搜索（无论顺序如何）比处理30,000个记录要快得多。

您可能已经注意到，有些人已经这样做了。但是，他们通常不是通过设计哈希方法生成哈希键，而是直接使用姓氏的第一个字母。因此，如果您有26个文件柜，每个文件柜包含A到Z的一个字母，则在理论上，您只是将数据分段并增强了文件和检索过程。

- Jeach

2

你描述了一种特定类型的哈希表冲突避免策略，称为“开放寻址”或“闭合寻址”（是的，很遗憾但却是真实的）或“链式”。还有另一种类型，它不使用列表桶，而是将项目“内联”存储。 - Konrad Rudolph

2

非常好的描述。除了每个文件柜平均包含约100条记录（30k条记录/ 300个文件柜= 100）之外。可能值得编辑一下。 - ryantuck

@TonyD，前往此网站sha-1在线并为输入在文本字段中的“TonyD”生成SHA-1哈希值。最终你将得到一个看起来像e5dc41578f88877b333c8b31634cf77e4911ed8c的生成值。这只是一个160位（20字节）的十六进制数。然后，您可以使用此值确定将用于存储记录的桶（数量有限）。 - Jeach

@TonyD，我不确定“哈希键”一词在哪里引起了冲突？如果是这样，请指出两个或更多位置。还是你在说“我们”使用“哈希键”这个术语，而其他网站如维基百科则使用“哈希值、哈希码、哈希和或简单哈希”？如果是这样，那么只要在一个组或组织内使用的术语是一致的，谁在乎呢。程序员经常使用“键”这个术语。我个人认为另一个很好的选择是“哈希值”。但我会排除使用“哈希码、哈希和或简单哈希”的可能性。专注于算法而不是词语！ - Jeach

2

@TonyD，我已经将文本更改为“他们将通过300模块化哈希键”，希望对每个人来说更清晰明了。谢谢！ - Jeach

@Jeach 这也非常有帮助，我一直在网上寻找关于哈希的直观解释，这个回复列表非常棒！ - carozimm

67

这是一个相当深入的理论领域，但基本概述很简单。

实际上，哈希函数只是将来自一个空间（比如任意长度的字符串）的内容映射到可用于索引的空间（无符号整数）的函数。

如果你只有一个小的哈希空间，你可能可以将那些内容视为整数并且直接使用（例如4字节的字符串），然后你就完成了

通常情况下，你要处理的空间更大。如果作为键的内容空间大于用于索引的空间（例如uint32），则不可能为每个键都生成唯一的值。当两个或多个内容散列到相同结果时，你必须以适当的方式处理冗余（通常称为冲突，并且你应该根据使用哈希的目的选择如何处理它）。

这意味着你希望重复的结果出现的概率很小，并且你可能真的希望哈希函数非常快速。

平衡这两个属性及其他几个属性一直占据着许多人的时间！

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

现在来使它作为哈希表：想象一下你不关心内存使用情况。那么，你可以创建一个与索引集（所有uint32）一样长的数组。当你向表中添加内容时，你会散列它的键并查看该索引位置处的数组。如果那里没有任何内容，你就将值放在那里。如果那里已经有了其他内容，你将把这个新条目添加到该地址的条目列表中，并添加足够的信息（你的原始键或一些聪明的东西）以查找哪个条目实际上属于哪个键。

因此，当你遍历哈希表时，哈希表中的每个条目（数组）都是空的、包含一个条目或多个条目的列表。检索操作只需要将其索引到数组中，并返回相应的值，或者遍历值列表并返回正确的值即可。

当然，在实践中，你通常无法这样做，它会浪费太多内存。因此，你需要基于稀疏数组进行所有操作（只有实际使用的条目才有输入，其他所有内容都默认为 null）。

有许多方案和技巧可以使其更好地工作，但这就是基础。

- simon

1

抱歉，我知道这是一个老问题/答案，但我一直在努力理解你所说的最后一点。哈希表具有O(1)时间复杂度。然而，一旦你使用了稀疏数组，难道你不需要执行二分查找来找到你的值吗？此时时间复杂度不会变成O(log n)吗？ - herbrandson

@herbrandson：不是...稀疏数组只是指相对较少的索引被赋予了值 - 您仍然可以直接索引到您从密钥计算出的哈希值的特定数组元素; 尽管如此，Simon描述的稀疏数组实现仅在非常有限的情况下才是明智的：当桶大小与内存页大小相当时（而不是1/1000稀疏度和4k页面的int键 = 大多数页面被触摸），并且当操作系统高效地处理所有0页面（因此所有未使用的bucket页面不需要支持内存）时，地址空间是充足的... - Tony Delroy

@TonyDelroy - 这是真的，这是一种过度简化，但是想法是为了概述它们是什么以及为什么，而不是实际实现。后者的细节更加微妙，正如您在扩展中所提到的那样。 - simon

65

有很多答案，但它们没有一个是非常直观的，并且哈希表可以很容易地通过可视化进行“点击”。

哈希表通常被实现为链表数组。如果我们想象一个存储人名的表，在插入几个名字后，它可能在内存中布局如下，其中括号中的数字是文本/名称的哈希值。

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范围内。

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

哈希表如何将键与值关联

假设有一个像上面描述的哈希表实现，我们可以想象创建一个值类型，例如`struct Value { string name; int age; };`，以及只查看`name`字段（忽略年龄）的等式比较和哈希函数，然后出现了一些奇妙的事情：我们可以在表中存储`Value`记录，例如`{"sue", 63}`，然后稍后搜索"sue"而不知道她的年龄，找到存储的值并恢复甚至更新她的年龄-生日快乐Sue-这不会改变哈希值，因此不需要将Sue的记录移动到另一个桶中。

这样做时，我们将哈希表用作关联容器，也称为映射，它存储的值可被视为包含一个键（名称）和一个或多个其他字段，仍称为-令人困惑的是-值（在我的例子中只有年龄）。用作映射的哈希表实现称为哈希映射。

这与本答案前面的示例形成对比，我们存储如"sue"这样的离散值，您可以认为它是其自身的键：这种用法称为哈希集。

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

并非所有哈希表都使用链接列表（称为分离链接），但大多数通用哈希表都会使用，因为主要的替代方案闭散列（也称为开放寻址） - 特别是支持删除操作-具有不太稳定的性能特性，因为它容易发生键/哈希函数冲突。

关于哈希函数的几句话

强哈希...

一个通用的、最坏情况下冲突最小化的哈希函数的工作是将密钥有效地随机分散在哈希表桶中，同时始终为相同的密钥生成相同的哈希值。即使密钥中的任何一个位发生变化，理想情况下，哈希值中大约一半的位会被随机翻转。

通常，这需要我难以理解的复杂数学来进行编排。我将提及一种易于理解的方式——不是最可扩展或缓存友好的方式，但本质上是优美的（就像使用一次性密码进行加密一样！）——因为我认为它有助于强调上述所述的理想特质。假设您要对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%），从而具有较少的冲突和较短的冲突元素链接列表，比随机映射实现的要少得多。它还可以节省生成强哈希所需的时间，并且如果按顺序查找键，则它们将在内存附近的桶中找到，从而提高缓存命中率。当键不适合递增时，希望它们足够随机，不需要强哈希函数来完全随机化它们放置到桶中。

- Tony Delroy

8

允许我说一句：回答太棒了。 - CRThaze

@selman：你的问题没有提供足够的细节来解释为什么你认为它可能是O(log100,000,000)，但你确实说“即使我们有所有的桶都排好序了”-请记住，哈希表桶中的值从来不会按照通常意义上的“排序”：哪个值出现在哪个桶中是通过将哈希函数应用于键来确定的。认为复杂度是O(log100,000,000)意味着你想象通过已排序的桶进行二分查找，但这不是哈希的工作方式。也许阅读一些其他答案，看看是否开始变得更加清晰。 - Tony Delroy

@TonyDelroy 好的，但是......你谈论的是“形成到桶数组的索引”。因此，即使有索引，访问特定的桶也是有成本的，如果这个数组有100.00.000个桶，如何在100.00.000个桶的数组中实现O(1)的查找成本呢？ - selman

1

@selman：因为计算机内存允许常数时间的“随机访问”：如果您可以计算出内存地址，则可以检索内存内容，而无需访问数组其他部分的内存。因此，无论您访问第一个桶、最后一个桶还是中间任何位置的桶，它都具有相同的性能特征（松散地说，需要相同的时间，尽管受到CPU L1/L2/L3内存缓存影响，但它们只能帮助您快速重新访问最近访问或巧合附近的桶，并且可以在大O分析中忽略）。 - Tony Delroy

只想补充一下，负载因子为a和n个桶时，每个桶具有二项式概率{{an}\choose k}1/n^k(1-1/n)^{an-k} 具有k个元素。当a和k保持不变时，随着n趋近于无穷大，概率趋近于Poisson分布e^{-a}a^k/k!。这给出了每个桶中平均元素数量的数值百分比值。 - Hans

显示剩余15条评论

24

你们已经非常接近完全解释这个问题了，但还是有一些遗漏。哈希表其实就是一个数组。这个数组的每个槽位都会存储某些内容。至少你需要在这个槽位中存储哈希值或者实际的值。除此之外，你还可以在这个槽位中存储发生碰撞的值的链表或者使用开放寻址法。你也可以在这个槽位中存储指向其他要检索出的数据的指针。

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

我想可能有其他更先进的方法来确定插槽索引，但这是我看到的常见方法...如果有其他更优越的方法，我会很感兴趣。

使用模数法，如果您有一个大小为1000的表格，任何介于1和1000之间的哈希值都会进入相应的插槽。任何负值和大于1000的值将潜在地发生冲突的插槽值。发生这种情况的机会取决于您的哈希方法以及向哈希表中添加的总项数。通常，最好将散列表的大小设置为其大小的约70％，这样添加到其中的总值仅等于其大小的约70％。如果您的哈希函数能够均匀分布，您通常会遇到很少或没有桶/插槽碰撞，并且查找和写入操作都能够非常快速地执行。如果不能预先知道要添加的值的总数，请使用任何方法进行良好的估计，然后一旦添加到其中的元素数量达到容量的70％，就调整散列表的大小。

希望这可以帮助您。

PS-在C＃中，GetHashCode()方法相当缓慢，并在许多条件下导致实际值冲突。为了获得实际乐趣，请构建自己的哈希函数，并尝试使其在散列的特定数据上从不发生碰撞，运行速度比GetHashCode快，并具有相当均匀的分布。我已经使用长而不是int大小的哈希码值完成此操作，并在最多3200万个条目的哈希表中工作得非常好，没有冲突。不幸的是，我不能分享代码，因为它属于我的雇主...但我可以透露在某些数据域中是可能的。当您能够做到这一点时，哈希表非常快。

- Chris

我知道这篇文章很旧了，但有人能解释一下这里的（余数+1）是什么意思吗？ - Hari

3

“remainder”指的是原始取模计算的结果，我们在其基础上加1以找到下一个可用的位置。 - x4nd3r

数组本身将在每个槽中包含某些内容。最少，您将在此槽中存储哈希值或值本身。对于“槽位”（桶），不存储任何值很常见；开放地址实现通常存储NULL或指向链接列表中第一个节点的指针 - 槽/桶中没有直接的值。如果有其他的实现方式，我会感兴趣。你所展示的“+1”被称为线性探测，通常表现更好的是：二次探测。一般情况下，几乎不会遇到桶/槽冲突，@ 70%容量，约12%的槽具有2个值，约3%的槽具有3个值... - Tony Delroy

“我已经使用长整型而不是整型大小的哈希值来完成了这个任务，在哈希表中最多有3200万个条目的情况下，哈希值为0的碰撞非常少。”但是在一般情况下，这根本不可能，因为键的值实际上是随机的，并且远远超出桶的数量。请注意，拥有不同的哈希值通常足够容易（您提到的长整型哈希值意味着这就是您所实现的），但是在模除/％操作之后确保它们不会在哈希表中发生冲突（在一般情况下）是不可能的。 - Tony Delroy

1

避免所有碰撞被称为“完美哈希”。通常，这对于预先知道的几百或几千个键是实用的 - gperf是计算这种哈希函数的工具的示例。在非常有限的情况下，您也可以编写自己的哈希函数 - 例如，如果您的键是指向自己的内存池中对象的指针，并且该内存池保持相当充满，每个指针之间有固定的距离，您可以将指针除以该距离并有效地拥有一个索引到略微稀疏的数组中，从而避免碰撞。 - Tony Delroy

20

这是我理解的工作原理:

举个例子，可以将整个表格想象成一系列桶。假设你有一个使用字母数字哈希代码的实现，并且每个字母表中都有一个桶。此实现会将其哈希码以特定字母开头的每个项放入相应的桶中。

假设你有200个对象，但只有15个对象的哈希码以字母'B'开头。哈希表只需要查找并搜索'B'桶中的15个对象，而不是所有200个对象。

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

- AndreiM

13

简短明了：

哈希表包装了一个数组，我们称之为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)的。

当我们的内部数组变得太满，也许在大约85%的容量时，我们可以重新调整内部数组大小，并将所有项目从旧数组移动到新数组中。

- Juliet

12

比这更简单。

散列表不过是一个数组（通常是sparse的），其中包含键/值对的向量。该数组的最大大小通常小于散列表中存储的数据类型可能具有的所有值的集合中的项目数。

散列算法用于根据将存储在数组中的项的值生成数组中的索引。

这就是把键/值对的向量存储在数组中的地方。因为可以用作数组索引的值的集合通常比类型可能具有的所有可能值的数量要小，所以您的散列算法有可能为两个单独的键生成相同的值。好的散列算法会尽可能避免这种情况（这就是为什么它通常被归类到类型中，因为它拥有一些一般的散列算法不可能知道的特定信息），但是防不胜防。

由于这个原因，您可以有多个键将生成相同的哈希代码。当发生这种情况时，迭代通过向量中的项，并直接比较向量中的键和正在查找的键。如果找到，则返回与键相关联的值，否则不返回任何内容。

- casperOne

11

你需要拿一些东西和一个数组。

对于每个东西，你都要为它创建一个索引，称为哈希。哈希的重要之处在于它会“分散”很多；你不希望两个相似的东西有相似的哈希值。

你将这些东西放入数组中，位置由哈希值指示。可能会有多个东西落在同一个哈希位置，所以你需要将这些东西存储在数组或其他适当的容器中，我们通常把这个容器称为桶。

当你在哈希表中查找东西时，需要执行相同的步骤，计算出哈希值，然后看看该位置的桶中是否有你要找的东西。

当哈希函数工作得很好且数组足够大时，任何特定索引处都只会有很少的东西，因此你不需要查看太多。

为了额外加分，使哈希表被访问时，如果找到了东西，就将其移到桶的最前面，下次查找时会首先检查它。

- chaos

2

谢谢你提到了其他人都忽略的最后一点。 - Sandeep Raju Prabhakar

6

基本思想

为什么人们使用梳妆台来存放衣服呢？除了看起来时尚和有型之外，它们的优点在于每件衣服都有一个应该放置的位置。如果你要找一双袜子，你只需要检查袜子抽屉。如果你要找一件衬衫，你就检查有衬衫的抽屉。无论你有多少件衬衫或裤子，当你要找袜子时，都不需要看它们。你只需查看袜子抽屉，并期望在那里找到袜子。

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

您会得到一些可以存储物品的位置(抽屉)。
您想出一些规则，告诉您每个物品属于哪个位置(抽屉)。
当您需要找到某些东西时，您使用该规则确定要查找哪个抽屉。

这种系统的优点是，假设您的规则不太复杂并且您拥有适当数量的抽屉，您可以通过简单地在正确的位置查找来快速找到您要找的东西。

当你整理衣服时，你可能会使用类似于“袜子放在左上抽屉，衬衫放在大中间抽屉”这样的“规则”。然而，当你存储更抽象的数据时，我们使用称为哈希函数的东西来为我们完成此操作。

理解哈希函数的一种合理方式是将其视为黑匣子。你将数据放入其中一个端口，然后另一个端口输出一个称为哈希码的数字。示意图如下：

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

所有哈希函数都是确定性的：如果您多次将相同的数据输入到函数中，您将始终在另一侧得到相同的值。而且，一个好的哈希函数应该看起来更或多或少是随机的：对输入数据进行微小更改应该会产生截然不同的哈希码。例如，字符串"pudu"和字符串"kudu"的哈希码很可能彼此非常不同。（当然，它们可能是相同的。毕竟，如果哈希函数的输出应该看起来更或多或少是随机的，那么我们有可能会两次获得相同的哈希码。）

那么，如何构建哈希函数呢？暂时来说，“体面的人不应该过多考虑这个问题。”数学家已经找出了更好和更差的设计哈希函数的方法，但对于我们的目的，我们不需要过多担心内部情况。只需要将哈希函数视为一个函数即可。

确定性的（相同的输入会得到相同的输出），但是
看起来随机（很难预测给定另一个哈希码的哈希码）。

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

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

这样做的好处是什么？嗯，假设我们有大量的桶，我们期望大多数桶里面没有太多的东西。毕竟，我们的哈希函数看起来有点像具有随机输出，因此项目在所有桶中分布得比较均匀。实际上，如果我们形式化“我们的哈希函数看起来有点随机”的概念，我们可以证明每个桶中预期的项目数量是总项目数与总桶数之比。因此，我们可以在不必做太多工作的情况下找到要查找的项目。

细节

解释“哈希表”如何工作有点棘手，因为有许多种类的哈希表。下一节将讨论所有哈希表共有的一些常见实现细节，以及不同风格的哈希表的一些具体细节。

一个首要的问题是如何将哈希码转换为表格槽位索引。在上面的讨论中，我只是说“使用哈希码作为索引”，但这实际上并不是一个很好的想法。在大多数编程语言中，哈希码会变成32位或64位整数，你不能直接使用它们作为桶索引。相反，一种常见的策略是制作一个大小为m的桶数组，计算您的项目的（完整的32位或64位）哈希码，然后对表的大小取模，以获得0到m-1之间的索引，包括m-1。在这里使用模数运算很好，因为它速度还可以，并且可以很好地将哈希码的全部范围分布到较小的范围内。

（有时会看到位运算符在这里使用。如果您的表的大小是2的幂，比如2的k次方，则计算哈希码的按位AND，然后umber 2的k次方-1等同于计算模数，并且速度要快得多。）

下一个问题是如何选择正确的桶数。如果选择太多的桶，那么大多数桶将为空或只有少量元素（对于速度很好-每个桶只需检查几个项目），但您将仅仅为了存储桶而使用大量空间（虽然也许您负担得起）。同样，反之亦然-如果桶太少，则平均每个桶会有更多的元素，使查找时间更长，但您将使用更少的内存。

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

哈希策略

到目前为止，我们一直在谈论链接哈希，这是构建哈希表的许多不同策略之一。作为提醒，链接哈希有点像衣柜 - 每个桶（抽屉）可以容纳多个项目，当您进行查找时，需要检查所有这些项目。

然而，这并非构建哈希表的唯一方法。还有另一种使用名为开放地址的策略的哈希表家族。开放地址背后的基本思想是存储一个插槽数组，每个插槽可以是空的或者恰好包含一个项。

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

线性探测是构建哈希表的一种令人惊讶的快速方法。CPU缓存被优化为引用局部性，因此相邻内存位置的内存查找往往比散布位置的内存查找快得多。由于线性探测插入或删除通过命中某个数组槽然后向前线性行走来工作，所以它导致缓存未命中较少，最终比理论预测要快得多。（而且恰好情况是理论预测它将非常快！）

另一种近期变得流行的策略是布谷鸟哈希。我认为布谷鸟哈希就像哈希表中的“冰雪奇缘”。我们不再使用一个哈希表和一个哈希函数，而是使用两个哈希表和两个哈希函数。每个项目只能在两个位置中的一个 - 要么在第一个哈希函数给出的第一个表中的位置，要么在第二个哈希函数给出的第二个表中的位置。这意味着查找是最坏情况下高效的，因为您只需要检查两个位置以查看某些内容是否在表中。

插入Cuckoo哈希使用不同的策略。我们开始查看可能保存该项的两个插槽是否有空位。如果有，太好了！我们只需将该项放在那里。但是，如果这样做不起作用，我们就选择一个插槽，将该项放在那里，并踢出原来在那里的项。该项必须去某个地方，因此我们尝试将其放在另一个表中的适当插槽中。如果可以，太好了！如果不行，我们会从那个表中踢出一个项，并尝试将其插入另一个表中。这个过程一直持续到一切都平息下来，或者我们发现自己陷入了循环。(后一种情况很少见，如果发生了，我们有很多选择，比如“将其放在辅助哈希表中”或“选择新的哈希函数并重建表。”)

有许多改进可用于Cuckoo哈希，例如使用多个表，让每个插槽容纳多个项，以及制作一个“储藏室”，用于存放无法适应其他位置的项，这是一个活跃的研究领域！

接下来介绍混合方法。Hopscotch hashing是开放地址和链式哈希的混合体，可以看作是将链式哈希表中每个桶中的每个项存储在靠近该项所需位置的插槽中。这种策略与多线程兼容。Swiss table利用一些处理器可以在单个指令中并行执行多个操作的事实来加速线性探测表。Extendible hashing专为数据库和文件系统设计，使用trie和链式哈希表的混合形式，在单独的存储桶被加载时动态增加桶大小。Robin Hood hashing是线性探测的一种变体，其中插入后可以移动项以减少每个元素与原始位置的距离方差。

哈希表是如何工作的？

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

哈希表如何将键与值关联

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

关于哈希函数的几句话

强哈希...

弱但常用的哈希函数...

基本思想

更多阅读