開放尋址是其中一種緩解散列沖突的編程技術(shù)，當使用開放尋址作為沖突解決技術(shù)時，鍵值對存儲在表（數(shù)組）中，而不是像單獨鏈表那樣的數(shù)據(jù)結(jié)構(gòu)中。這意味著我們需要時刻留意哈希表的尺寸以及當前表中已有的元素數(shù)量。因為一旦哈希表中有太多元素，也將很難找到可用的位置來存放我們新插入的元素，因此這里我們需要引入一個重要的術(shù)語，負載系數(shù)(Load Factor)

負載系數(shù)

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

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

當我們想要將鍵值對插入哈希表時，我們對鍵進行哈希處理并獲得該鍵值對所屬位置的原始位置。如果我們的鍵被散列到的位置被占用(此時出現(xiàn)了沖突)，對于開放尋址來說，同一個位置中不允許有兩個鍵的，這不是數(shù)組的工作方式，我們要做的是使用一個探測序列函數(shù)(Probing Seque Function) 這里簡稱p(x)，因為我們已從散列函數(shù)獲取了沖突點的所在位置，現(xiàn)在我們使用p(x)進行探測直到在沿途發(fā)現(xiàn)一個空閑的位置為止

探測函數(shù)

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

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

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

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

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

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

開放尋址的通用算法

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

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）

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

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

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

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

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

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

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

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

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

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

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

注意，開放尋址對使用的哈希函數(shù)和探測函數(shù)非常敏感。如果使用單獨的鏈接作為沖突解決方法，則不必擔心此問題。

小結(jié)

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