前面提到,在Hash table中发生碰撞时,我们会使用chaining的方式处理,也就是在每一个slot中建立一个linked list,但这会涉及到很多指标问题,以及花费额外的时间开销,以及每一个元素,还要记录下一个节点的指标,为此,我们使用了另外一种方法,称为open addressing。
open addressing就是直接将每一笔资料直接放到hash table中,hash table的每一个slot最多一个元素,假设我们有个slot,有个元素,我们要保证才能使用这个方法,也就是,但open addresssing有一个显而易见的问题,就是必然会发生碰撞,这时候,我们使用探测(Probing)这个方式,来找到下一个为空的slot。
探测的顺序不一定要按照这个顺序,而是依靠於待插入的,而具体要将元素放到哪一个位置,使用一个特殊的hash function来决定,这个hash function需要两个参数,一个为,另一个为探测的次数(trial count),hash function会输出一个介於到的数字。
我们会希望整个hash table是没有空间被浪费的,因此上面hash function所产生出的数值所构成的集合,会刚好为到的其中一种排列。
探测的目的就是要找到下一个空的slot,下面演示一个阵列和使用探测的方式进行插入
上面这张图演示使用insert插入元素的形式,如果失败,则探测次数加1,目的是为了改变hash function所产生的值。
而插入的概念就像是上方所演示的,如果发现slot为NULL,则插入该slot,如果发现Hash table已经满了,则回传错误
HASH-INSERT(T, k)
i = 0
repeat
j = h(k, i)
if T[j] == NULL
T[j] = k
return j
else
i = i + 1
until i == m
error "hash table overflow"
而搜寻的操作也和插入是一样的,如果找到就回传该index,否则回传NULL。
HASH-SEARCH(T,k)
i = 0
repeat
j = h(k, j)
if T[j] == k
return j
i = i + 1
until T[j] == NULL or i == m
return NULL
而删除的部分就比较麻烦了,如果我们将想要删除的数值标示成NULL,那麽在搜寻时我们就会出问题了,因为HASH-SEARCH会停在当T[j] == NULL时,因此会回传NULL表示该数值不在Hash table中,而这很明显是错误的,因此,我们必须要有一个特殊的标示符来表示该节点已经被删除,为此,我们必须修改一点点HASH-SEARCH,当遇到删除的标示符,继续遍历,不做任何行为。
而HASH-INSERT也要做出相似的修改,当遇到NULL或是删除标示符,就可以将欲插入的数值放入该slot。
而我们可以发现到,当我们在做insert, search, delete时,这些操作都取决於我们的hash function,也就是我们探测的方式(probing),插入第一个元素,为,接着继续插入元素,如果发生该slot有元素存在,则我们就必须考虑现有的元素数目,也就是修改hash fuction的参数,探测数目,去找到空的slot去执行我们想要的操作。
给定一个普通的杂凑函数,线性探测使用的杂凑函数为以下
这个方法使用加了常数,然後藉由来使杂凑值保持在一定的范围,可以确保我们产生出到的所有排列。可以当作任意杂凑函数,像是除法杂凑法,乘法杂凑法等等。
虽然这是一个很简单产生出到排序的做法,但它存在一个问题,称为一次群集(primary clustering)。表示hash table中某一个区块的slot都已经有元素了,如果这时候有一个又被分配到该区域,可能会造成我们需要进行很多次linear probing才找到合适的slot进行操作,因为每一次只移动一格i, k不变,而这连带会影响到insert, delete和search的效率。
双重杂凑是用於open addressing最好的方法之一,他产生出的排列具有随机选择性和许多特性,他的杂凑函数如下
如果和互质,则可以保证我们产生出到的组合,而要满足这个条件,我们可以假设 , ,或是另外一个方法,取为质数,令,,其中略小於,若为质数,则必然与~的任何数字互质,而由於是取决於另外一个hash function,因此我们可以产生出更大的群集,使上面线性探测发生的一次群集的发生情况大幅度降低。
参考资料:Introduction to algorithms 3rd, https://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html
<<: Day 22 - Vue Router基本概念(2)
>>: #22 No-code 之旅 — 静态网站可以部署到哪里?~
引言 不好意思,作者总是有说不完的序言! 「机派X」的由来源自於无人机的机、树莓派的派还有 Linu...
Heroku 网址:https://www.heroku.com/ LINE Developers...
简单来说,TeamCity 的运作方式是 Server + Agent 的架构。平常我们看到的 Te...
LINE Developers:https://developers.line.biz/zh-ha...
这个得上一篇:https://ithelp.ithome.com.tw/articles/10258...