Day-26 Hash Table-开放定址(Open Addressing)

open addressing概念

前面提到,在Hash table中发生碰撞时,我们会使用chaining的方式处理,也就是在每一个slot中建立一个linked list,但这会涉及到很多指标问题,以及花费额外的时间开销,以及每一个元素,还要记录下一个节点的指标,为此,我们使用了另外一种方法,称为open addressing。

open addressing就是直接将每一笔资料直接放到hash table中,hash table的每一个slot最多一个元素,假设我们有https://chart.googleapis.com/chart?cht=tx&chl=m个slot,有https://chart.googleapis.com/chart?cht=tx&chl=n个元素,我们要保证https://chart.googleapis.com/chart?cht=tx&chl=m%3E%3Dn才能使用这个方法,也就是https://chart.googleapis.com/chart?cht=tx&chl=%5Calpha%20%3C%201,但open addresssing有一个显而易见的问题,就是必然会发生碰撞,这时候,我们使用探测(Probing)这个方式,来找到下一个为空的slot。

探测的顺序不一定要按照https://chart.googleapis.com/chart?cht=tx&chl=0%2C1%2C...%2Cm-1这个顺序,而是依靠於待插入的https://chart.googleapis.com/chart?cht=tx&chl=key,而具体要将元素放到哪一个位置,使用一个特殊的hash function来决定,这个hash function需要两个参数,一个为https://chart.googleapis.com/chart?cht=tx&chl=key,另一个为探测的次数(trial count),hash function会输出一个介於https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的数字。

我们会希望整个hash table是没有空间被浪费的,因此上面hash function所产生出的数值所构成的集合,会刚好为https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的其中一种排列。

插入(insert), 搜寻(search), 删除(delete)

探测的目的就是要找到下一个空的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),插入第一个元素,为https://chart.googleapis.com/chart?cht=tx&chl=O(1),接着继续插入元素,如果发生该slot有元素存在,则我们就必须考虑现有的元素数目,也就是修改hash fuction的参数,探测数目,去找到空的slot去执行我们想要的操作。

线性探测(linear probing)

给定一个普通的杂凑函数https://chart.googleapis.com/chart?cht=tx&chl=%5Cdisplaystyle%20h'%20%3A%20U%5Crightarrow%5Cbegin%7BBmatrix%7D0%2C1%2C...%2Cm-1%5Cend%7BBmatrix%7D,线性探测使用的杂凑函数为以下

https://chart.googleapis.com/chart?cht=tx&chl=h(k%2C%20i)%20%3D%20(h'(k)%20%2B%20i)%5C%20mod%5C%20m%5C%20%5C%20%2C%20i%20%3D%200%2C1%2C...m-1

这个方法使用加了常数https://chart.googleapis.com/chart?cht=tx&chl=i,然後藉由https://chart.googleapis.com/chart?cht=tx&chl=%5C%20mod来使杂凑值保持在一定的范围,可以确保我们产生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的所有排列。https://chart.googleapis.com/chart?cht=tx&chl=h'(k)可以当作任意杂凑函数,像是除法杂凑法,乘法杂凑法等等。

虽然这是一个很简单产生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1排序的做法,但它存在一个问题,称为一次群集(primary clustering)。表示hash table中某一个区块的slot都已经有元素了,如果这时候有一个https://chart.googleapis.com/chart?cht=tx&chl=key又被分配到该区域,可能会造成我们需要进行很多次linear probing才找到合适的slot进行操作,因为每一次只移动一格i, k不变,而这连带会影响到insert, delete和search的效率。

双重杂凑(double hashing)

双重杂凑是用於open addressing最好的方法之一,他产生出的排列具有随机选择性和许多特性,他的杂凑函数如下

https://chart.googleapis.com/chart?cht=tx&chl=h(k%2C%20i)%20%3D%20(h_1(k)%20%2B%20ih_2(k))%20%5C%20mod%20%5C%20m

如果https://chart.googleapis.com/chart?cht=tx&chl=h_2(k)https://chart.googleapis.com/chart?cht=tx&chl=m互质,则可以保证我们产生出https://chart.googleapis.com/chart?cht=tx&chl=0https://chart.googleapis.com/chart?cht=tx&chl=m-1的组合,而要满足这个条件,我们可以假设https://chart.googleapis.com/chart?cht=tx&chl=m%3D2%5Er , https://chart.googleapis.com/chart?cht=tx&chl=h_2(k)%20%5C%20mod%5C%20k%20%5Cne%200,或是另外一个方法,取https://chart.googleapis.com/chart?cht=tx&chl=m为质数,令https://chart.googleapis.com/chart?cht=tx&chl=h_1(k)%20%3D%20k%20%5C%20mod%5C%20m,https://chart.googleapis.com/chart?cht=tx&chl=%20h_2(k)%20%3D%201%20%2B%20(k%5C%20mod%5C%20m'),其中https://chart.googleapis.com/chart?cht=tx&chl=m'略小於https://chart.googleapis.com/chart?cht=tx&chl=m,若https://chart.googleapis.com/chart?cht=tx&chl=m为质数,则https://chart.googleapis.com/chart?cht=tx&chl=m必然与https://chart.googleapis.com/chart?cht=tx&chl=1~https://chart.googleapis.com/chart?cht=tx&chl=m'的任何数字互质,而由於https://chart.googleapis.com/chart?cht=tx&chl=i是取决於另外一个hash function,因此我们可以产生出更大的群集,使上面线性探测发生的一次群集的发生情况大幅度降低。

参考资料:Introduction to algorithms 3rd, https://alrightchiu.github.io/SecondRound/hash-tableopen-addressing.html


<<:  Day 22 - Vue Router基本概念(2)

>>:  #22 No-code 之旅 — 静态网站可以部署到哪里?~

[机派X] Day 1 - 纯聊天

引言 不好意思,作者总是有说不完的序言! 「机派X」的由来源自於无人机的机、树莓派的派还有 Linu...

Day9 - 串接 LINE Login 与 LIFF

Heroku 网址:https://www.heroku.com/ LINE Developers...

第七天:加装 Build Agent

简单来说,TeamCity 的运作方式是 Server + Agent 的架构。平常我们看到的 Te...

Day25 - LIFF 使用入门

LINE Developers:https://developers.line.biz/zh-ha...

第38天~

这个得上一篇:https://ithelp.ithome.com.tw/articles/10258...