開(kāi)放尋址是其中一種緩解散列沖突的編程技術(shù)，當(dāng)使用開(kāi)放尋址作為沖突解決技術(shù)時(shí)，鍵值對(duì)存儲(chǔ)在表（數(shù)組）中，而不是像單獨(dú)鏈表那樣的數(shù)據(jù)結(jié)構(gòu)中。這意味著我們需要時(shí)刻留意哈希表的尺寸以及當(dāng)前表中已有的元素?cái)?shù)量。因?yàn)橐坏┕１碇杏刑嘣兀矊⒑茈y找到可用的位置來(lái)存放我們新插入的元素，因此這里我們需要引入一個(gè)重要的術(shù)語(yǔ)，負(fù)載系數(shù)(Load Factor)

負(fù)載系數(shù)

其實(shí)就是表中已有元素個(gè)數(shù)和表尺寸的比例，我們要密切關(guān)注這個(gè)系數(shù)的是因?yàn)楣１淼腛(1)恒定時(shí)間行為假設(shè)負(fù)載因子k保持一定的固定值，這意味著一旦k>閾值，我們就需要增加表的大小（理想情況下是指數(shù)增長(zhǎng)，例如，兩倍）

在上圖中，你會(huì)看到有兩種緩解沖突的方法，即單獨(dú)鏈表和線性探測(cè)(Linear Probing),在開(kāi)放尋址(線性探測(cè))技術(shù)看來(lái)，一旦達(dá)到某個(gè)閥值，它的時(shí)間復(fù)雜度就會(huì)呈現(xiàn)指數(shù)級(jí)惡化的趨勢(shì)

當(dāng)我們想要將鍵值對(duì)插入哈希表時(shí)，我們對(duì)鍵進(jìn)行哈希處理并獲得該鍵值對(duì)所屬位置的原始位置。如果我們的鍵被散列到的位置被占用(此時(shí)出現(xiàn)了沖突)，對(duì)于開(kāi)放尋址來(lái)說(shuō)，同一個(gè)位置中不允許有兩個(gè)鍵的，這不是數(shù)組的工作方式，我們要做的是使用一個(gè)探測(cè)序列函數(shù)(Probing Seque Function) 這里簡(jiǎn)稱p(x)，因?yàn)槲覀円褟纳⒘泻瘮?shù)獲取了沖突點(diǎn)的所在位置，現(xiàn)在我們使用p(x)進(jìn)行探測(cè)直到在沿途發(fā)現(xiàn)一個(gè)空閑的位置為止

探測(cè)函數(shù)

您可以提出無(wú)限數(shù)量的探測(cè)序列，這里僅提及一些常見(jiàn)的探測(cè)函數(shù)：

線性探測(cè)(Linear Probing)：p(x)= kx + b其中a，b是常數(shù)

二次探測(cè)(Quaratic Probing):p(x)= ax ^ 2 + bx + c，其中a，b，c是常數(shù)

雙重散列(Double Hashing):p(k，x)= x * h(k），其中h(k)是輔助s散列函數(shù)

偽隨機(jī)數(shù)發(fā)生器(Pseudo Random Number Generator): p(k，x)= x*RNG(h(k),x）其中RNG是以H（k）作為種子的隨機(jī)數(shù)生成器函數(shù)

本篇僅介紹線性探測(cè)函數(shù)進(jìn)行線性探測(cè)，因此給定輸入參數(shù)x,當(dāng)我們進(jìn)行探測(cè)時(shí)，我們通常會(huì)將變量x初始化為0或1作為一個(gè)起點(diǎn),如果我們找不到空閑的位置，會(huì)依次將x增加1,對(duì)以上所有這些探測(cè)函數(shù)都是一樣的

開(kāi)放尋址的通用算法

接下來(lái)，這是一個(gè)通用的開(kāi)放尋址插入算法，假設(shè)我們有一個(gè)表的尺寸為n,開(kāi)放尋址算法首先會(huì)初始化變量x=1,因?yàn)閤是一個(gè)變量，我們要用它來(lái)探測(cè)，每當(dāng)我們未能到達(dá)閑置的位置時(shí)，都需要遞增x，然后我們通過(guò)散列函數(shù)獲得keyHash,而實(shí)際上我們首先要查看表的索引，當(dāng)表索引被占用意味著它不為空，那么新索引就是我們散列的最初位置(keyHash所指向的起始索引)加上探測(cè)函數(shù)的總和再于表尺寸N取模運(yùn)算得到整數(shù)，由于我們總是回到表里，在循環(huán)中要遞增x。下一次當(dāng)我們?cè)诓煌奈恢锰綔y(cè)時(shí)，在while循環(huán)中，最終我們會(huì)找到一個(gè)空閑的位置

x=1 keyHash=h(k) index=keyHash while table[index]!=NULL: index=(keyHash+p(k,x)) mod N x=x+1 insert(k,v,index)

死循環(huán)地獄（Chaos with Cycle）

由于我們知道負(fù)載系數(shù)被控制在一定的范圍內(nèi)，所以這里有個(gè)問(wèn)題，就是開(kāi)放尋址中的探測(cè)函數(shù)存在缺陷--死循環(huán)地獄,以表尺寸N為模的大多數(shù)隨機(jī)選擇的探測(cè)序列將產(chǎn)生比表大小N更短的循環(huán)。當(dāng)您嘗試插入一個(gè)鍵-值對(duì)并且循環(huán)中的所有存儲(chǔ)桶都被占用時(shí)，這將成為災(zāi)難性問(wèn)題，因?yàn)槟鷮⑾萑霟o(wú)限循環(huán),這在一些老外談及哈希表的相關(guān)文章中有一個(gè)非常有趣的昵稱叫死循環(huán)地獄(Chaos with Cycle)

為了生動(dòng)說(shuō)明什么叫死循環(huán)地獄,我們這里看一個(gè)例子，這里有一個(gè)尺寸為12的哈希表，并且使用開(kāi)放尋址插入了一些鍵值對(duì)，該哈希表已經(jīng)部分填充。 占用的單元格填充有鍵值對(duì)（Ki，Vi）和帶有空令牌Φ的空單元格，如下圖所示

假設(shè)我們使用探測(cè)序列函數(shù)p(x)=4x，并且在表中插入一個(gè)新的鍵值對(duì)，并且該鍵值對(duì)的散列值為8,即h(x)=8這意味著我們會(huì)在索引8的位置插入該鍵值對(duì)，但是該位置已被占用，因?yàn)檫@里已經(jīng)有簡(jiǎn)直對(duì)(k5,v5)，所以我們?cè)撛趺崔k呢？接下來(lái)，我們需要進(jìn)行探測(cè)，所以我們計(jì)算： index=h(k)+p(1)=8+4 mod 12=0

此時(shí)，如下圖，此時(shí)探測(cè)函數(shù)會(huì)跳轉(zhuǎn)到索引為0的位置，糟糕的是索引1的位置也被占用了，因?yàn)?k1,v1)已經(jīng)存在.

當(dāng)x=2時(shí)，即index=h(k)+p(2)=(8+8) mod 12=4，探測(cè)函數(shù)會(huì)跳躍到索引4的位置，同樣這里也是被占用的，如此類推

當(dāng)x=3時(shí),即index=h(k)+p(3)=(8+12) mod 12=8,p(x)跳躍到索引8的位置,該位置被占用

當(dāng)x=4時(shí),即index=h(k)+p(4)=(8+16) mod 12=0,p(x)跳躍到索引0的位置,該位置被占用

當(dāng)x=5時(shí),即index=h(k)+p(5)=(8+20) mod 12=4,p(x)跳躍到索引4的位置,該位置被占用
.....

這樣盡管我們具有探測(cè)函數(shù)，但這種特定的情況下它一直在一個(gè)死循環(huán)里面一直做一些毫無(wú)意義的事情。

由這個(gè)例子我們可知探測(cè)函數(shù)存在缺陷，他們產(chǎn)生的周期短于表的尺寸，因此，我們要如何處理產(chǎn)生小于表大小的周期的探測(cè)功能？一般來(lái)說(shuō)，一致的看法是我們不處理這個(gè)問(wèn)題，相反，我們通過(guò)將探測(cè)函數(shù)的范圍限制在那些產(chǎn)生長(zhǎng)度為N的循環(huán)的函數(shù)上來(lái)避免這個(gè)問(wèn)題，我們選擇的那些產(chǎn)生的周期正好為N的探測(cè)函數(shù)，并且這些探測(cè)函數(shù)確實(shí)存在。

線性探測(cè)、二次探測(cè)和雙重散列等技術(shù)都受到死循環(huán)地獄問(wèn)題的影響，這就是為什么與這些方法一起使用的探測(cè)函數(shù)非常特殊的原因。這是一個(gè)很大的話題，將是接下來(lái)幾篇文章會(huì)重點(diǎn)講述這些，我們目前需要做的是重新定義非常具體的探測(cè)函數(shù)，這些函數(shù)會(huì)產(chǎn)生一個(gè)循環(huán)長(zhǎng)度為表尺寸N，并且避免無(wú)法插入元素或陷入無(wú)限循環(huán)

注意，開(kāi)放尋址對(duì)使用的哈希函數(shù)和探測(cè)函數(shù)非常敏感。如果使用單獨(dú)的鏈接作為沖突解決方法，則不必?fù)?dān)心此問(wèn)題。

小結(jié)

我們本篇用一個(gè)反例生動(dòng)地介紹了開(kāi)放尋址插入算法的底層是由探測(cè)函數(shù)和散列函數(shù)相互作用的結(jié)果，同時(shí)我們也介紹了一些探測(cè)函數(shù)的固有缺陷，就是死循環(huán)地獄,下一篇我們會(huì)詳細(xì)討論線性探測(cè)函數(shù)的原理，敬請(qǐng)期待。