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

我的理解是这样的:

这里有一个例子:把整个表想象成一系列的桶。假设您有一个带有字母-数字哈希码的实现，并且每个字母都有一个存储桶。该实现将哈希码以特定字母开头的每个项放入相应的bucket中。

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

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

其实比这更简单。

哈希表不过是一个包含键/值对的向量数组(通常是稀疏的 one)。此数组的最大大小通常小于哈希表中存储的数据类型的可能值集中的项数。

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

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

因此，您可以使用多个键来生成相同的散列代码。当这种情况发生时，将遍历向量中的项，并在向量中的键和正在查找的键之间进行直接比较。如果找到，则返回与该键关联的值，否则不返回任何值。

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

本质上，哈希函数只是一个函数，它从一个空间(比如任意长度的字符串)获取内容，并将它们映射到一个用于索引的空间(比如无符号整数)。

如果你只有一个小空间的东西来散列，你可能只需要把这些东西解释为整数，你就完成了(例如4字节字符串)

不过，通常情况下，你的空间要大得多。如果你允许作为键的空间大于你用于索引的空间(你的uint32或其他)，那么你不可能为每个键都有唯一的值。当两个或多个东西散列到相同的结果时，您必须以适当的方式处理冗余(这通常被称为冲突，如何处理它或不处理它将略微取决于您使用散列的目的)。

这意味着你不希望得到相同的结果，你也可能希望哈希函数是快速的。

平衡这两个属性(以及其他一些属性)让许多人忙得不可开交!

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

现在让它作为哈希表工作:假设您不关心内存使用情况。然后你可以创建一个和你的索引集一样长的数组(例如，所有的uint32)。当你向表中添加一些东西时，你对它的键进行哈希并在索引处查看数组。如果那里什么都没有，你就把你的价值放在那里。如果那里已经有一些内容，则将这个新条目添加到该地址的内容列表中，并添加足够的信息(您的原始密钥或其他聪明的信息)，以查找哪个条目实际上属于哪个密钥。

因此，随着时间的推移，哈希表(数组)中的每个条目要么是空的，要么包含一个条目，要么包含一个条目列表。检索很简单，就像在数组中建立索引，然后返回值，或者遍历值列表并返回正确的值。

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

有很多方案和技巧可以让它更好地工作，但这是最基本的。

你取一堆东西，和一个数组。

对于每一个东西，你为它建立一个索引，称为哈希。关于哈希的重要事情是它“分散”了很多;你不希望两个相似的东西有相似的哈希值。

你把东西放到数组中哈希值表示的位置。在一个给定的哈希中可以有多个对象，所以你可以将这些对象存储在数组或其他合适的东西中，我们通常称之为bucket。

当你在哈希中查找东西时，你会经历相同的步骤，计算哈希值，然后查看那个位置的bucket中有什么，并检查它是否是你要寻找的东西。

当你的哈希工作得很好并且你的数组足够大时，在数组的任何特定下标处最多只会有很少的东西，所以你不需要看太多。

额外的好处是，当你的哈希表被访问时，它会把找到的东西(如果有的话)移动到桶的开头，这样下次它就会是第一个被检查的东西。

这是一个外行的解释。

让我们假设你想要用书填满一个图书馆，而不仅仅是把它们塞进去，而且你希望在你需要它们的时候能够很容易地再次找到它们。

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

那么，你该怎么做呢?当然，你可以列出你把每本书放在哪里的列表，但是你会遇到和搜索图书馆一样的问题，你需要搜索列表。当然，列表会更小，更容易搜索，但您仍然不希望从库(或列表)的一端到另一端依次搜索。

你想要的东西，有了书名，就能立刻给你正确的位置，所以你所要做的就是漫步到正确的书架上，拿起书。

但这怎么能做到呢?嗯，当你填满图书馆的时候要有一点先见之明，当你填满图书馆的时候要做很多工作。

你设计了一个聪明的小方法，而不是开始从一端到另一端填满这个库。你拿着书名，在一个小的计算机程序中运行，它会显示出书架的编号和书架上的槽号。这是你放书的地方。

这个程序的美妙之处在于，稍后，当一个人回来阅读这本书时，您再次通过程序输入标题，并获得与最初给您的相同的书架编号和插槽编号，这就是书的位置。

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

为了简单起见，我们假设它只是将每个字母和符号转换为一个数字，并将它们全部相加。实际上，它要比这复杂得多，但现在让我们先把它放在这里。

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

这就是哈希表的基本工作原理。

接下来是技术方面的内容。

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

那么，我们该怎么办呢?我们使用所谓的模量计算，它基本上是说，如果你数到你想要的数字(即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(17除7得14,17和14之差是3)。

因此，你把书放在3号槽里。

这就导致了下一个问题。碰撞。由于该算法无法将图书间隔开来以使它们完全填满库(或者填满哈希表)，因此它最终总是会计算一个以前使用过的数字。在图书馆的意义上，当你到达书架和你想放一本书的槽号时，那里已经有一本书了。

存在各种冲突处理方法，包括将数据运行到另一个计算中以获得表中的另一个位置(双散列)，或者简单地找到一个靠近给定位置的空间(即，就在前一本书旁边，假设插槽可用，也称为线性探测)。这意味着当你稍后试图找到这本书时，你需要做一些挖掘工作，但这仍然比简单地从图书馆的一端开始要好。

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

我希望这个解释比桶和函数更接地气一点:)

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

正如simon所解释的，哈希函数用于从大空间映射到小空间。对于我们的例子，一个简单的哈希函数实现可以取字符串的第一个字母，并将其映射为一个整数，因此“短吻鳄”的哈希代码为0，“蜜蜂”的哈希代码为1，“斑马”的哈希代码为25，等等。

接下来，我们有一个包含26个存储桶的数组(在Java中可以是数组列表)，我们将项放入与键的哈希码匹配的存储桶中。如果我们有不止一个元素键以相同字母开头，它们就会有相同的哈希码，所以它们都会进入存储桶中寻找那个哈希码所以必须在存储桶中进行线性搜索才能找到一个特定的元素。

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

用法和行话:

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

现实世界的例子:

散列,有限公司成立于1803年，当时没有任何计算机技术，只有300个文件柜来保存大约3万名客户的详细信息(记录)。每个文件夹都清楚地标识其客户端编号，从0到29,999的唯一编号。

当时的档案管理员必须迅速为工作人员获取和存储客户记录。工作人员决定使用哈希方法来存储和检索他们的记录会更有效。

要归档客户记录，档案管理员将使用写在文件夹上的唯一客户编号。使用这个客户端编号，他们将散列键调整300，以识别包含它的文件柜。当他们打开文件柜时，他们会发现里面有很多按客户号排序的文件夹。在确定正确的位置后，他们会简单地把它塞进去。

要检索客户记录，档案管理员将在一张纸上获得客户号码。使用这个唯一的客户编号(散列键)，他们将调整它300，以确定哪个文件柜有客户文件夹。当他们打开文件柜时，他们会发现里面有很多按客户号排序的文件夹。通过搜索记录，他们可以快速找到客户端文件夹并检索它。

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

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

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

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

这样做的主要思想是将整个数据集划分为几个部分，以加快实际搜索的速度，而实际搜索通常是耗时的。在我们上面的例子中，300个文件柜中的每个(统计上)将包含大约100条记录。搜索100条记录(不管顺序)要比处理3万条记录快得多。

你可能已经注意到有些人已经这样做了。但是，在大多数情况下，他们只是使用姓氏的第一个字母，而不是设计一个哈希方法来生成哈希键。因此，如果您有26个文件柜，每个文件柜都包含从a到Z的一个字母，理论上您只是将数据分割并增强了归档和检索过程。

希望这能有所帮助，

Jeach !

简短而甜蜜:

哈希表包含一个数组，我们称它为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%左右的容量，我们可以调整内部数组的大小，并将所有项目从旧数组移动到新数组中。

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

我假设你理解数组A的概念，它支持索引操作，你可以一步找到第I个元素，A[I]，不管A有多大。

因此，例如，如果您想存储一组恰好年龄不同的人的信息，一个简单的方法是有一个足够大的数组，并使用每个人的年龄作为数组的索引。这样，你就可以一步获取任何人的信息。

但是当然可能有不止一个相同年龄的人，所以你在每个元素的数组中放入的是这个年龄的所有人的列表。这样你就可以一步得到一个人的信息，再加上在列表(称为“bucket”)中进行一点点搜索。只有当人多到桶变大时，它才会变慢。然后你需要一个更大的数组，以及其他一些方法来获得关于这个人的更多识别信息，比如他们姓氏的前几个字母，而不是使用年龄。

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

你们已经很接近完整地解释了这个问题，但是遗漏了一些东西。哈希表只是一个数组。数组本身将在每个槽中包含一些内容。至少要将哈希值或值本身存储在这个插槽中。除此之外，您还可以存储在此插槽上碰撞的值的链接/链表，或者您可以使用开放寻址方法。您还可以存储一个或多个指针，这些指针指向您希望从该槽中检索的其他数据。

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

uint slotIndex = hashValue % hashTableSize;

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

slotIndex = (remainder + 1) % hashTableSize;

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

使用模量方法，如果你有一个大小为1000的表，任何在1到1000之间的哈希值都将进入相应的插槽。任何负值和任何大于1000的值都可能是槽值冲突。发生这种情况的几率取决于你的哈希方法，以及你向哈希表中添加了多少项。一般来说，最佳实践是将哈希表的大小设置为添加到其中的值的总数仅等于其大小的70%左右。如果你的哈希函数能很好地完成均匀分布，你通常会遇到很少甚至没有桶/槽冲突，并且它会非常快地执行查找和写入操作。如果预先不知道要添加的值的总数，请使用任何方法进行良好的估计，然后在添加到哈希表中的元素数量达到容量的70%时调整哈希表的大小。

我希望这对你有所帮助。

在c#中，GetHashCode()方法非常慢，并且在我测试的许多条件下会导致实际的值冲突。为了获得一些真正的乐趣，构建你自己的哈希函数，并尝试让它永远不会与你正在哈希的特定数据发生冲突，运行速度比GetHashCode快，并且具有相当均匀的分布。我使用了long而不是int size的hashcode值，它在哈希表中工作得很好，达到3200万个完整的哈希值，并且没有冲突。不幸的是，我不能分享代码，因为它属于我的雇主…但我可以告诉你，在某些数据领域，这是可能的。当你可以做到这一点，哈希表是非常快的。：）

有很多答案，但没有一个是非常视觉的，并且哈希表可以很容易地“点击”;当形象化。

哈希表通常实现为链表数组。如果我们想象一个存储人名的表，经过几次插入之后，它可能会被放置在内存中，其中# eyz0括起来的数字是文本/姓名的哈希值。

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]…)都被称为< >强桶< / >强，并开始一个可能为空的值(在本例中也称为元素，即人们的的名字)的链表。
• 每个值(例如:"fred"带散列42)从桶[hash % number_of_buckets]链接，例如:42 % 10 == [2];%是< em >模运算符< / em > -除以桶数的余数
• 多个数据值可能<强> < /碰撞强>在并从同一个桶链接，最常见的原因是它们的哈希值在模运算后发生碰撞(例如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%有五个等。不管表中有多少个元素，非空桶的平均链长度都是~1.58(即是否有100个元素和100个桶，还是1亿个元素和1亿个桶)，这就是为什么我们说查找/插入/擦除是< em > O < / em > (1)常量时间操作。

哈希表如何将键与值关联

当我们这样做的时候，我们使用哈希表作为关联容器 aka map，它存储的值可以被认为是由关键(名字)和一个或多个其他字段组成——令人困惑的是——价值(在我的例子中，只是年龄)。用作映射的哈希表实现称为散列映射。

这与前面的示例形成对比，在前面的示例中，我们存储了像"sue"这样的离散值，您可以把它看作是它自己的键:这种用法被称为散列集。

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

并不是所有的哈希表都使用链表(称为< em >单独链接< / em >)，但是大多数通用哈希表都使用链表，因为主要的替代方案封闭哈希(又名开放寻址)——特别是支持擦除操作——在容易发生冲突的键/哈希函数中性能不太稳定。

简单讲一下哈希函数

强大的散列…

一个通用的、最小化最坏情况碰撞的哈希函数的工作是有效地随机地在哈希表桶周围散布键，同时总是为相同的键生成相同的哈希值。理想情况下，即使在键的任何位置改变一个位，也会随机地翻转结果哈希值中的大约一半位。

这通常是由我难以理解的复杂数学编排的。我将提到一种易于理解的方法——不是最可扩展或缓存友好的方法，但本质上是优雅的(就像使用一次性的加密板!)——因为我认为它有助于说明上面提到的可取的品质。假设您正在哈希64位的doubles -您可以创建8个表，每个表有256个随机数(代码如下)，然后使用double的内存表示的每个8位/1字节切片索引到不同的表中，XORing您查找的随机数。使用这种方法，可以很容易地看到，在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]];

弱但通常快速的哈希…

许多库的哈希函数都是将整数原样传递(称为微不足道的或<强> < / >强身份哈希函数);这是上面描述的强哈希的另一个极端。在最坏的情况下，一个标识哈希很容易发生极冲突，但是我们希望在比较常见的整数键倾向于增加(可能有一些间隙)的情况下，它们将映射到连续的bucket中，留下的空比随机哈希叶(前面提到的负载因子1时约36.8%)更少，因此比随机映射实现的冲突更少，碰撞元素的链表更短。这也很好地节省了生成强哈希的时间，如果按顺序查找键，它们将在内存中附近的桶中找到，从而提高缓存命中。当键不很好地增加时，希望它们足够随机，它们不需要强大的哈希函数来完全随机地将它们放置到桶中。

哈希表完全基于这样一个事实，即实际计算遵循随机访问机模型，即内存中任何地址的值都可以在O(1)时间或常数时间内访问。

因此，如果我有一个键的宇宙(我可以在应用程序中使用的所有可能的键的集合，例如，滚动no。对于学生来说，如果它是4位，那么这个宇宙就是从1到9999的一组数字)，并且一种将它们映射到有限大小的数字集的方法可以在我的系统中分配内存，理论上我的哈希表已经准备好了。

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

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

• 将分配给该值的空间用作对链表的引用。这个链表将存储一个或多个值，这些值在多对一映射中位于同一个槽中。链表还包含键，以帮助来搜索的人。就像很多人住在同一间公寓里，当一个快递员来的时候，他会走进房间，专门找那个人。
• 在数组中使用双哈希函数，每次都给出相同的值序列，而不是单个值。当我去存储一个值时，我查看所需的内存位置是空闲的还是已占用的。如果它是空闲的，我可以把值存储在那里，如果它被占用了，我从序列中取下一个值，以此类推，直到我找到一个空闲的位置，我把值存储在那里。当搜索或检索值时，我回到序列给定的相同路径，在每个位置询问值是否存在，直到找到它或搜索数组中所有可能的位置。

CLRS的《算法导论》对这个主题提供了非常好的见解。

对于所有寻找编程用语的人，下面是它是如何工作的。高级哈希表的内部实现有许多复杂之处，并且对存储分配/释放和搜索进行了优化，但顶层的思想是非常相同的。

(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作为数组索引，但它也可能是一个内存位置。

基本思路

为什么人们要用梳妆台来存放衣服?除了看起来时髦时髦之外，它们还有一个优势，那就是每件衣服都有它应该放在的地方。如果你要找一双袜子，你只要检查袜子抽屉就行了。如果你在找一件衬衫，你会检查放衬衫的抽屉。当你在找袜子时，你有多少件衬衫或几条裤子都无关紧要，因为你不需要看它们。你只要往袜子抽屉里一看，就指望能找到袜子。

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

• 你有一些可以存储物品的位置(抽屉)。
• 你想出一些规则，告诉你每件物品属于哪个位置(抽屉)。
• 当你需要找东西时，你就用这个规则来决定要找哪个抽屉。

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

当你把衣服收起来的时候，“规则”;你可能会这样说:“袜子放在左边最上面的抽屉里，衬衫放在中间的大抽屉里，等等”。但是，当您存储更抽象的数据时，我们使用一个名为< /强> < >强哈希函数的东西来为我们做这件事。

考虑哈希函数的一种合理方式是将其视为一个黑盒。你把数据放在一边，一个名为散列码的数字从另一边出来。从示意图上看，它是这样的:

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

所有哈希函数都是< >强确定性< / >强:如果你多次将相同的数据放入函数中，你总是会从另一边得到相同的值。一个好的哈希函数应该看起来或多或少是随机的:对输入数据的微小改变应该会产生截然不同的哈希码。例如，字符串“pudu"和字符串“kudu"的哈希码很可能完全不同。(当然，也有可能它们是一样的。毕竟，如果一个哈希函数的输出看起来或多或少是随机的，我们就有可能得到两次相同的哈希码。)

如何构建哈希函数呢?现在，让我们用“正派的人不应该想太多”。数学家们已经想出了更好和更差的方法来设计哈希函数，但对于我们的目的，我们真的不需要太担心内部。把哈希函数看成是这样的函数就很好了

• 确定性的(相同的输入给出相同的输出)，但是
• 看起来是随机的(很难预测一个哈希码给出另一个)。

一旦我们有了哈希函数，我们就可以建立一个非常简单的哈希表。我们将创建一个“桶”数组;你可以把它想象成我们梳妆台里的抽屉。要在哈希表中存储一个项目，我们将计算该对象的哈希代码，并将其用作表中的索引，这类似于“选择该项目放在哪个抽屉中”。然后，我们把这个数据项放在桶内的那个索引处。如果桶是空的，那太好了!我们可以把物品放在那里。如果这个桶是满的，我们有一些选择我们可以做什么。一种简单的方法(称为< em > < >强链接哈希< /强> < / em >)是将每个桶视为一个项目列表，就像您的袜子抽屉可能存储多个袜子一样，然后将项目添加到该列表的索引处。

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

这样做有什么好处呢?假设我们有很多桶，我们会期望大多数桶里不会有太多东西。毕竟，我们的哈希函数看起来是随机输出的，所以数据项是均匀地分布在所有的存储区中。事实上，如果我们将“我们的哈希函数看起来有点随机”的概念形式化，我们可以证明，每个桶中的期望物品数量是物品总数与桶总数的比率。因此，我们不需要做太多的工作就能找到我们想要的东西。

细节

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

出现的第一个问题是如何将哈希码转换为表槽索引。在上面的讨论中，我只是说“使用哈希码作为索引”，“;但这其实不是个好主意。在大多数编程语言中，哈希码都是32位或64位整数，不能直接将它们用作bucket索引。相反，一种常见的策略是创建一个大小为m的桶数组，为您的项目计算(完整的32位或64位)哈希码，然后根据表的大小对它们进行mod，以获得0到m-1之间(包括m-1)的索引。模量在这里工作得很好，因为它相当快，并且在一个较小的范围内出色地扩展了整个哈希码范围。

(这里有时会使用位运算符。如果你的表的大小是2的幂，比如2^k，那么计算哈希码的位与，然后计算编号2^k - 1相当于计算一个模数，而且它明显更快。)

下一个问题是如何选择正确的桶数。如果您选择太多的bucket，那么大多数bucket将是空的或只有很少的元素(对速度有好处-每个bucket只需要检查一些项)，但是您将使用大量的空间来简单地存储bucket(不是很好，尽管也许您可以负担得起)。反之亦然——如果存储桶太少，那么每个存储桶平均会有更多的元素，这会使查找时间变长，但会减少内存使用量。

一个很好的折衷方法是在哈希表的生命周期内动态地改变桶的数量。哈希表的< >强负荷系数< / >强，通常表示为α，是元素数量与桶数量的比值。大多数哈希表选择一些最大负载因子。一旦负载因子超过这个限制，哈希表就会增加它的槽数(比如翻倍)，然后将旧表中的元素重新分配到新表中。这个叫做再处理。假设表中的最大负载因子是一个常数，这确保了(假设您有一个良好的哈希函数)执行查找的预期成本仍然是O(1)。插入现在有一个摊销的期望成本是O(1)，因为定期重建表的成本，就像删除的情况一样。(如果负载因子过小，删除操作同样会压缩表。)

哈希策略

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

然而，这并不是构建哈希表的唯一方法。还有另一类哈希表使用< em > < >强开放寻址< /强> < / em >策略。开放寻址的基本思想是存储一个< >强槽< / >强数组，其中每个槽可以是空的，也可以只保存一项。

在开放寻址中，当像以前一样执行插入时，将跳转到某个槽，其索引依赖于计算的哈希码。如果那个位置是空的，那就太好了!你把东西放在那里，就完成了。但如果名额已经满了怎么办?在这种情况下，您可以使用一些辅助策略来找到一个不同的空闲槽来存储项目。最常用的策略是使用< em > < >强线性探测< /强> < / em >。在线性探测中，如果您想要的槽已经满了，则只需将其移到表中的下一个槽。如果那个槽是空的，那就太好了!你可以把物品放在那里。但是如果那个槽已经满了，你就移动到表中的下一个槽，等等(如果你到达了表的末端，就回到开始)。

线性探测是一种构建哈希表的快速方法。CPU缓存针对<强>参考局部性进行了优化，因此在相邻内存位置的内存查找往往比在分散位置的内存查找快得多。由于线性探测插入或删除的工作原理是命中某个数组槽，然后线性向前移动，因此它很少会导致缓存丢失，最终比理论通常预测的要快得多。(碰巧的是，理论预测它会非常快!)

另一个最近很流行的策略是< em > <强>杜鹃散列< /强> < / em >。我喜欢把布谷鸟杂音想象成《冰雪奇缘》。哈希表。不是只有一个哈希表和一个哈希函数，而是有两个哈希表和两个哈希函数。每一项可以恰好在两个位置中的一个——它要么在由第一个哈希函数给出的第一个表中的位置，要么在由第二个哈希函数给出的第二个表中的位置。这意味着查找是最坏的高效的，因为您只需要检查两个点来查看表中是否有内容。

布谷鸟哈希中的插入使用了与以前不同的策略。我们首先查看两个可以容纳物品的槽中是否有一个是空闲的。如果是这样，那太好了!我们只是把项放在那里。但如果这不起作用，那么我们选择一个槽，把物品放在那里，然后把以前在那里的物品踢出去。这一项必须放到某个地方，所以我们试着将它放到另一个表中相应的槽中。如果有效，那太好了!如果不是，我们从那表中删除一个项，并尝试将它插入到另一个表中。这个过程会一直持续下去，直到一切都归于平静，或者我们发现自己陷入了一个循环。(后一种情况很少见，如果发生这种情况，我们有很多选项，比如“把它放在第二个哈希表中”;或者“选择新的哈希函数并重新构建表”;)

对于布谷鸟哈希有很多改进的可能，比如使用多个表，让每个槽容纳多个项目，并使“stash"它能容纳任何地方都放不下的物品，这是一个活跃的研究领域!

还有混合方法。< em > < >强跳房子散列< /强> < / em >是开放寻址和链式哈希的混合，可以认为是采用链式哈希表，将每个项目存储在每个bucket中靠近项目位置的槽中。该策略在多线程中很好地发挥作用。< em > < >强瑞士表< /强> < / em >利用了一些处理器可以用一条指令并行执行多个操作的事实来加快线性探测表的速度。< em > < >强可伸长的散列< /强> < / em >是为数据库和文件系统设计的，它混合使用了trie和链式哈希表，以便在加载单个桶时动态增加桶的大小。罗宾汉哈希是线性探测的一个变体，在这个变体中，项目被插入后可以移动，以减少每个元素可以存在的距离的差异。

进一步的阅读

有关哈希表基础知识的更多信息，请查看这些关于链式哈希的幻灯片和这些关于线性探测和罗宾汉哈希的后续幻灯片。你可以了解更多关于这里布谷鸟哈希和这里哈希函数的理论性质的信息。

直连地址表

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

然而，在实现直接地址表之前，有四个注意事项:

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

事实上，现实生活中并不是很多情况都符合上述要求，所以哈希表就可以救场了

哈希表

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

宇宙键的长度可以大于数组的长度，这意味着两个不同的键可以散列到相同的索引(称为散列碰撞)?

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

如果你仍然有兴趣知道如何从头开始实现hashmap，请阅读下面的文章

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