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

例如,我知道它接受键,计算哈希(我正在寻找一个解释),然后执行某种模运算来计算出它在存储值的数组中的位置,但我的知识到此为止。

谁能解释一下过程吗?

编辑:我并不是特别问哈希码是如何计算的,而是对哈希表如何工作的一般概述。


当前回答

用法和行话:

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

现实世界的例子:

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

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

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

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

在我们的实际示例中,桶是文件柜,记录是文件夹。


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

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

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


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

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

其他回答

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

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

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

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

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

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

我的理解是这样的:

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

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

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

这是一个外行的解释。

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

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

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

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

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

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

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

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

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

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

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

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

首先是数字的大小。通常,这种哈希算法的输出在一个较大的数字范围内,通常比表中的空间大得多。例如,假设我们的图书馆刚好有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号槽里。

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

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

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

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

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

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

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

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

But of course there could be more than one person with the same age, so what you put in the array at each entry is a list of all the people who have that age. So you can get to an individual person's information in one step plus a little bit of search in that list (called a "bucket"). It only slows down if there are so many people that the buckets get big. Then you need a larger array, and some other way to get more identifying information about the person, like the first few letters of their surname, instead of using age.

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