哈希表如何工作？
我正在寻找一个哈希表如何工作的解释 - 对于像我这样的傻瓜来说，简单英语！
例如，我知道它需要关键字，计算散列（我正在寻找一个解释如何），然后执行某种模数来确定它存储在数组中的位置，但这正是我知识停止的地方。
任何人都可以澄清这个过程吗？
编辑：我没有具体询问如何计算哈希码，而是总体了解哈希表的工作原理。
这是一个外行人的解释。
假设你想填充一个图书馆的书，而不是把它们放在那里，但是你希望能够在你需要时再次找到它们。
所以，你决定如果想看书的人知道书的标题和确切的标题，那就只需要这些。 有了这个头衔，这个人在图书管理员的帮助下应该能够轻松快速地找到这本书。
那么，你怎么能这样做呢？ 那么，显然你可以保留一些你放置每本书的列表，但是你有和搜索库一样的问题，你需要搜索列表。 当然，列表会更小，更容易搜索，但是您仍然不希望从库（或列表）的一端顺序搜索到另一端。
你想要的东西和书名一样，可以立刻给你正确的位置，所以你只需要走到右边的书架上去拿书。
但是，怎么做呢？ 那么，当你填满图书馆时需要一些深思熟虑，当你填满图书馆时需要做很多工作。
而不是从一端到另一端开始填满图书馆，而是设计一个聪明的小方法。 你拿这本书的标题，通过一个小型计算机程序运行它，在该书架上分出一个书架号和一个插槽号。 这是你放置这本书的地方。
这个程序的优点在于，稍后当一个人回来阅读这本书时，你再次通过该程序提供标题，并找回原来给出的相同的货架号和槽号，这是书的位置。
正如其他人已经提到的那样，该程序被称为散列算法或散列计算，通常通过将数据输入到该程序中（本例中为书名）并根据其计算数字。
为了简单起见，我们假设它只是将每个字母和符号转换为数字并将它们总和起来。 事实上，这比这更复杂，但我们现在就让它离开。
这种算法的美妙之处在于，如果您一次又一次地向其输入相同的输入，则每次都会继续吐出相同的数字。
好吧，这基本上是一个哈希表的工作原理。
技术的东西如下。
首先，数字的大小。 通常，这种散列算法的输出在一定数量的范围内，通常比表中的空间大得多。 举例来说，假设我们在图书馆中有一百万本书的空间。 哈希计算的结果可能在0到10亿的范围内，这是很高的。
那么我们该怎么办？ 我们使用一种称为模数计算的方法，基本上说如果您计算出您想要的数字（即十亿个数字），但希望保持在一个更小的范围内，那么每次您达到这个较小范围的极限时， 0，但是你必须跟踪你到达的大序列有多远。
假设散列算法的输出在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号插槽中。
这导致了下一个问题。 碰撞。 由于算法没有办法将书籍分隔开来，所以它们可以完全填满图书馆（或者如果你愿意的话可以使用散列表），它总是会计算一个以前使用过的数字。 从图书馆的角度来说，当你到达书架和想要放入书籍的插槽号时，那里已经有一本书。
存在各种冲突处理方法，包括将数据运行到另一个计算中以获得表格中的另一个点（双散列），或者只是为了找到接近给定的空间的位置（即紧邻前一本书的假设插槽可用也被称为线性探测）。 这意味着你在稍后尝试查找书籍时需要进行一些挖掘工作，但它比简单地从图书馆的一端开始还要好。
最后，在某些时候，你可能想要让更多的书进入图书馆，而不是图书馆允许的。 换句话说，你需要建立一个更大的图书馆。 由于库中的确切位置是使用库的确切大小和当前大小计算的，因此如果调整库的大小，您可能最终不得不为所有书找到新位置，因为计算完成后会找到它们的位置已经改变。
我希望这个解释比水桶和功能更简单:)
用法和Lingo：
真实世界示例：
Hash＆Co.成立于1803年，缺乏计算机技术，共有300个文件柜，为其约30,000个客户提供详细信息（记录）。 每个文件夹都清楚地标识了其从0到299的唯一编号。
那时的档案管理员不得不快速提取和存储工作人员的客户记录。 工作人员已经决定使用哈希方法来存储和检索他们的记录会更有效率。
要提交客户记录，备案文员将使用该文件夹上写入的唯一客户号码。 使用这个客户端号码，他们会调整散列密钥300，以便识别它所包含的文件柜。当他们打开文件柜时，他们会发现它包含许多按客户端编号排序的文件夹。 在确定了正确的位置之后，他们会简单地将其滑入。
为了检索客户记录，提交文员将在纸条上提供客户编号。 使用这个唯一的客户端号码，他们会调整它300（哈希键），以确定哪个文件柜有客户端文件夹。 当他们打开档案柜时，他们会发现它包含许多按客户编号排序的文件夹。 通过搜索记录，他们会很快找到客户端文件夹并检索它。
在我们现实世界的例子中，我们的水桶是文件柜，我们的记录是文件夹。
一个重要的事情要记住的是，电脑（和他们的算法）处理数字比字符串更好。 因此使用索引访问大型数组比访问顺序要快得多。
正如Simon提到的我认为非常重要的一点是，哈希部分是将大型空间（任意长度，通常是字符串等）进行转换并将其映射到一个用于索引的小空间（已知大小，通常是数字）。 这个如果记住非常重要！
所以在上面的例子中，30,000个可能的客户端被映射到一个更小的空间。
其主要思想是将整个数据集分成不同的部分，以加快通常耗时的实际搜索。 在我们上面的例子中，300个文件柜中的每一个（统计上）都会包含大约100个记录。 通过100条记录搜索（无论订单）比处理30,000个要快得多。
你可能已经注意到有些实际上已经这样做了。 但是，与其设计一种散列方法来生成散列键，它们在大多数情况下只是使用姓氏的第一个字母。 因此，如果您有26个文件柜，每个文件柜都包含从A到Z的字母，理论上您已经将您的数据分割并加强了归档和检索过程。
希望这可以帮助，
Jeach！
事实证明，这是一个相当深的理论领域，但基本轮廓很简单。
从本质上讲，散列函数只是一个从一个空间（例如任意长度的字符串）中取出东西的函数，并将它们映射到一个对索引有用的空间（如无符号整数）。
如果你只有很小的空间需要散列，那么你可能会把这些东西解释为整数，而你完成了（例如4字节的字符串）
不过，通常情况下，你有更大的空间。 如果你允许的东西作为键的空间大于你用来索引的东西的空间（你的uint32或其他），那么你不可能为每个东西都有一个唯一的值。 当两个或两个以上的东西哈希到相同的结果，你必须以适当的方式处理冗余（这通常被称为碰撞，你如何处理或不取决于你是什么使用散列）。
这意味着你希望它不太可能有相同的结果，并且你可能也真的希望散列函数更快。
平衡这两个属性（以及其他一些属性）让很多人忙碌起来！
在实践中，您通常应该能够找到已知适用于您的应用程序并使用它的功能。
现在让这个工作成为一个哈希表：想象一下，你并不关心内存使用情况。 然后，只要您的索引集（例如，所有uint32）都可以创建一个数组。 当你添加一些东西到表中时，你将它散列为键，并查看该索引处的数组。 如果那里什么都没有，你就把价值放在那里。 如果那里已经有东西，你可以将这个新条目添加到该地址的一个列表中，以及足够的信息（你的原始密钥或聪明的东西），以找到哪个条目实际上属于哪个键。
因此，当你走了很长一段时间，你的散列表（数组）中的每个条目都是空的，或者包含一个条目或一个条目列表。 检索是一种简单的索引入数组，并返回值，或走值的列表并返回正确的值。
当然在实践中你通常不能这样做，这会浪费太多的记忆。 所以你根据一个稀疏数组来做一切事情（其中唯一的条目是你实际使用的条目，其他条目都隐式为空）。
有很多方案和技巧可以使这项工作更好，但这是基础知识。
链接地址: http://www.djcxy.com/p/91909.html