一、什么是散列表

散列表是由數(shù)組擴(kuò)展而來，其通過散列函數(shù)將元素的鍵值映射為下標(biāo)，然后將元素存儲(chǔ)在數(shù)組中對(duì)應(yīng)下標(biāo)的位置。

關(guān)鍵字經(jīng)過散列函數(shù)的計(jì)算得到一個(gè)散列值：hash(key)=hashCode；關(guān)于散列函數(shù)的選擇和設(shè)計(jì)，應(yīng)該要滿足如下三個(gè)要求：

• 散列值一定是一個(gè)非負(fù)整數(shù)；
• 如果key1 == key2，那么hash(k1) == hash(k2)；
• 如果key1 != key2， 那么hash(k1) != hash(k2)；

這三個(gè)條件中，最難滿足的就是第三點(diǎn)，在現(xiàn)實(shí)中找一個(gè)這樣的散列函數(shù)幾乎是不可能的；比如著名的hash算法MD5、SHA、CRC等，都只是盡量均勻地散列，盡量避免散列沖突，但是做不到完全避免；而且由于數(shù)組空間有限，散列沖突就太正常不過了。

二、如何處理散列沖突

2.1 開放尋址法

線性探測(cè)

當(dāng)散列沖突發(fā)生時(shí)，存儲(chǔ)位置已經(jīng)被占用，那么就往后探測(cè)查找空閑位置；

如果想在散列表中查找某個(gè)元素，那么先計(jì)算得到散列值，找到該值對(duì)應(yīng)的存儲(chǔ)空間，如果無值，說明要查找的元素不存在；如果有值，那么就比對(duì)值是否相等，相等則說明找到了，不相等那么就依次往后探測(cè)比較，要么找到，要么遇到空閑的存儲(chǔ)空間，說明查找的元素不存在；

如果想在散列表中刪除元素，那么不能將其簡(jiǎn)單地刪除，因?yàn)閯h除后會(huì)導(dǎo)致該空間后面的元素查找失敗，因?yàn)閷⑿枰獎(jiǎng)h除的元素置為邏輯刪除，如此才能不影響后面元素的查找過程；

線性探測(cè)方法弊端比較明顯，極端情況下插入、查找、刪除都需要探測(cè)n個(gè)元素才能找到目標(biāo)位置，時(shí)間復(fù)雜度為O(n)；

二次探測(cè)

其實(shí)是在線性探測(cè)的基礎(chǔ)上每次探測(cè)增大步長(zhǎng)，比如，每次探測(cè)當(dāng)前次數(shù)的平方之后的位置，如此可以降低探測(cè)的次數(shù)的概率；但是不能解決線性探測(cè)同樣的弊端問題；

雙重散列

準(zhǔn)備多個(gè)散列函數(shù)，如果第一個(gè)散列之后沖突了，就換一個(gè)散列函數(shù)，依次類推，直到找到空閑位置；但是一樣的，當(dāng)元素增多后，所有散列函數(shù)都可能造成散列沖突；

使用場(chǎng)景

當(dāng)數(shù)據(jù)量比較小，且裝載因子也比較小的時(shí)候，適合使用開放尋址法，比如ThreadLocalMap；

2.2 鏈表法

該種方法中，每個(gè)位置（可以稱為桶、槽）對(duì)應(yīng)一個(gè)鏈表，所有散列值相同的元素都放在該位置對(duì)應(yīng)的鏈表中，結(jié)構(gòu)示意圖如下：

鏈表發(fā)解決散列沖突示意

當(dāng)需要插入元素的時(shí)候，直接找到對(duì)應(yīng)下標(biāo)的插槽，插入鏈表即可，時(shí)間復(fù)雜度為O(1)；

當(dāng)需要查找和刪除元素的時(shí)候，也是找到對(duì)應(yīng)下標(biāo)的插槽，然后遍歷鏈表查找即可，時(shí)間復(fù)雜度為O(n/m)，n是當(dāng)前元素的個(gè)數(shù)，m是數(shù)組大小，假設(shè)散列是均勻的，那么時(shí)間復(fù)雜度就是鏈表的長(zhǎng)度；

無論插入、查找還是刪除，時(shí)間復(fù)雜度都要優(yōu)于開放尋址法；

適用場(chǎng)景：

當(dāng)需要存儲(chǔ)的數(shù)據(jù)比較多，或者存儲(chǔ)的是大對(duì)象的時(shí)候，鏈表法比較合適，而且鏈表的長(zhǎng)度過長(zhǎng)時(shí)可以采用靈活的優(yōu)化策略，比如紅黑樹來代替鏈表，如此查找時(shí)間復(fù)雜度最壞情況下的O(n)就能優(yōu)化為O(logn)；

2.3 裝載因子

裝載因子=已經(jīng)裝入散列表中的元素個(gè)數(shù)/散列表總的位置個(gè)數(shù)

裝載因子是用來衡量散列表當(dāng)前盈滿程度的指標(biāo)，其越大，說明散列沖突的概率就越高，當(dāng)達(dá)到一定程度，就需要對(duì)散列表進(jìn)行擴(kuò)容了。

開放尋址法中，裝載因子不會(huì)超過100%，但是在拉鏈法中，裝載因子是會(huì)超過100%的；

三、散列函數(shù)的設(shè)計(jì)

散列函數(shù)不能太復(fù)雜，否則計(jì)算散列值就需要花費(fèi)很多時(shí)間和資源；

散列函數(shù)生成的值要盡可能隨機(jī)并且均勻分布，最小化散列沖突，并避免某個(gè)槽中的鏈表過長(zhǎng)；

裝載因子需要根據(jù)實(shí)際情況進(jìn)行設(shè)置，當(dāng)超過閾值會(huì)觸發(fā)散列表的擴(kuò)容和rehash（重新申請(qǐng)一個(gè)大的散列表），時(shí)間復(fù)雜度將為O(n)；當(dāng)小于某個(gè)閾值會(huì)觸發(fā)縮容和rehash；如果閾值設(shè)置地太大，就容易造成散列沖突，但如果設(shè)置地太小，就容易造成空間資源浪費(fèi)；

為了避免擴(kuò)容和rehash的影響，可以在裝載因子達(dá)到閾值時(shí)先申請(qǐng)大的散列表，但是不做rehash，當(dāng)有新的元素需要插入的時(shí)候，就插入到新的散列表中，并從舊的散列表中取小量的元素進(jìn)行rehash，當(dāng)插入若干新元素后，舊的散列表中的所有元素就能逐漸rehash到新的散列表，如此是將整個(gè)rehash均攤到每次插入新元素操作中，用戶就不會(huì)感覺效率低了，此時(shí)的時(shí)間復(fù)雜度近似O(1)；

四、散列表HashMap分析

初始大小默認(rèn)為16，如果事先能知道數(shù)據(jù)量，可以在初始化的時(shí)候就設(shè)置相應(yīng)的大小，避免動(dòng)態(tài)擴(kuò)容。

最大裝載因子為0.75，觸發(fā)擴(kuò)容時(shí)，會(huì)擴(kuò)容為原來的兩倍。

當(dāng)鏈表長(zhǎng)度超過8時(shí)，鏈表就轉(zhuǎn)換為紅黑樹，從而提高增刪查改的效率；當(dāng)紅黑樹元素個(gè)數(shù)小于8個(gè)的時(shí)候，就會(huì)再次轉(zhuǎn)換會(huì)鏈表，因?yàn)樾?shù)據(jù)量時(shí)紅黑樹為了維護(hù)平衡，性能并不比鏈表高。

散列函數(shù)并不復(fù)雜，足夠簡(jiǎn)單高效，并且分布均勻。

int hash(Object key){
  // 鍵對(duì)象的
  hashcodeint h = key.hashCode();
  // capitity表示散列表的大小
  return (h ^ (h >>> 16)) & (capitity - 1);
}

五、散列表LinkedHashMap分析

也是通過散列表和鏈表組合在一起實(shí)現(xiàn)的，只不過此處的鏈表不是單鏈表，而是雙向鏈表，可以用來記錄元素插入的順序?