什么是哈希開放尋址法？

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

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

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

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

刪除有些特別，?不能單純的把要?jiǎng)h除的元素設(shè)置為空?，因?yàn)樵诓檎以氐倪^程中探測(cè)到的空閑位置是刪除元素的位置，就會(huì)使得查找元素的尋址算法失效，本來存在的元素誤判定為不存在。該如何解決這個(gè)問題呢？

?只需要?jiǎng)h除元素不是物理刪除而是邏輯刪除?。給刪除的元素做上delete標(biāo)記，當(dāng)查詢?cè)貙ぶ窌r(shí)遇到delete標(biāo)記的位置時(shí)不會(huì)停下來而是?繼續(xù)向后探測(cè)?，但是在插入元素尋址遇到delete標(biāo)記的位置就會(huì)把應(yīng)該刪除的元素替換掉。

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

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

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

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

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

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

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

審核編輯：符乾江