我正在寻找有关哈希表如何工作的解释 - 对于像我这样的傻瓜来说用简单的英语!
例如，我知道它需要 key ，计算散列(我正在寻找如何解释)，然后执行某种模以计算出它在存储值的数组中的位置，但这就是我的知识停止的地方.
谁能解释一下这个过程？
编辑:我不是专门询问散列码的计算方式，而是询问散列表如何工作的一般概述。
最佳答案
这是通俗易懂的解释。
假设您想用书籍填满图书馆，而不仅仅是将它们塞进图书馆，还想在需要时能够轻松地再次找到它们。
因此，您决定，如果想要阅读一本书的人知道这本书的书名以及要引导的确切书名，那么这就是全部。有了书名，这个人在图书管理员的帮助下应该能够轻松快速地找到这本书。
那么，你怎么能这样做呢？嗯，显然你可以保留某种类型的列表，列出每本书的放置位置，但是你会遇到与搜索图书馆相同的问题，你需要搜索列表。诚然，该列表会更小且更易于搜索，但您仍然不想从库(或列表)的一端到另一端按顺序搜索。
您想要一些带有书名的东西，可以立即为您提供正确的位置，因此您要做的就是走到正确的书架上，然后拿起书。
但是怎么做呢？好吧，当你填满图书馆时要深思熟虑，当你填满图书馆时需要做很多工作。
您不是只是开始从一端到另一端填满图书馆，而是设计了一种聪明的小方法。您获取书名，通过一个小型计算机程序运行它，该程序会在该书架上输出一个书架编号和一个插槽编号。这是你放置书的地方。
这个程序的美妙之处在于，当一个人回来读这本书时，你再次通过程序输入标题，并返回与你最初获得的相同的书架号和插槽号，这就是书所在的地方。
正如其他人已经提到的，该程序被称为散列算法或散列计算，通常通过将数据输入其中(在这种情况下是书名)并从中计算出一个数字来工作。
为简单起见，假设它只是将每个字母和符号转换为一个数字并将它们相加。实际上，它比这复杂得多，但让我们暂时搁置它。
这种算法的美妙之处在于，如果你一次又一次地向它输入相同的输入，它每次都会不断吐出相同的数字。
好的，这基本上就是哈希表的工作方式。
技术内容如下。
首先，是数字的大小。通常，这种散列算法的输出在某个大数的范围内，通常比表中的空间大得多。例如，假设我们的图书馆正好有 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 )。这意味着当您稍后尝试查找这本书时，您需要进行一些挖掘工作，但这仍然比简单地从图书馆的一端开始要好。
最后，在某些时候，您可能希望将比图书馆允许的更多的书籍放入图书馆。换句话说，您需要构建一个更大的库。由于图书馆中的确切位置是使用图书馆的确切和当前大小计算的，因此如果您调整图书馆的大小，您可能最终不得不为所有书籍找到新的位置，因为计算已完成以找到它们的位置已经改变。
我希望这个解释比桶和函数更接地气:)
关于data-structures - 哈希表是如何工作的？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/730620/