什么是哈希開放尋址法？

開放尋址法，就是當發(fā)生哈希沖突時，重新找到空閑的位置，然后插入元素。尋址方式有多種，常用的有線性尋址、二次方尋址、雙重哈希尋址：

?線性尋址?，當需要插入元素的位置被占用時，順序向后尋址，如果到數(shù)組最后也沒找到一個空閑位置，則從數(shù)組開頭尋址，直到找到一個空閑位置插入數(shù)據(jù)。線性尋址的每次尋址步長是1，尋址公式??hash(key)+n??（n是尋址的次數(shù)）。 ?二次方尋址?，就是線性尋址的總步長的二次方，即??hash(key)+n^2??。 ?雙重哈希尋址?，顧名思義就是多次哈希直到找到一個不沖突的哈希值。

采用開放尋址法解決哈希沖突，又該如何查找元素和刪除元素呢？

查找元素的過程和插入元素類似，用相同的尋址方式，尋址的同時比對key或者value是否相等，相等則認為元素存在，不相等則繼續(xù)尋址，?如果探測到空閑位置依然沒有找到則認為該元素不存在?。

刪除有些特別，?不能單純的把要刪除的元素設(shè)置為空?，因為在查找元素的過程中探測到的空閑位置是刪除元素的位置，就會使得查找元素的尋址算法失效，本來存在的元素誤判定為不存在。該如何解決這個問題呢？

?只需要刪除元素不是物理刪除而是邏輯刪除?。給刪除的元素做上delete標記，當查詢元素尋址時遇到delete標記的位置時不會停下來而是?繼續(xù)向后探測?，但是在插入元素尋址遇到delete標記的位置就會把應該刪除的元素替換掉。

三種尋址方式都有著明顯的不足：

線性尋址，尋址的性能雖然元素個數(shù)的增多逐步下降，最壞時間復雜度是O(n)。 二次方尋址，尋址的次數(shù)比線性尋址較低了，但是會因為步長是二次方，所以需要較長的數(shù)組長度，內(nèi)存利用率可能較低。 雙重哈希尋址，多次哈希可能會浪費時間，需要優(yōu)質(zhì)的哈希函數(shù)做支撐。

而整個開放尋址法的不足也很明顯：

插入、查找、刪除都需要尋址。 數(shù)組中元素越多，空閑位置越少，哈希沖突越劇烈。所以裝載因子不能太大，要及時擴容減小沖突，但是數(shù)組內(nèi)存利用率較低。

看似開放尋址法有挺多問題，但是也有一些優(yōu)點：

數(shù)據(jù)都存儲在數(shù)組中，可以有效地利用 CPU 緩存加快查詢速度。 而且，這種方法實現(xiàn)的哈希表，序列化也簡單，不像鏈表還要考慮指針。

總結(jié)而得，當數(shù)據(jù)量比較小、裝載因子小的時候，適合采用開放尋址法。這也是 Java 中??ThreadLocal???內(nèi)部類??ThreadLocalMap??使用開放尋址法解決散列沖突的原因。

審核編輯：符乾江