我正在寻找一个关于哈希表如何工作的解释-用简单的英语为我这样的傻瓜!
例如,我知道它接受键,计算哈希(我正在寻找一个解释),然后执行某种模运算来计算出它在存储值的数组中的位置,但我的知识到此为止。
谁能解释一下过程吗?
编辑:我并不是特别问哈希码是如何计算的,而是对哈希表如何工作的一般概述。
我正在寻找一个关于哈希表如何工作的解释-用简单的英语为我这样的傻瓜!
例如,我知道它接受键,计算哈希(我正在寻找一个解释),然后执行某种模运算来计算出它在存储值的数组中的位置,但我的知识到此为止。
谁能解释一下过程吗?
编辑:我并不是特别问哈希码是如何计算的,而是对哈希表如何工作的一般概述。
当前回答
我的理解是这样的:
这里有一个例子:把整个表想象成一系列的桶。假设您有一个带有字母-数字哈希码的实现,并且每个字母都有一个存储桶。该实现将哈希码以特定字母开头的每个项放入相应的bucket中。
假设你有200个对象,但只有15个对象的哈希码以字母“B”开头。哈希表只需要查找和搜索'B' bucket中的15个对象,而不是所有200个对象。
至于计算哈希码,没有什么神奇的。目标只是让不同的对象返回不同的代码,对于相同的对象返回相同的代码。您可以编写一个类,它总是为所有实例返回相同的整数作为哈希代码,但这实际上会破坏哈希表的用处,因为它只会变成一个巨大的桶。
其他回答
简短而甜蜜:
哈希表封装了一个数组,我们称之为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%左右的容量,我们可以调整内部数组的大小,并将所有项目从旧数组移动到新数组中。
哈希的计算方式通常不取决于哈希表,而是取决于添加到哈希表中的项。在框架/基类库(如。net和Java)中,每个对象都有一个GetHashCode()(或类似)方法,返回该对象的哈希码。理想的哈希码算法和准确的实现取决于对象中表示的数据。
这是一个外行的解释。
让我们假设你想要用书填满一个图书馆,而不仅仅是把它们塞进去,而且你希望在你需要它们的时候能够很容易地再次找到它们。
因此,您决定,如果想要阅读一本书的人知道书名和确切的书名,那么这就是所有应该做的。有了书名,在图书管理员的帮助下,读者就能轻松快速地找到这本书。
那么,你该怎么做呢?当然,你可以列出你把每本书放在哪里的列表,但是你会遇到和搜索图书馆一样的问题,你需要搜索列表。当然,列表会更小,更容易搜索,但您仍然不希望从库(或列表)的一端到另一端依次搜索。
你想要的东西,有了书名,就能立刻给你正确的位置,所以你所要做的就是漫步到正确的书架上,拿起书。
但这怎么能做到呢?嗯,当你填满图书馆的时候要有一点先见之明,当你填满图书馆的时候要做很多工作。
你设计了一个聪明的小方法,而不是开始从一端到另一端填满这个库。你拿着书名,在一个小的计算机程序中运行,它会显示出书架的编号和书架上的槽号。这是你放书的地方。
这个程序的美妙之处在于,稍后,当一个人回来阅读这本书时,您再次通过程序输入标题,并获得与最初给您的相同的书架编号和插槽编号,这就是书的位置。
正如其他人已经提到的,这个程序被称为哈希算法或哈希计算,通常通过输入数据(在这种情况下是书名)并从中计算一个数字来工作。
为了简单起见,我们假设它只是将每个字母和符号转换为一个数字,并将它们全部相加。实际上,它要比这复杂得多,但现在让我们先把它放在这里。
这种算法的美妙之处在于,如果你一次又一次地向它输入相同的输入,它每次都会输出相同的数字。
这就是哈希表的基本工作原理。
接下来是技术方面的内容。
首先是数字的大小。通常,这种哈希算法的输出在一个较大的数字范围内,通常比表中的空间大得多。例如,假设我们的图书馆刚好有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号槽里。
这就导致了下一个问题。碰撞。由于该算法无法将图书间隔开来以使它们完全填满库(或者填满哈希表),因此它最终总是会计算一个以前使用过的数字。在图书馆的意义上,当你到达书架和你想放一本书的槽号时,那里已经有一本书了。
存在各种冲突处理方法,包括将数据运行到另一个计算中以获得表中的另一个位置(双重哈希),或者只是在给定的位置附近找到一个空间(例如,就在前一本书的旁边,假设插槽可用,也称为线性探测)。这意味着当你稍后试图找到这本书时,你需要做一些挖掘工作,但这仍然比简单地从图书馆的一端开始要好。
最后,在某些情况下,您可能希望将更多的书放入图书馆,而不是图书馆所允许的。换句话说,你需要建立一个更大的库。由于图书馆中的确切位置是使用图书馆的确切和当前大小计算出来的,因此,如果您调整了图书馆的大小,那么您可能最终不得不为所有书籍找到新的位置,因为为找到它们的位置所做的计算已经改变了。
我希望这个解释比桶和函数更接地气一点:)
我的理解是这样的:
这里有一个例子:把整个表想象成一系列的桶。假设您有一个带有字母-数字哈希码的实现,并且每个字母都有一个存储桶。该实现将哈希码以特定字母开头的每个项放入相应的bucket中。
假设你有200个对象,但只有15个对象的哈希码以字母“B”开头。哈希表只需要查找和搜索'B' bucket中的15个对象,而不是所有200个对象。
至于计算哈希码,没有什么神奇的。目标只是让不同的对象返回不同的代码,对于相同的对象返回相同的代码。您可以编写一个类,它总是为所有实例返回相同的整数作为哈希代码,但这实际上会破坏哈希表的用处,因为它只会变成一个巨大的桶。
对于所有寻找编程用语的人,下面是它是如何工作的。高级哈希表的内部实现有许多复杂之处,并且对存储分配/释放和搜索进行了优化,但顶层的思想是非常相同的。
(void) addValue : (object) value
{
int bucket = calculate_bucket_from_val(value);
if (bucket)
{
//do nothing, just overwrite
}
else //create bucket
{
create_extra_space_for_bucket();
}
put_value_into_bucket(bucket,value);
}
(bool) exists : (object) value
{
int bucket = calculate_bucket_from_val(value);
return bucket;
}
其中calculate_bucket_from_val()是哈希函数,所有的惟一性魔术都必须在这里发生。
经验法则是: 对于要插入的给定值,bucket必须是唯一的,并且派生自它应该存储的值。
Bucket是存储值的任何空间-这里我将它保持int作为数组索引,但它也可能是一个内存位置。