ang*_*son 894
这是外行人的术语解释.
让我们假设您想要在图书馆中填充书籍,而不仅仅是将它们填入其中,但您希望能够在需要时再次轻松找到它们.
所以,你决定如果想要阅读一本书的人知道书的标题和确切的标题,那就应该采取这一切.有了头衔,这个人在图书管理员的帮助下,应该能够轻松快速地找到这本书.
那么,你怎么能这样做？好吧,显然你可以保留一些列出你放每本书的地方,但是你遇到的问题与搜索图书馆一样,你需要搜索列表.当然,列表会更小,更容易搜索,但您仍然不希望从库(或列表)的一端依次搜索到另一端.
你想要的东西,凭书的标题,可以立刻给你正确的位置,所以你要做的只是漫步到正确的架子,拿起书.
但是怎么做呢？好吧,当你填满图书馆并填写图书馆时需要做一些预见.
你可以设计一个聪明的小方法,而不仅仅是开始从一端到另一端填充库.你拿这本书的标题,通过一个小型计算机程序运行它,该计算机程序在该架子上吐出一个货架编号和一个插槽号.这是你放书的地方.
这个程序的美妙之处在于,当一个人回来阅读这本书时,你再次通过程序提供标题,并获得与你最初给出的相同的货架编号和插槽编号,这是这本书的位置.
正如其他人已经提到的那样,该程序被称为哈希算法或哈希计算,并且通常通过将数据输入其中(在这种情况下为书的标题)并从中计算数字来工作.
为简单起见,我们假设它只是将每个字母和符号转换为数字并将它们全部加起来.实际上,它要复杂得多,但现在让我们把它留在那里.
这种算法的优点在于,如果你一次又一次地向它输入相同的输入,它每次都会继续吐出相同的数字.
好吧,这基本上就是哈希表的工作原理.
技术内容如下.
首先,这个号码的大小.通常,这种散列算法的输出在一些大数的范围内,通常远大于表中的空间.例如,假设我们在图书馆中只有一百万册书籍.哈希计算的输出可以在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(7在14时为17,而在17和14之间的差为3).
因此,您将该书放在3号插槽中.
这导致了下一个问题.碰撞.由于算法没有办法将书籍空间分开以便它们准确地填充库(或者如果你愿意的话就填充哈希表),因此它总是会计算出之前使用过的数字.在图书馆的意义上,当你到书架和插槽时你想要放书,那里已经有一本书.
存在各种冲突处理方法,包括将数据运行到另一个计算中以获得表中的另一个点(双重散列),或者只是找到一个与您给出的空间接近的空间(即,在前一本书的旁边,假定插槽)也可称为线性探测).这意味着当你稍后尝试找到这本书时,你需要做一些挖掘工作,但它仍然比仅仅从图书馆的一端开始更好.
最后,在某些时候,您可能希望将更多书籍放入库中,而不是库允许的.换句话说,您需要构建一个更大的库.由于库中的确切位置是使用库的精确和当前大小计算的,因此如果您调整库的大小,可能最终必须找到所有书籍的新位置,因为计算完成后才能找到它们的位置已经改变.
我希望这个解释比桶和函数更加脚踏实地:)
Jea*_*ach 98
用法和Lingo:
真实世界的例子:
Hash&Co.成立于1803年,缺乏任何计算机技术,总共有300个文件柜,可以为大约30,000个客户保留详细信息(记录).每个文件夹都清楚地标识了其客户编号,从0到29,999的唯一编号.
当时的备案员必须快速获取并存储工作人员的客户记录.工作人员已经决定使用散列方法存储和检索其记录会更有效.
要提交客户记录,归档职员将使用写在该文件夹上的唯一客户端编号.使用此客户端编号,他们将调整散列密钥 300,以便识别它所包含的文件柜.当他们打开文件柜时,他们会发现它包含许多按客户编号排序的文件夹.确定正确的位置后,他们只需将其放入.
要检索客户记录,归档文员将在一张纸上给出客户编号.使用这个唯一的客户端编号(散列密钥),他们会将其调制为300,以确定哪个文件柜具有客户端文件夹.当他们打开文件柜时,他们会发现它包含许多按客户编号排序的文件夹.通过搜索记录,他们可以快速找到客户端文件夹并检索它.
在我们的实际示例中,我们的存储桶是文件柜,我们的记录是文件夹.
需要记住的一件重要事情是计算机(及其算法)处理数字比使用字符串更好.因此,使用索引访问大型数组比按顺序访问要快得多.
正如Simon所提到的,我认为非常重要的是散列部分是变换一个大空间(任意长度,通常是字符串等)并将其映射到一个小空间(已知大小,通常是数字)进行索引.这个非常重要,要记住!
因此,在上面的示例中,将30,000个可能的客户端映射到较小的空间.
其中的主要思想是将整个数据集划分为多个段,以加快实际搜索速度,这通常很耗时.在上面的示例中,300个文件柜中的每一个(统计上)将包含大约100条记录.通过100条记录搜索(无论顺序)要比处理30,000条记录要快得多.
您可能已经注意到有些人已经这样做了.但是,它们不是设计散列方法来生成散列键,而是在大多数情况下只使用姓氏的第一个字母.因此,如果您有26个文件柜,每个文件柜都包含从A到Z的字母,理论上您只需要对数据进行分段并增强文件归档和检索过程.
希望这可以帮助,
Jeach!
sim*_*mon 64
事实证明这是一个非常深刻的理论领域,但基本概要很简单.
本质上,哈希函数只是一个从一个空间(比如任意长度的字符串)获取东西并将它们映射到一个对索引有用的空间(比如说无符号整数)的函数.
如果你只有一小部分东西需要哈希,那么你可能只需将这些东西解释为整数就可以了,你就完成了(例如4字节字符串)
但通常情况下,你有更大的空间.如果你允许作为键的东西的空间大于你用来索引的东西的空间(你的uint32或其他什么)那么你不可能为每个东西都有一个唯一的值.当两个或两个以上的东西散列到相同的结果时,你将必须以适当的方式处理冗余(这通常被称为冲突,你如何处理它或不依赖于你是什么使用哈希).
这意味着您希望它不太可能具有相同的结果,并且您可能也希望哈希函数快速.
平衡这两个属性(以及其他一些属性)让很多人忙碌起来!
在实践中,您通常应该能够找到一个已知适合您的应用程序并使用它的函数.
现在让它作为哈希表工作:想象一下,你不关心内存使用情况.然后,只要您的索引集(例如,所有uint32),您就可以创建一个数组.当您向表中添加内容时,您将其哈希键并查看该索引处的数组.如果那里什么也没有,你就把价值放在那里.如果已经存在某些内容,则将此新条目添加到该地址的事物列表中,以及足够的信息(您的原始密钥或其他聪明的东西)以查找哪个条目实际属于哪个密钥.
因此,当你走了很长时间时,哈希表(数组)中的每个条目都是空的,或者包含一个条目或条目列表.检索是一个简单的索引到数组,并返回值,或遍历值列表并返回正确的值.
当然在实践中你通常不能这样做,它浪费了太多的内存.因此,您可以基于稀疏数组执行所有操作(其中唯一的条目是您实际使用的条目,其他所有条目都隐式为null).
有很多方案和技巧可以使这项工作更好,但这是基础知识.
Ton*_*roy 43
很多答案,但没有一个是非常直观的,哈希表可以在可视化时轻松"点击".
散列表通常实现为链接列表的数组.如果我们想象一个存储人名的表,在几次插入后,它可能会在内存中布局如下,其中 - ()封闭的数字是文本/名称的哈希值.
bucket# bucket content / linked list
[0] --> "sue"(780) --> null
[1] null
[2] --> "fred"(42) --> "bill"(9282) --> "jane"(42) --> null
[3] --> "mary"(73) --> null
[4] null
[5] --> "masayuki"(75) --> "sarwar"(105) --> null
[6] --> "margaret"(2626) --> null
[7] null
[8] --> "bob"(308) --> null
[9] null
几点:
[0],[1]...)被称为一个桶,并启动一个 - 可能是空的 - 链接的值列表(在这个例子中也称为元素 - 人名)"fred"使用散列42)从桶链接,[hash % number_of_buckets]例如42 % 10 == [2]; %是模数运算符 - 除以桶的数量时的余数42 % 10 == [2],和9282 % 10 == [2]),但偶尔因为哈希值相同(例如"fred","jane"两者都显示为哈希值42)
如果表大小增加,上面实现的哈希表倾向于调整自身大小(即创建更大的桶数组,从那里创建新的/更新的链表,删除旧数组)以保持元素与桶的比率(也称为负载)因素)在0.5到1.0范围内的某个地方.汉斯在下面的评论中给出了实际的公式,但是对于指示值:加载因子1和加密强度哈希函数,1/e(~36.8%)的桶将倾向于空,另外1/e(~36.8%) )有一个元素,1 /(2e)或~18.4%两个元素,1 /(3!e)约6.1%三元素,1 /(4!e)或~1.5%四元素,1 /(5!e) )大约〜.3%有五个等等. - 无论表中有多少元素(即有100个元素和100个桶,还是1亿个元素),非空桶的平均链长为~1.58和1亿个桶,这就是为什么我们说查找/插入/擦除是O(1)常数时间操作.
(注意:并非所有哈希表都使用链表,但大多数通用表都使用,因为封闭哈希(也就是开放寻址) - 尤其是支持擦除操作 - 具有较少稳定的性能属性,具有易于碰撞的键/哈希函数).
通用的,最坏情况下的冲突最小化散列函数的工作是有效地随机地在哈希表桶周围喷射密钥,同时总是为相同的密钥生成相同的哈希值.即使在密钥中任何地方改变一位,理想情况下 - 随机 - 在结果散列值中翻转大约一半的位.
这通常是用数学太精心策划的,这对我来说太复杂了.我将提到一种易于理解的方式 - 不是最具扩展性或缓存友好性但本身优雅(如使用一次性密码加密!) - 因为我认为它有助于将上述所需的品质带回家.假设您正在散列64位struct Value { string name; int age; };s - 您可以创建8个表,每个256个随机数(即name),然后使用每个8位/ 1字节Value的内存表示切片索引到不同的表中,对随机进行异或你抬头看的号码.通过这种方法,很容易看出{"sue", 63}在一个表中查找不同随机数的结果中的任何位置变化,以及完全不相关的最终值.
尽管如此,许多库的散列函数通过整数传递整数,这在最坏的情况下极易发生冲突,但希望在相当常见的整数键的情况下,往往会递增,它们将映射到连续的桶中,留下更少的比36.8%的随机散列叶片空,因此与随机映射相比,碰撞元素的冲突更少,链接列表的链接列表更少.保存生成强散列所需的时间也很棒.当键没有很好地增加时,希望它们是随机的,它们不需要强大的哈希函数来完全随机化它们放置到桶中.
嗯,这比散列表解释更有趣,更重,但希望它有助于某人....
小智 24
你们非常接近完全解释这一点,但遗漏了一些事情.哈希表只是一个数组.数组本身将在每个插槽中包含一些内容.您至少会将哈希值或值本身存储在此插槽中.除此之外,您还可以存储已在此插槽上发生冲突的链接/链接值列表,或者您可以使用开放寻址方法.您还可以存储指向要从此插槽中检索的其他数据的指针或指针.
重要的是要注意,hashvalue本身通常不指示将值放入的槽.例如,hashvalue可能是负整数值.显然负数不能指向数组位置.此外,哈希值往往会比可用的时隙数量大很多倍.因此,需要由散列表本身执行另一个计算,以确定该值应该进入哪个槽.这是通过模数运算来完成的,例如:
uint slotIndex = hashValue % hashTableSize;
该值是值将进入的槽.在开放寻址中,如果插槽已经填充了另一个哈希值和/或其他数据,则将再次运行模数操作以查找下一个插槽:
slotIndex = (remainder + 1) % hashTableSize;
我想可能还有其他更先进的方法来确定插槽索引,但这是我见过的常见方法...会对其他性能更好的人感兴趣.
使用模数方法,如果您有一个大小为1000的表,则任何介于1和1000之间的哈希值将进入相应的槽.任何负值以及任何大于1000的值都可能会碰撞插槽值.发生这种情况的可能性取决于您的散列方法,以及您添加到散列表的总项数.通常,最佳做法是使散列表的大小使得添加到其中的值的总数仅等于其大小的大约70%.如果您的哈希函数在均匀分布方面做得很好,您通常会遇到很少甚至没有桶/槽冲突,并且它将对查找和写入操作执行得非常快.如果事先不知道要添加的值的总数,请使用任何方法进行良好的估计,然后在添加到其中的元素数量达到容量的70%时调整哈希表的大小.
我希望这有帮助.
PS - 在C#中,该GetHashCode()方法非常慢,并且在我测试的许多条件下导致实际值冲突.为了一些真正的乐趣,构建自己的哈希函数并尝试使其永远不会碰撞您正在散列的特定数据,运行速度比GetHashCode快,并且具有相当均匀的分布.我使用long而不是int size hashcode值完成了这项工作,并且它在哈希表中有多达3200万个哈希值,并且有0次冲突.不幸的是,我无法共享代码,因为它属于我的雇主...但我可以透露它可能是某些数据域.当你可以实现这一点时,哈希表非常快.:)
And*_*eiM 17
这就是我的理解:
这是一个例子:将整个表格描绘成一系列桶.假设您有一个带字母数字哈希码的实现,并且每个字母表的字母都有一个存储桶.此实现将其哈希码以特定字母开头的每个项目放在相应的存储桶中.
假设您有200个对象,但其中只有15个具有以字母"B"开头的哈希码.哈希表只需要查找并搜索"B"桶中的15个对象,而不是所有200个对象.
就计算哈希码而言,没有任何神奇之处.目标只是让不同的对象返回不同的代码,并使相同的对象返回相等的代码.您可以编写一个总是返回与所有实例的哈希代码相同的整数的类,但是您实际上会破坏哈希表的有用性,因为它只会成为一个巨大的桶.
Jul*_*iet 13
短而甜蜜:
哈希表包装一个数组,让我们调用它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%的容量时,我们可以调整内部数组的大小,并将旧数组中的所有项目移动到新数组中.
cas*_*One 10
它甚至比那更简单.
哈希表只不过是包含键/值对的向量的数组(通常是稀疏的).此数组的最大大小通常小于存储在哈希表中的数据类型的可能值集中的项数.
哈希算法用于根据将存储在数组中的项的值生成该数组的索引.
这是存储数组中键/值对的向量的地方.因为数组中可以是索引的值集合通常小于该类型可能具有的所有可能值的数量,所以您的哈希值可能是算法将为两个单独的键生成相同的值.一个好的哈希算法会尽可能地防止这种情况(这就是为什么它通常因为它具有普通哈希算法不可能知道的特定信息而降级到该类型的原因),但是它是不可能防止的.
因此,您可以使用多个密钥生成相同的哈希代码.当发生这种情况时,迭代向量中的项目,并在向量中的键和正在查找的键之间进行直接比较.如果找到,则返回了很好的值并返回与键关联的值,否则返回任何内容.
你拿了一堆东西和一个数组.
对于每一件事,你构成一个索引,称为哈希.哈希的重要之处在于它散布了很多东西; 你不希望两个类似的东西有类似的哈希.
你把你的东西放在哈希指示的位置的数组中.不止一件事可以在给定的哈希值上结束,所以你将事物存储在数组或其他合适的东西中,我们通常将其称为存储桶.
当您在哈希中查找内容时,您将执行相同的步骤,计算哈希值,然后查看该位置的桶中的内容并检查它是否是您要查找的内容.
当您的散列运行良好且阵列足够大时,阵列中的任何特定索引最多只会有一些内容,因此您不必非常关注.
对于奖励积分,请将其设置为当访问哈希表时,它会将找到的东西(如果有的话)移动到桶的开头,因此下次检查时首先检查它.
为什么人们用梳妆台来存放衣服？除了看起来新潮时尚之外，它们还有一个优点，那就是每件衣服都有它应该放的地方。如果您正在寻找一双袜子，只需检查袜子抽屉即可。如果您正在寻找衬衫，请检查装有衬衫的抽屉。当您寻找袜子时，您有多少件衬衫或您有多少条裤子都没关系，因为您不需要看它们。您只需查看袜子抽屉并期望在那里找到袜子。
\n从较高的层次来看，哈希表是一种存储东西的方式，就像衣服的梳妆台一样（有点像）。基本思想如下：
\n这样的系统的优点是，假设您的规则不太复杂并且您有适当数量的抽屉，那么您只需在正确的位置查找即可很快找到您要找的东西。
\n当你收起衣服时，你使用的“规则”可能是“袜子放在左上角的抽屉里，衬衫放在中间的大抽屉里，等等”。但是，当您存储更抽象的数据时，我们使用称为哈希函数的东西来为我们做到这一点。
\n将哈希函数视为黑匣子是一种合理的方式。您将数据放在一侧，并放置一个称为哈希码的数字从另一侧输出从原理上讲，它看起来像这样：
\n +---------+\n |\\| hash |/| --> hash code\n data --> |/| function|\\|\n +---------+\n所有哈希函数都是确定性的：如果您多次将相同的数据放入函数中，您总是会从另一端获得相同的值。一个好的哈希函数应该看起来或多或少是随机的：输入数据的微小变化应该给出截然不同的哈希码。例如，字符串“pudu”和字符串“kudu”的哈希码可能彼此截然不同。（话又说回来，它们有可能是相同的。毕竟，如果哈希函数的输出看起来或多或少是随机的，那么我们就有可能两次获得相同的哈希码。）
\n究竟如何构建哈希函数？现在，让我们先说“正派的人不应该对此想太多”。数学家们已经研究出了更好和更差的哈希函数设计方法，但就我们的目的而言，我们实际上不需要过多担心内部结构。将哈希函数视为一个函数就足够了
\n一旦我们有了哈希函数，我们就可以构建一个非常简单的哈希表。我们将制作一系列“桶”，您可以将其视为类似于梳妆台中的抽屉。为了在哈希表中存储一个项目，我们将计算该对象的哈希码并将其用作表中的索引，这类似于“选择该项目放入哪个抽屉”。然后，我们将该数据项放入该索引处的存储桶中。如果那个桶是空的，那就太好了！我们可以把物品放在那里。如果桶已满，我们可以选择做什么。一种简单的方法（称为链式哈希）是将每个存储桶视为一个项目列表，就像您的袜子抽屉可能存储多个袜子一样，然后只需将项目添加到该索引处的列表中即可。
\n要在哈希表中查找某些内容，我们使用基本相同的过程。我们首先计算要查找的项目的哈希码，它告诉我们要查找哪个存储桶（抽屉）。如果该项目在表中，则它必须在该存储桶中。然后，我们只需查看桶中的所有项目，看看我们的项目是否在其中。
\n这样做有什么好处？好吧，假设我们有大量的桶，我们预计大多数桶中不会有太多东西。毕竟，我们的哈希函数看起来有点随机输出，因此项目在所有存储桶中均匀分布。事实上，如果我们形式化“我们的哈希函数看起来有点随机”的概念，我们可以证明每个桶中的预期项目数是项目总数与桶总数的比率。因此，我们可以找到我们正在寻找的项目，而无需做太多的工作。
\n解释“哈希表”的工作原理有点棘手，因为哈希表有很多种风格。下一节将讨论所有哈希表共有的一些通用实现细节，以及不同风格的哈希表如何工作的一些细节。
\n出现的第一个问题是如何将哈希码转换为表槽索引。在上面的讨论中，我只是说“使用哈希码作为索引”，但这实际上不是一个很好的主意。在大多数编程语言中，哈希码计算为 32 位或 64 位整数，并且您无法直接将它们用作存储桶索引。相反，一种常见的策略是创建一个大小为 m 的存储桶数组，计算项目的（完整 32 位或 64 位）哈希码，然后根据表的大小对它们进行修改以获得 0 到 0 之间的索引。 m-1，包括在内。模数的使用在这里效果很好，因为它速度相当快，并且可以很好地将整个范围的哈希码分布在较小的范围内。
\n（您有时会看到这里使用按位运算符。如果您的表的大小是 2 的幂，例如 2 k，那么计算哈希码的按位 AND，然后计算 2 k - 1 相当于计算模数，而且速度明显更快。）
\n下一个问题是如何选择正确数量的桶。如果您选择太多的存储桶，那么大多数存储桶将是空的或只有很少的元素（有利于速度 - 您只需检查每个存储桶的几个项目），但是您将使用一堆空间来简单地存储存储桶（而不是太棒了，尽管也许你买得起）。另一面也成立 - 如果您的存储桶太少，那么平均每个存储桶将包含更多元素，从而使查找花费更长的时间，但您将使用更少的内存。
\n一个好的折衷方案是在哈希表的生命周期内动态更改存储桶的数量。哈希表的负载因子通常表示为\xce\xb1，是元素数量与桶数量的比率。大多数哈希表都会选择一些最大负载因子。一旦负载因子超过此限制，哈希表就会增加其槽数（例如加倍），然后将旧表中的元素重新分配到新表中。这称为重新散列。假设表中的最大负载因子是一个常数，这可以确保，假设您有一个好的哈希函数，则执行查找的预期成本仍然是 O(1)。插入现在已摊销由于定期重建表的成本（与删除的情况相同），插入（如果负载因子变得太小，删除同样会压缩表。）
\n到目前为止，我们一直在讨论链式哈希，这是构建哈希表的许多不同策略之一。提醒一下，链式哈希有点像一个服装梳妆台 - 每个桶（抽屉）可以容纳多个物品，当您进行查找时，您会检查所有这些物品。
\n然而，这并不是构建哈希表的唯一方法。还有另一系列哈希表使用称为开放寻址的策略。开放寻址背后的基本思想是存储一组槽，其中每个槽可以是空的，也可以只容纳一个项目。
\n在开放寻址中，当您执行插入时，与以前一样，您会跳转到某个槽，该槽的索引取决于计算的哈希码。如果该插槽是免费的，那就太好了！你把物品放在那里，你就完成了。但如果插槽已满怎么办？在这种情况下，您可以使用一些辅助策略来查找不同的空闲插槽来存储该项目。最常见的策略是使用一种称为线性探测的方法。在线性探测中，如果您想要的插槽已满，您只需转移到表中的下一个插槽即可。如果该插槽是空的，那就太好了！您可以将物品放在那里。但如果该插槽已满，则您将移动到表中的下一个插槽，依此类推（如果您到达了表的末尾，则只需回到开头）。
\n线性探测是构建哈希表的一种令人惊讶的快速方法。CPU 缓存针对引用局部性进行了优化进行了优化，因此相邻内存位置中的内存查找往往比分散位置中的内存查找快得多。由于线性探测插入或删除是通过命中某个数组槽然后线性向前行走来工作的，因此它会导致很少的缓存未命中，并且最终比理论通常预测的速度要快得多。（而且恰好理论预测它会非常快！）
\n最近流行的另一种策略是布谷鸟哈希。我喜欢将布谷鸟哈希视为哈希表的“冻结”。我们没有一个哈希表和一个哈希函数，而是两个哈希表和两个哈希函数。每个项目可以恰好位于两个位置之一 - 它要么位于第一个哈希函数给出的第一个表中的位置，要么位于第二个哈希函数给出的第二个表中的位置。这意味着查找是最坏情况是有效的，因为您只需检查两个位置即可查看表中是否有某些内容。
\n布谷鸟散列中的插入使用与以前不同的策略。我们首先查看可以容纳该物品的两个插槽中的任何一个是否空闲。如果是这样，那就太好了！我们只是把物品放在那里。但如果这不起作用，那么我们会选择一个插槽，将物品放在那里，然后踢出原来在那里的物品。该项目必须去某个地方，因此我们尝试将其放入另一个表中的适当位置。如果有效的话，那就太好了！如果没有，我们将从该表中踢出一个项目，然后尝试将其插入到另一个表中。这个过程一直持续到一切都平静下来，或者我们发现自己陷入了一个循环。（后一种情况很少见，如果发生这种情况，我们有很多选择，例如“将其放入辅助哈希表中”或“选择新的哈希函数并重建表。”）
\n布谷鸟散列有许多可能的改进，例如使用多个表，让每个槽容纳多个项目，以及制作一个“储藏室”来容纳无法容纳在其他任何地方的项目，这是一个活跃的研究领域！
\n然后还有混合方法。跳房子散列是开放寻址和链式散列之间的混合，可以将其视为采用链式散列表并将每个桶中的每个项目存储在项目想要去的位置附近的槽中。这种策略与多线程配合得很好。Swiss表利用了一些处理器可以使用单个指令并行执行多个操作的事实来加速线性探测表。可扩展散列是为数据库和文件系统设计的，并使用特里树和链式散列表的混合来随着单个存储桶的加载而动态增加存储桶的大小。罗宾汉散列是线性探测的一种变体，其中项目可以在插入后移动，以减少每个元素可以居住的距离的差异。
\n有关哈希表基础知识的更多信息，请查看有关链式哈希的讲座幻灯片以及有关线性探测和 Robin Hood 哈希的后续幻灯片。您可以在此处了解有关布谷鸟散列的更多信息以及在此处了解散列函数的理论属性。
\n哈希的计算方式通常不取决于哈希表，而是取决于添加到其中的项。在 .net 和 Java 等框架/基类库中，每个对象都有一个 GetHashCode() （或类似）方法，返回该对象的哈希码。理想的哈希码算法和确切的实现取决于对象中表示的数据。