哈希表是如何工作的？

Question

哈希表是如何工作的？

我在寻找一个关于哈希表是如何工作的解释-用简单的英语来解释像我这样的傻瓜！

例如，我知道它接受键，计算散列(我正在寻找如何解释)，然后执行某种模块化来计算它在存储值的数组中的位置，但这就是我的知识停止的地方。

有人能澄清这个过程吗？

编辑：我不是专门问哈希码是如何计算的，而是对哈希表是如何工作的进行了概述。

Answer 1

用法和灵芝：散列表用于快速存储和检索数据(或记录)。记录存储在桶使用散列键散列键通过将散列算法应用到选定的值(钥匙值)包含在记录中。所选值必须是所有记录的公共值。各斗可以有多个按特定顺序组织的记录。真实世界的例子：哈希公司，成立于1803年，缺乏任何计算机技术，总共有300个文件柜，为他们的大约30，000名客户保存详细的信息(记录)。每个文件夹都清楚地标识了其客户端编号，这是一个从0到29，999之间的唯一编号。当时的档案办事员必须迅速为工作人员提取和储存客户记录。工作人员决定，使用散列方法存储和检索其记录将更为有效。若要归档客户记录，归档办事员将使用写入文件夹上的唯一客户编号。使用此客户端编号，它们将对散列键到300，以确定它包含在其中的文件柜。当他们打开文件柜时，他们会发现里面有许多按客户编号订购的文件夹。在确定正确的位置后，他们就会简单地溜进去。为了检索客户记录，档案办事员将在一张纸条上得到客户号码。使用此唯一客户端编号(散列键)，他们会调整它300，以确定哪个文件柜有客户文件夹。当他们打开文件柜时，他们会发现里面有许多按客户编号订购的文件夹。通过搜索记录，他们会快速找到客户端文件夹并检索它。在我们的现实世界中，我们的桶是文件柜而我们记录是文件文件夹.需要记住的一件重要的事情是，计算机(及其算法)处理数字比处理字符串更好。因此，使用索引访问大型数组比按顺序访问要快得多。正如西蒙提到的我相信非常重要哈希部分是转换一个大空间(任意长度，通常是字符串等)，并将其映射到一个小空间(已知大小，通常是数字)进行索引。这如果是非常重要的记住！所以在上面的例子中，30，000个可能的客户机被映射到一个较小的空间。其中的主要思想是将整个数据集分割成段，以加快实际的搜索，这通常是耗时的。在我们上面的例子中，300个文件柜中的每一个都会(统计上)包含大约100条记录。通过100条记录进行搜索(不管顺序如何)比处理30，000条记录要快得多。你可能已经注意到有些人实际上已经这样做了。但是，在大多数情况下，它们不会设计哈希方法来生成散列密钥，而只是使用姓氏的第一个字母。因此，如果你有26个文件柜，每个都包含一个字母从A到Z，理论上你只是分割了你的数据，并加强了归档和检索过程。希望这能帮上忙吉奇！

Answer 2

这是一个很深的理论领域，但基本的轮廓很简单。从本质上说，散列函数只是一个函数，它从一个空格(例如任意长度的字符串)获取事物，并将它们映射到一个用于索引的空间(例如，无符号整数)。如果你只有一小部分要散列的东西，你就可以把这些事情解释成整数，然后你就完成了(例如，4个字节字符串)。通常情况下，你有一个更大的空间。如果允许作为键的事物的空间大于用于索引的东西的空间(您的uint 32或其他东西)，那么您不可能对每个键都有唯一的值。当两个或多个事物散列到相同的结果时，您将不得不以一种适当的方式处理冗余(这通常被称为冲突，以及如何处理它，这在一定程度上取决于您使用哈希的目的是什么)。这意味着您希望它不太可能有相同的结果，而且您可能也非常希望哈希函数很快。平衡这两个属性(和其他几个属性)让很多人都很忙！在实践中，您通常应该能够找到一个为您的应用程序很好地工作的函数，并使用它。现在，要将其作为一个哈希表使用：假设您不关心内存的使用。然后，您可以创建一个数组，只要您的索引集(所有uint 32，例如)。当您向表中添加某些内容时，您会散列它的键，并查看该索引处的数组。如果那里什么都没有，你就把你的价值放在那里。如果已经有什么东西在那里，您可以将这个新条目添加到该地址的事物列表中，并提供足够的信息(原始密钥或一些聪明的信息)，以找到哪个条目实际上属于哪个键。因此，在进行长时间操作时，哈希表(数组)中的每个条目要么为空，要么包含一个条目或一个条目列表。检索就像索引到数组中一样简单，或者返回值，或者遍历值列表并返回正确的值。当然，在实践中，您通常不能这样做，这浪费了太多的内存。因此，您可以根据稀疏数组(其中唯一的条目是实际使用的条目，其他所有内容都隐式为空)来执行所有操作。有很多方案和技巧可以使这个工作更好，但这是最基本的。