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

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

谁能解释一下过程吗?

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


当前回答

我的理解是这样的:

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

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

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

其他回答

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

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

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

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

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

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

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

简短而甜蜜:

哈希表封装了一个数组,我们称之为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)。

当我们的internalArray太满时,可能在85%左右的容量,我们可以调整内部数组的大小,并将所有项目从旧数组移动到新数组中。

我的理解是这样的:

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

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

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

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

我假设你理解数组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表示的每三分之一,按某种顺序打乱。重要的是,您不希望太多人散列到同一个存储桶,因为速度取决于存储桶保持较小。