散列表 （Hash table，也叫哈希表）驮审，是根據(jù)關(guān)鍵碼值(Key value)而直接進(jìn)行訪問的數(shù)據(jù)結(jié)構(gòu)译株。也就是說，它通過把關(guān)鍵碼值映射到表中一個位置來訪問記錄屿脐，以加快查找的速度涕蚤。這個映射函數(shù)叫做散列函數(shù)宪卿。

散列思想

散列表用的是數(shù)組支持按照下標(biāo)隨機(jī)訪問數(shù)據(jù)的特性，所以散列表其實就是數(shù)組的一種擴(kuò)展万栅，由數(shù)組演化而來佑钾。可以說烦粒，如果沒有數(shù)組休溶，就沒有散列表。
我用一個例子來解釋一下扰她。假如我們有89名選手參加學(xué)校運動會兽掰。為了方便記錄成績，每個選手胸前都會貼上自己的參賽號碼徒役。這89名選手的編號依次是1到89?孽尽。 現(xiàn)在我們希望編程實現(xiàn)這樣一個功能，通過編號快速找到對應(yīng)的選手信息忧勿。你會怎么做呢?
我們可以把這89名選手的信息放在數(shù)組里杉女。編號為1的選手，我們放到數(shù)組中下標(biāo)為1的位置;編號為2的選手鸳吸，我們放到數(shù)組中下標(biāo)為2的位置熏挎。以此類推，編號 為k的選手放到數(shù)組中下標(biāo)為k的位置晌砾。
因為參賽編號跟數(shù)組下標(biāo)一一對應(yīng)婆瓜，當(dāng)我們需要查詢參賽編號為x的選手的時候，我們只需要將下標(biāo)為x的數(shù)組元素取出來就可以了贡羔，時間復(fù)雜度就是O(1)廉白。這樣 按照編號查找選手信息，效率是不是很高?
實際上乖寒，這個例子已經(jīng)用到了散列的思想猴蹂。在這個例子里，參賽編號是自然數(shù)楣嘁，并且與數(shù)組的下標(biāo)形成一一映射磅轻，所以利用數(shù)組支持根據(jù)下標(biāo)隨機(jī)訪問的時候， 時間復(fù)雜度是O(1)這一特性逐虚，就可以實現(xiàn)快速查找編號對應(yīng)的選手信息聋溜。
你可能要說了，這個例子中蘊含的散列思想還不夠明顯叭爱，那我來改造一下這個例子撮躁。
假設(shè)校長說，參賽編號不能設(shè)置得這么簡單买雾，要加上年級把曼、班級這些更詳細(xì)的信息杨帽，所以我們把編號的規(guī)則稍微修改了一下，用6位數(shù)字來表示嗤军。比如051167注盈，其 中，前兩位05表示年級叙赚，中間兩位11表示班級老客，最后兩位還是原來的編號1到89。這個時候我們該如何存儲選手信息震叮，才能夠支持通過編號來快速查找選手信息 呢?
思路還是跟前面類似胧砰。盡管我們不能直接把編號作為數(shù)組下標(biāo)，但我們可以截取參賽編號的后兩位作為數(shù)組下標(biāo)冤荆，來存取選手信息數(shù)據(jù)。當(dāng)通過參賽編號查詢選
手信息的時候权纤，我們用同樣的方法钓简，取參賽編號的后兩位，作為數(shù)組下標(biāo)汹想，來讀取數(shù)組中的數(shù)據(jù)外邓。
這就是典型的散列思想。其中古掏，參賽選手的編號我們叫作鍵(key)或者關(guān)鍵字损话。我們用它來標(biāo)識一個選手。我們把參賽編號轉(zhuǎn)化為數(shù)組下標(biāo)的映射方法就叫作散 列函數(shù)(或“Hash函數(shù)”“哈希函數(shù)”)槽唾，而散列函數(shù)計算得到的值就叫作散列值(或“Hash值”“哈希值”)丧枪。

散列思想

散列函數(shù)

散列函數(shù)，顧名思義庞萍，它是一個函數(shù)拧烦。我們可以把它定義成hash(key)，其中key表示元素的鍵值钝计，hash(key)的值表示經(jīng)過散列函數(shù)計算得到的散列值恋博。

散列函數(shù)設(shè)計的基本要求:

1. 散列函數(shù)計算得到的散列值是一個非負(fù)整數(shù)。
2. 如果key1 = key2私恬，那hash(key1) == hash(key2)债沮。
3. 如果key1 =? key2，那hash(key1) =? hash(key2)本鸣。

其中疫衩，第一點理解起來應(yīng)該沒有任何問題。因為數(shù)組下標(biāo)是從0開始的荣德，所以散列函數(shù)生成的散列值也要是非負(fù)整數(shù)隧土。第二點也很好理解提针。 相同的key，經(jīng)過散列函數(shù)得到的散列值也應(yīng)該是相同的曹傀。
第三點理解起來可能會有問題辐脖，我著重說一下。這個要求看起來合情合理皆愉，但是在真實的情況下嗜价，要想找到一個不同的key對應(yīng)的散列值都不一樣的散列函數(shù)，幾 乎是不可能的幕庐。即便像業(yè)界著名的MD5久锥、SHA、CRC等哈希算法异剥，也無法完全避免這種散列沖突瑟由。而且，因為數(shù)組的存儲空間有限冤寿，也會加大散列沖突的概率歹苦。
所以我們幾乎無法找到一個完美的無沖突的散列函數(shù)，即便能找到督怜，付出的時間成本殴瘦、計算成本也是很大的，所以針對散列沖突問題号杠，我們需要通過其他途徑來解決蚪腋。

散列沖突

再好的散列函數(shù)也無法避免散列沖突。那究竟該如何解決散列沖突問題呢?我們常用的散列沖突解決方法有兩類姨蟋，開放尋址法(open addressing)和鏈表法
(chaining)屉凯。

1.開放尋址法

開放尋址法的核心思想是，如果出現(xiàn)了散列沖突眼溶，我們就重新探測一個空閑位置神得，將其插入。那如何重新探測新的位置呢?我先講一個比較簡單的探測方法偷仿，線 性探測(Linear Probing)哩簿。

插入

當(dāng)我們往散列表中插入數(shù)據(jù)時，如果某個數(shù)據(jù)經(jīng)過散列函數(shù)散列之后酝静，存儲位置已經(jīng)被占用了节榜，我們就從當(dāng)前位置開始，依次往后查找别智，看是否有空閑位置宗苍，直到找到為止。

插入

從圖中可以看出，散列表的大小為10讳窟，在元素x插入散列表之前让歼，已經(jīng)6個元素插入到散列表中。x經(jīng)過Hash算法之后丽啡，被散列到位置下標(biāo)為7的位置谋右，但是這個位 置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突补箍。于是我們就順序地往后一個一個找改执，看有沒有空閑的位置，遍歷到尾部都沒有找到空閑的位置坑雅，于是我們再從表頭開始 找辈挂，直到找到空閑位置2，于是將其插入到這個位置裹粤。

查找

在散列表中查找元素的過程有點兒類似插入過程终蒂。我們通過散列函數(shù)求出要查找元素的鍵值對應(yīng)的散列值，然后比較數(shù)組中下標(biāo)為散列值的元素和要查找的元
素遥诉。如果相等拇泣，則說明就是我們要找的元素;否則就順序往后依次查找。如果遍歷到數(shù)組中的空閑位置突那，還沒有找到挫酿，就說明要查找的元素并沒有在散列表中构眯。

查找

刪除

散列表跟數(shù)組一樣愕难，不僅支持插入、查找操作惫霸，還支持刪除操作猫缭。對于使用線性探測法解決沖突的散列表，刪除操作稍微有些特別壹店。我們不能單純地把要刪除的
元素設(shè)置為空猜丹。這是為什么呢?
還記得我們剛講的查找操作嗎?在查找的時候，一旦我們通過線性探測方法硅卢，找到一個空閑位置射窒，我們就可以認(rèn)定散列表中不存在這個數(shù)據(jù)。但是将塑，如果這個空
閑位置是我們后來刪除的脉顿，就會導(dǎo)致原來的查找算法失效。本來存在的數(shù)據(jù)点寥，會被認(rèn)定為不存在艾疟。這個問題如何解決呢?
我們可以將刪除的元素，特殊標(biāo)記為deleted。當(dāng)線性探測查找的時候蔽莱，遇到標(biāo)記為deleted的空間弟疆，并不是停下來，而是繼續(xù)往下探測盗冷。

刪除

問題

線性探測法其實存在很大問題怠苔。當(dāng)散列表中插入的數(shù)據(jù)越來越多時，散列沖突發(fā)生的可能性就會越來越大正塌，空閑位置會越來越少嘀略，線性探測 的時間就會越來越久。極端情況下乓诽，我們可能需要探測整個散列表帜羊，所以最壞情況下的時間復(fù)雜度為O(n)。同理鸠天，在刪除和查找時讼育，也有可能會線性探測整張散 列表，才能找到要查找或者刪除的數(shù)據(jù)稠集。在開放尋址法中奶段，所有的數(shù)據(jù)都存儲在一個數(shù)組中，比起鏈表法來說剥纷，沖突的代價更高痹籍。所以，使用開放尋址法解決沖突的散列表晦鞋，裝載因子的上限不能太大蹲缠。這也導(dǎo)致這種方法比鏈表法更浪費內(nèi)存空間。

二次探測(Quadratic probing)

二次探測悠垛，跟線性探測很像线定，線性探測每次探測的步長是1，那它探測的下標(biāo)序列就是hash(key)+0确买，hash(key)+1斤讥，hash(key)+2......而二次探測探測的步長就變 成了原來的“二次方”，也就是說湾趾，它探測的下標(biāo)序列就是hash(key)+0芭商，hash(key)+12，hash(key)+22......

雙重散列(Double hashing)

所謂雙重散列搀缠，意思就是不僅要使用一個散列函數(shù)铛楣。我們使用一組散列函數(shù)hash1(key)，hash2(key)胡嘿，hash3(key)......我們先用第一個散列函數(shù)蛉艾，如果計算得到的存 儲位置已經(jīng)被占用，再用第二個散列函數(shù)，依次類推勿侯，直到找到空閑的存儲位置拓瞪。

不管采用哪種探測方法，當(dāng)散列表中空閑位置不多的時候助琐，散列沖突的概率就會大大提高祭埂。為了盡可能保證散列表的操作效率，一般情況下兵钮，我們會盡可能保證 散列表中有一定比例的空閑槽位蛆橡。我們用裝載因子(load factor)來表示空位的多少。

裝載因子的計算公式是: 散列表的裝載因子=填入表中的元素個數(shù)/散列表的長度

裝載因子越大掘譬，說明空閑位置越少泰演，沖突越多，散列表的性能會下降葱轩。

2.鏈表法

鏈表法是一種更加常用的散列沖突解決辦法睦焕，相比開放尋址法，它要簡單很多靴拱。我們來看這個圖垃喊，在散列表中，每個“桶(bucket)”或者“槽(slot)”會對應(yīng)一條 鏈表袜炕，所有散列值相同的元素我們都放到相同槽位對應(yīng)的鏈表中本谜。
鏈表法比起開放尋址法，對大裝載因子的容忍度更高偎窘。開放尋址法只能適用裝載因子小于1的情況乌助。接近1時，就可能會有大量的散列沖突评架，導(dǎo)致大量的探測眷茁、再 散列等炕泳，性能會下降很多纵诞。但是對于鏈表法來說，只要散列函數(shù)的值隨機(jī)均勻培遵，即便裝載因子變成10浙芙，也就是鏈表的長度變長了而已，雖然查找效率有所下降籽腕， 但是比起順序查找還是快很多嗡呼。

鏈表法

當(dāng)插入的時候，我們只需要通過散列函數(shù)計算出對應(yīng)的散列槽位皇耗，將其插入到對應(yīng)鏈表中即可南窗，所以插入的時間復(fù)雜度是O(1)。當(dāng)查找、刪除一個元素時万伤，我們 同樣通過散列函數(shù)計算出對應(yīng)的槽窒悔，然后遍歷鏈表查找或者刪除。那查找或刪除操作的時間復(fù)雜度是多少呢?
實際上敌买，這兩個操作的時間復(fù)雜度跟鏈表的長度k成正比简珠，也就是O(k)。對于散列比較均勻的散列函數(shù)來說虹钮，理論上講聋庵，k=n/m，其中n表示散列中數(shù)據(jù)的個 數(shù)芙粱，m表示散列表中“槽”的個數(shù)祭玉。

問題

鏈表因為要存儲指針，所以對于比較小的對象的存儲春畔，是比較消耗內(nèi)存的攘宙，還有可能會讓內(nèi)存的消耗翻倍。而且拐迁，因為鏈 表中的結(jié)點是零散分布在內(nèi)存中的诱告，不是連續(xù)的，所以對CPU緩存是不友好的踪区，這方面對于執(zhí)行效率也有一定的影響俐载。
當(dāng)然，如果我們存儲的是大對象缓淹，也就是說要存儲的對象的大小遠(yuǎn)遠(yuǎn)大于一個指針的大小(4個字節(jié)或者8個字節(jié))哈打，那鏈表中指針的內(nèi)存消耗在大對象面前就可 以忽略了。

總結(jié)

1.開放尋址的散列沖突處理方法 比較適合當(dāng)比較小讯壶、裝載因子小的時候料仗，這也是Java中的ThreadLocalMap使用開放尋址法解決散列沖突的原因。

2. 鏈表的散列沖突處理方法比較適合存儲大對象伏蚊、大數(shù)據(jù)量的散列表立轧，而且，比起開放尋址法躏吊，它更加靈活氛改，支持更多的優(yōu)化策略，比如用紅黑樹代替鏈表比伏。
   
   紅黑樹
   
   在JDK1.8版本中胜卤，為了對HashMap做進(jìn)一步優(yōu)化，我們引入了紅黑樹赁项。而當(dāng)鏈表長度太長(默認(rèn)超過8)時葛躏，鏈表就轉(zhuǎn)換為紅黑樹澈段。我們可以利用紅黑樹快 速增刪改查的特點，提高HashMap的性能舰攒。當(dāng)紅黑樹結(jié)點個數(shù)少于8個的時候均蜜，又會將紅黑樹轉(zhuǎn)化為鏈表。因為在數(shù)據(jù)量較小的情況下芒率，紅黑樹要維護(hù)平衡囤耳，比起 鏈表來，性能上的優(yōu)勢并不明顯偶芍。