哈希表如何工作？
我正在寻找一个哈希表如何工作的解释 – 用简单的英语为我这样的傻瓜！
例如，我知道它需要的关键，计算散列（我正在寻找一个解释如何），然后执行某种模数来找出它存储在数组中的位置，但这是我的知识停止。
任何人都可以澄清这个过程吗？
编辑：我没有具体询问如何计算哈希代码，而是一个哈希表如何工作的一般概述。
这是一个外行人的解释。
假设你想填满一个图书馆，而不是把它们放在那里，但是你希望能够在你需要的时候再次find它们。
所以，你决定，如果想读书的人知道书的标题和确切的标题，那就只需要这样做。 有了这个头衔，这个人在图书pipe理员的帮助下，应该能够方便快捷地find这本书。
那么，你怎么能这样做呢？ 那么显然你可以保留一些你放置每本书的列表，但是你有和search库一样的问题，你需要search列表。 当然，列表会更小，更容易search，但是您仍然不希望从库（或列表）的一端顺序search到另一端。
你想要的东西，与书的标题，可以给你一次正确的位置，所以你所要做的只是漫步到右边的书架，拿起书。
但是，怎么做呢？ 那么，当你填满图书馆，并在你填满图书馆的时候，有一些预先考虑的事情。
而不是刚刚开始填满图书馆从一端到另一端，你devise一个聪明的小方法。 你拿这本书的标题，通过一个小的计算机程序运行它，在该书架上吐出一个书架号和一个插槽号。 这是你放置这本书的地方。
这个程序的美妙之处在于，当一个人回来阅读这本书的时候，你再次通过这个程序提供这个标题，并且找回原来给出的相同的货架号和槽号，这是书的位置。
正如其他人已经提到的那样，这个程序被称为散列algorithm或者散列计算，通常是通过把数据送入它（这里是书名）并且从中计算出一个数字。
为了简单起见，假设它只是将每个字母和符号转换成一个数字并将它们总和起来。 实际上，这比现在复杂得多，但现在就让我们暂时搁置吧。
这种algorithm的优点在于，如果您一次又一次地input相同的input，则每次都会一直保持同样的数字。
好吧，这基本上是一个哈希表如何工作。
技术的东西如下。
首先是数字的大小。 通常，这种散列algorithm的输出是在一个很大的范围内，通常比你在表中的空间大得多。 例如，假设图书馆里有一百万本书的空间。 哈希计算的结果可能在0到10亿的范围内，这个数字要高得多。
那么我们该怎么办？ 我们使用一种叫做模数计算的方法，基本上说，如果你计算出你想要的数字（即十亿个数字），但希望保持在一个更小的范围内，那么每当你达到这个较小范围的极限， 0，但是你必须跟踪你到达的大序列有多远。
假定散列algorithm的输出在0到20的范围内，并且从特定标题获得值17。 如果图书馆的大小只有7本书，你就算1,2,3,4,5,6，当你到了7时，你从0开始。因为我们需要计数17次，所以我们有1， 1,2,3,4,5,6,0,1,2,3,4,5,6,0,1,2,3，最终数为3。
当然模数计算不是这样做的，它是用除法和余数完成的。 17除以7的余数是3（7在14中7次2次，17和14之间的差值是3）。
因此，你把这本书放在3号插槽。
这导致了下一个问题。 碰撞。 由于algorithm没有办法将书本分隔开来，所以它们完全填满了图书馆（或者如果你愿意的话），它总是会计算一个以前使用过的数字。 从图书馆的意义上讲，当你到书架和插槽号码，你希望把一本书，那里已经有一本书。
存在各种冲突处理方法，包括将数据运行到另一个计算中以获得表格中的另一个点（ 双重散列 ），或者只是简单地find接近给定的空间（即紧接前一本书的假设时隙也被称为线性探测 ）。 这意味着当你试图在后面find这本书的时候，你有一些挖掘的工作要做，但是它比简单地从图书馆的一端开始还要好。
最后，在某种程度上，你可能想把更多的书放进图书馆，而不是图书馆允许的。 换句话说，你需要build立一个更大的图书馆。 由于图书馆中的确切位置是使用图书馆的确切大小和当前的大小计算的，因此如果调整图书馆的大小，您可能最终不得不为所有图书find新的位置，已经改变。
我希望这个解释比桶和function更简单一点:)
用法和Lingo：
- 哈希表用于快速存储和检索数据（或logging）。
- logging使用散列键存储在桶中
- 散列密钥是通过对logging中包含的选定值应用散列algorithm来计算的。 这个select的值必须是所有logging的共同价值。
- 每个桶可以有多个按特定顺序组织的logging。
真实世界的例子：
哈希公司成立于1803年，缺乏计算机技术，共有300个档案柜，为约3万名客户保存详细信息（logging）。 每个文件夹都清楚地标识了它的唯一编号，从0到299。
当时的档案pipe理员不得不快速提取和存储工作人员的客户logging。 工作人员已经决定使用哈希方法来存储和检索logging会更有效率。
要提交客户logging，提交文员将使用该文件夹上的唯一客户号码。 使用这个客户端号码，他们会调整散列键 300，以便识别它所在的文件柜。当他们打开文件柜时，他们会发现它包含许多按客户端编号sorting的文件夹。 确定了正确的位置之后，他们只需将其滑入。
为了检索客户logging，提交文件的工作人员将在一张纸上得到一个客户号码。 使用这个唯一的客户端号码，他们将调整它300（ 哈希键 ），以确定哪个文件柜有客户端文件夹。 当他们打开文件柜时，他们会发现它包含许多按客户编号sorting的文件夹。 searchlogging，他们会很快find客户端文件夹，并检索它。
在我们现实世界的例子中，我们的水桶是文件柜 ，我们的logging是文件夹 。
一个重要的事情要记住的是，电脑（和他们的algorithm）处理数字比string更好。 因此，使用索引访问大型数组比访问顺序要快得多。
正如Simon提到的我认为非常重要的一点是，哈希部分是将一个大的空间（任意长度，通常是string等）转换成一个小的空间（已知大小，通常是数字）来索引。 这要记住非常重要！
所以在上面的例子中，30,000个可能的客户端被映射到一个更小的空间。
其主要思想是将整个数据集分成不同的部分，以加快通常耗时的实际search。 在我们上面的例子中，300个文件柜中的每一个（统计上）将包含大约100个logging。 search（不pipe顺序）通过100条logging要比处理30,000个要快得多。
你可能已经注意到有些实际上已经这样做了。 但是，不是devise一个哈希方法来生成一个哈希键，他们将在大多数情况下简单地使用姓氏的第一个字母。 因此，如果您有26个文件柜，每个文件柜都包含一个从A到Z的信件，那么您理论上只是对您的数据进行分段，并增强了存档和检索过程。
希望这可以帮助，
Jeach！
原来这是一个相当深的理论领域，但基本的轮廓很简单。
从本质上讲，哈希函数只是一个从一个空间（比如说任意长度的string）中取东西的函数，并将它们映射到一个对索引有用的空间（无符号整数）。
如果你只有很小的空间来散列，那么你可能会把这些东西解释为整数，而你完成了（例如4字节的string）
但是，通常情况下，你有更大的空间。 如果你所允许的东西的空间大于你用来索引的东西的空间（你的uint32或其他东西），那么你不可能为每个东西都有唯一的值。 当两个或两个以上的东西哈希到相同的结果，你将不得不以适当的方式处理冗余（这通常被称为碰撞，而你如何处理或不取决于你是什么使用散列）。
这意味着你希望它不可能有相同的结果，你可能也会真的喜欢哈希函数是快速的。
平衡这两个属性（以及其他一些属性）让很多人忙碌起来！
在实践中，你通常应该能够find一个已知对你的应用程序很好的function并使用它。
现在把这个工作作为一个哈希表：想象一下，你不关心内存使用情况。 然后你可以创build一个数组，只要你的索引集（例如所有uint32的）。 当你添加一些东西到表中时，你把它作为关键字来查看那个索引处的数组。 如果那里什么都没有，那就把你的价值放在那里。 如果那里已经有东西了，你可以把这个新条目添加到这个地址的一个列表中，并且有足够的信息（你原来的关键字或者其他聪明的东西）来find哪个条目实际上属于哪个关键字。
所以当你走了很长一段时间，你的散列表（数组）中的每个条目都是空的，或者包含一个条目或一个条目列表。 检索是一个简单的索引到数组，并返回值，或走值的列表，并返回正确的。
当然，在实践中，你通常不能这样做，这浪费了太多的记忆。 所以你根据一个稀疏的数组（其中唯一的条目是你实际使用的，其他的一切都隐式为空）做一切事情。
有很多scheme和技巧可以使这项工作更好，但这是基础知识。
你们非常接近解释这一点，但错过了一些事情。 哈希表只是一个数组。 arrays本身将包含每个插槽中的东西。 至less你会存储散列值或值本身在这个槽中。 除此之外，您还可以存储在此插槽上发生碰撞的链接/链接值列表，也可以使用开放寻址方法。 您还可以存储一个指针或指针，指向您想要从该插槽中检索的其他数据。
值得注意的是，散列值本身通常不会指示放置值的位置。 例如，散列值可能是一个负整数值。 显然负数不能指向数组的位置。 另外，散列值往往会比可用的插槽大很多倍。 因此，散列表本身需要执行另一个计算来确定值应该进入哪个时隙。 这是通过模数运算完成的，如：
uint slotIndex = hashValue % hashTableSize;
这个值是该值将进入的槽。 在开放寻址中，如果插槽已经被另一个散列值和/或其他数据填充，模数运算将再次运行以查找下一个插槽：
slotIndex = (remainder + 1) % hashTableSize;
我想可能还有其他更高级的确定槽位索引的方法，但是这是我见过的常见的方法…会对其他performance更好的其他方法感兴趣。
使用模数方法，如果有一个表格大小为1000，那么介于1和1000之间的任何散列值将进入相应的插槽。 任何负值和大于1000的任何值都可能会碰撞槽值。 发生这种情况的可能性取决于你的散列方法，以及你添加到散列表的总数。 一般来说，最好的做法是制作散列表的大小，使得添加到其中的值的总数仅等于其大小的大约70％。 如果你的散列函数在分布上做的很好，你通常会遇到很less或没有桶/槽冲突，并且对于查找和写入操作来说，它的执行速度非常快。 如果事先不知道要添加的值的总数，则可以使用任何方法做出一个好的猜测，然后一旦添加到元素的元素的数量达到容量的70％，就调整你的hashtable的大小。
我希望这有助于。
PS – 在C＃中， GetHashCode()方法非常慢，在我testing过的很多条件下会导致实际的值冲突。 为了一些真正的乐趣，build立你自己的散列函数，并尝试让它永远不会碰撞你正在散列的特定数据，运行速度比GetHashCode快，并且分布相当均匀。 我已经使用long来代替int大小的hashcode值，并且在散列表中有3个32位的哈希值，它们的碰撞效果非常好。 不幸的是，我不能分享代码，因为它属于我的雇主…但我可以透露它是可能的某些数据域。 当你可以做到这一点，散列表非常快。 🙂
很多的答案，但没有一个是非常可视的 ，哈希表可以很容易地“点击”时可视化。
哈希表通常以链表forms实现。 如果我们想象一个存储人们姓名的表格，那么经过几次插入之后，它可能会被放置在内存中，其中()是包含文本哈希值的数字。
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]），但偶尔会因为散列值是相同的（例如上面的散列42所示的"fred"和"jane"）- 大多数散列表处理冲突 – 性能略有下降，但没有function混淆 – 通过比较被查找或插入的密钥的全部值（在这里是文本）到已经在散列存储的链表中的每个密钥
如果表大小增长，如上实现的哈希表往往会调整自己的大小（即创build一个更大的桶arrays，创build新的/更新的链接列表，从删除旧的数组），以保持元素的比例桶（又名负载因子 ）在0.5到1.0的范围内。 具有加载因子1和密码强度散列函数，36.8％的桶将倾向于空，另外36.8％具有一个元素，两个元素18.4％，三个元素6.1％，四个元素1.5％，三个五个等等。 – 列表长度平均 2.0个元素，不pipe表中有多less元素，这就是为什么我们说查找/插入/擦除是O（1）个常量时间操作。
（注：不是所有的哈希表都使用链表，但是大多数通用的哈希表作为封闭哈希（又名开放寻址），特别是在支持擦除操作的情况下，具有不太稳定的性能特性，容易碰撞的键/散列函数）。
几个关于散列函数的文字
通用的，最坏情况的最小化碰撞最小化散列函数的工作是随机地散列在散列表桶周围的密钥，同时总是为相同的密钥产生相同的散列函数。 即使在密钥的任何地方改变一个位，理想情况下都会随机地翻转生成的哈希值中大约一半的位。
这通常是math计算太复杂，我不能苟同。 我会提到一种易于理解的方式 – 不是最具可扩展性或者caching友好的，但本质上是优雅的（就像使用一次性密钥encryption一样！） – 我认为这有助于推动上面提到的理想品质。 假设你正在哈希64位double s–你可以创build8个256个随机数的表，然后用double的内存表示的每个8-bit / 1-byte slice索引到一个不同的表中，把你的随机数抬头。 通过这种方法，很容易看出在double结果中的任何位置发生变化的结果是在一个表格中查find不同的随机数字，并且完全不相关的最终值。
尽pipe如此，许多库的哈希函数通过不变的方式传递整数，这在最糟糕的情况下是非常容易碰撞的，但是希望在整数密钥相当普遍的情况下，这些整数密钥往往会增加，他们会映射到连续的桶中，比随机哈希离散的36.8％空，因此具有比随机映射所实现的更less的碰撞和更less的更长的碰撞元素的链表。 节省生成强大散列所花费的时间也是非常好的。 当密钥不能很好地递增时，希望是足够随机的，他们不需要一个强大的哈希函数来将它们的位置完全随机化到桶中。
那么，这比哈希表的解释没有那么有趣和重要，但希望它有助于某人….
这是我的理解是如何工作的：
下面是一个例子：将整个表格作为一系列桶来描绘。 假设你有一个字母数字散列码的实现，并且每个字母的字母都有一个桶。 这个实现将哈希码以特定字母开始的每个项目放在相应的桶中。
假设您有200个对象，但其中只有15个哈希代码以字母“B”开头。 哈希表只需要查找并search“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）。
当我们的内部arrays变得太满，也许大概有85％的容量，我们可以调整内部arrays的大小，并将旧arrays中的所有项目移动到新arrays中。
比这更简单。
哈希表不过是一个包含键/值对的向量的数组（通常是稀疏的 ）。 此数组的最大大小通常小于存储在散列表中的数据types的可能值集合中的项目数。
散列algorithm用于根据将存储在数组中的项目的值生成该数组的索引。
这是存储数组中键/值对的向量的地方。因为可以是数组中的索引的值的集合通常小于该types可能具有的所有可能值的数目，所以有可能您的哈希algorithm将为两个单独的密钥生成相同的值。 一个好的散列algorithm将尽可能地防止这种情况（这就是为什么它通常被归为types的原因，因为它具有一般散列algorithm不可能知道的特定信息），但是不可能防止。
正因为如此，你可以有多个键将生成相同的哈希码。 当这种情况发生时，向量中的项被迭代，直接比较向量中的键和被查找的键。 如果find了，那么很好，并且与键相关的值被返回，否则没有返回。
你拿了一堆东西，还有一个数组。
对于每一件事，你都为它构成一个索引，称为哈希。 散列的重要之处在于“分散”了很多; 你不希望两个类似的东西有相似的哈希值。
你把你的东西放在哈希表示的位置上。 不止一件事情可以结束于给定的散列，所以你把它们存储在数组或其他适当的东西里，我们通常把它称为一个桶。
当你在散列中查找事物时，你需要经过相同的步骤，计算散列值，然后查看该位置存在的内容，并检查它是否是你要查找的内容。
当你的哈希algorithm运行良好，你的数组足够大时，在数组中任何特定的索引最多只会有几件事情，所以你不必看太多。
对于奖励积分，使得当你的哈希表被访问时，它将发现的东西（如果有的话）移动到桶的开始，所以下一次是检查的第一件事情。
如何计算散列通常不依赖于散列表，而是依赖于添加到它的项目。 在.net和Java之类的框架/基类库中，每个对象都有一个GetHashCode（）（或类似的）方法返回这个对象的哈希码。 理想的哈希码algorithm和确切的实现取决于对象中表示的数据。
到目前为止所有的答案都是好的，并在哈希表如何工作的不同方面。 这是一个简单的例子，可能会有所帮助。 比方说，我们要存储一些与小写字母string项目作为一个关键。
正如simon所解释的那样，散列函数用于从大空间映射到小空间。 对于我们的例子，一个简单而朴实的哈希函数实现可以将string的第一个字母，并映射到一个整数，所以“鳄鱼”的哈希码为0，“蜜蜂”哈希码为1，斑马“将是25等。
接下来我们有一个26个桶的数组（可以是Java中的ArrayLists），并且我们把这个项目放在与我们的密钥的哈希码匹配的桶中。 如果我们有多个项目的密钥以相同的字母开始，那么它们将具有相同的哈希码，所以所有的哈希码都会在桶中进行search，因此必须在该桶中进行线性searchfind一个特定的项目。
在我们的例子中，如果我们只有几十个键字跨越的项目，它将工作得很好。 但是，如果我们有一百万个项目，或者所有的键都以'a'或'b'开头，那么我们的散列表就不是理想的。 为了获得更好的性能，我们需要一个不同的哈希函数和/或更多的桶。
这是另一种看待它的方法。
我假设你理解数组A的概念。这是支持索引操作的事情，在这里你可以一步到达第I个元素A [I]，不pipeA有多大。
因此，例如，如果要存储关于所有碰巧具有不同年龄段的人的信息，一个简单的方法就是创build一个足够大的数组，并将每个人的年龄用作数组中的索引。 Thay的方式，你可以一步到达任何人的信息。
但是，当然也可以有一个以上的同龄人，所以你在每个条目中列出的是所有那个年龄段的人。 所以你可以一步到达一个人的信息，再加上那个列表中的一些search（称为“桶”）。 如果有这么多的人，水桶变大，它只会变慢。 那么你需要一个更大的数组，以及其他方式来获得更多关于这个人的身份信息，比如他们姓的前几个字母，而不是使用年龄。
这是基本的想法。 可以使用产生良好价值分布的人的任何function，而不是使用年龄。 这是散列函数。 就像你可以把每个人的名字的ASCII码的三分之一一样，按照一定的顺序进行编码。 重要的是你不想让太多的人对同一个桶进行散列，因为速度依赖于桶的小。
散列表完全是基于这样的事实，即实际计算遵循随机访问机器模型，即在存储器中的任何地址处的值可以在O（1）时间或恒定时间被访问。
所以，如果我有一个键的全部（我可以在应用程序中使用的所有可能的键的集合，例如学生的滚动号码，如果它是4位数，那么这个宇宙是从1到9999的一组数字），以及方式映射到一个有限的数量的大小我可以在我的系统中分配内存，理论上我的哈希表已经准备就绪。
一般来说，在应用程序中，密钥的Universe的大小要比我要添加到散列表的元素的数量要大（我不想浪费1GB的内存来散列，比如10000或100000的整数值，因为它们是32在二进制reprsentaion位长）。 所以，我们使用这个哈希。 这是一种混合式的“math”运算，它将我的大宇宙映射到一小群我可以容纳的记忆中。 在实际情况中，散列表的空间往往与（元素个数×每个元素的大小）相同的“order”（big-O），所以我们不会浪费太多内存。
现在，映射到一个小集合的大集合映射必须是多对一的。 所以，不同的键将被分配相同的空间（??不公平）。 有几种方法可以解决这个问题，我只知道其中的两个：
- 使用要分配给该值的空间作为链接列表的引用。 这个链接列表将存储一个或多个值，它们位于同一个槽中，在多个到一个映射中。 链表还包含帮助search的人的键。 就像同一间公寓里的很多人一样，当送货员来的时候，他走进房间，专门为那个人问道。
- 在数组中使用双散列函数，每次给出相同的值序列而不是单个值。 当我去存储一个值时，我会看到所需的内存位置是空闲的还是被占用的。 如果它是免费的，我可以在那里存储我的价值，如果它被占用，我从序列中获取下一个值，等等，直到我find一个空闲的位置，然后将我的价值存储在那里。 当search或检索值时，我按照序列给出的相同path返回，并在每个位置询问vaue，直到find它或search数组中的所有可能位置。
CLRSalgorithm介绍对这个话题提供了非常好的见解。
对于那些寻找编程说法的人来说，这是它的工作原理。 高级哈希表的内部实现对于存储分配/重新分配和search有许多复杂和优化，但最高级的思想将非常相似。
(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()是所有唯一性魔术必须发生的哈希函数。
经验法则是： 对于要插入的给定值，存储区必须是唯一的，并且可以从应该存储的值派生。
桶是存储值的任何空间 – 在这里我已经把它保存为一个数组索引，但它也可能是一个内存位置。
