HashMap是Java面試中的必問考點之一，網上關于HashMap實作原理的文章數不勝數。但是在翻閱了大部分HashMap相關的文章之後，發現大多數文章都是對HashMap源碼的分析，絲毫沒有提到哈希表的概念。這就導緻了很多人隻記住了HashMap的原理，卻不知哈希表為何物的奇特現象。很多情況下，面試官可能并不會直接問HashMap是如何實作的，而是抛出一個質問三連：
搞錯了，重來！什麼是哈希表？什麼是哈希沖突？如何處理哈希沖突？
對于不了解哈希表的同學，這三個問題确實觸及到了知識盲區。為了避免這種尴尬，接下來就一起來學習一下哈希表吧。
一、什麼是哈希表？
在回答這個問題之前我們先來思考一個問題：如何在一個無序的線性表中查找一個資料元素？
注意，這是一個無序的線性表，也就是說要查找的這個元素線上性表中的位置是随機的。對于這樣的情況，想要找到這個元素就必須對這個線性表進行周遊，然後與要查找的這個元素進行比較。這就意味着查找這個元素的時間複雜度為o(n)。對于o(n)的時間複雜度，在查找海量資料的時候也是一個非常消耗性能的操作。那麼有沒有一種資料結構，這個資料結構中的元素與它所在的位置存在一個對應關系，這樣的話我們就可以通過這個元素直接找到它所在的位置，而此時查找這個元素的時間複雜度就變成了o(1),可以大大節省程式的查找效率。當然，這種資料結構是存在的，它就是我們今天要講的哈希表。
我們先來看一下哈希表的定義：
哈希表又叫 散清單，是一種根據設定的映射函數f(key)将一組關鍵字映射到一個有限且連續的位址區間上，并以關鍵字在位址區間中的“像”作為元素在表中的存儲位置的一種資料結構。這個映射過程稱為 哈希造表或者 散列，這個映射函數f(key)即為 哈希函數也叫 散列函數，通過哈希函數得到的存儲位置稱為 哈希位址或 散列位址
定義總是這麼的拗口且難以了解。簡單來說，哈希表就是通過一個映射函數f(key)将一組資料散列存儲在數組中的一種資料結構。在這哈希表中，每一個元素的key和它的存儲位置都存在一個f(key)的映射關系，我們可以通過f(key)快速的查找到這個元素在表中的位置。
舉個例子，有一組資料：[19,24,6,33,51,15]，我們用散列存儲的方式将其存儲在一個長度為11的數組中。采用除留取餘法，将這組資料分别模上數組的長度（即f(key)=key % 11），以餘數作為該元素在數組中的存儲的位置。則會得到一個如下圖所示的哈希表：
此時，如果我們想從這個表中找到值為15的元素，隻需要将15模上11即可得到15在數組中的存儲位置。可見哈希表對于查找元素的效率是非常高的。
二、什麼是哈希沖突
上一節中我們舉了一個很簡單的例子來解釋什麼是哈希表，例子中的這組資料隻有6個元素。假如我們向這組資料中再插入一些元素，插入後的資料為：[19,24,6,33,51,15,25,72]，新元素25模11後得到3，存儲到3的位置沒有問題。而接下來我們對72模11之後得到了6，而此時在數組中6的位置已經被其他元素給占據了。“72“隻能很無奈的表示我放哪呢？
對于上述情況我們将其稱之為哈希沖突。哈希沖突比較官方的定義為：
哈希沖突，也叫 哈希碰撞
一般情況下，哈希沖突隻能盡可能的減少，但不可能完全避免。因為哈希函數是從關鍵字集合到位址集合的映射，通常來說關鍵字集合比較大，它的元素理論上包括所有可能的關鍵字，而位址集合的元素僅為哈希表中的位址值。這就導緻了哈希沖突的必然性。
1.如何減少哈希沖突？
盡管哈希沖突不可避免，但是我們也要盡可能的減少哈希沖突的出現。一個好的哈希函數可以有效的減少哈希沖突的出現。那什麼樣的哈希函數才是一個好的哈希函數呢？通常來說，一個好的哈希函數對于關鍵字集合中的任意一個關鍵字，經過這個函數映射到位址集合中任何一個集合的機率是相等的。
常用的構造哈希函數的方法有以下幾種： （1）除留取餘法
這個方法我們在上邊已經有接觸過了。取關鍵字被某個不大于哈希表長m的數p除後所得餘數為哈希位址。即：f(key)=key % p, p≤m;
（2）直接定址法
直接定址法是指取關鍵字或關鍵字的某個線性函數值為哈希位址。即： f(key)=key 或者 f(key)=a*key+b、
（3）數字分析法
假設關鍵字是以為基的數（如以10為基的十進制數），并且哈希表中可能出現的關鍵字都是事先知道的，則可以選取關鍵字的若幹位數組成哈希表。
當然，除了上邊列舉的幾種方法，還有很多種選取哈希函數的方法，就不一一列舉了。我們隻要知道，選取合适的哈希函數可以有效減少哈希沖突即可。
2.如何處理哈希沖突？
雖然我們可以通過選取好的哈希函數來減少哈希沖突，但是哈希沖突終究是避免不了的。那麼，碰到哈希沖突應該怎麼處理呢？接下來我們來介紹幾種處理哈希沖突的方法。
（1）開放定址法
開放定址法是指當發生位址沖突時，按照某種方法繼續探測哈希表中的其他存儲單元，直到找到空位置為止。
我們以本節開頭的例子來講解開放定址法是如何處理沖突的。72模11後得到6，而此時6的位置已經被其他元素占用了，那麼将6加1得到7， 此時發現7的位置也被占用了，那就再加1得到下一個位址為8，而此時8仍然被占用，再接着加1得到9，此時9處為空，則将72存入其中，即得到如下哈希表：
像上邊的這種探測方法稱為線性探測再散列。當然除了線性探測再散列之外還有二次探測再散列，探測位址的方式為原哈希位址加上d (d=
、
、
......
)，經過二次探測再散列後會得到求得72的哈希位址為5，存儲如下圖所示：
（2）再哈希法
再哈希法即選取若幹個不同的哈希函數，在産生哈希沖突的時候計算另一個哈希函數，直到不再發生沖突為止。
（3）建立公共溢出區
專門維護一個溢出表，當發生哈希沖突時，将值填入溢出表。
（4）鍊位址法
鍊位址法是指在碰到哈希沖突的時候，将沖突的元素以連結清單的形式進行存儲。也就是凡是哈希位址為i的元素都插入到同一個連結清單中，元素插入的位置可以是表頭（頭插法），也可以是表尾（尾插法）。我們以仍然以[19,24,6,33,51,15,25,72] 這一組資料為例，用鍊位址法來進行哈希沖突的處理，得到如下圖所示的哈希表：
我們可以向這組資料中再添加一些元素，得到一組新的資料[19,24,6,33,51,15,25,72,37,17,4,55,83]。使用鍊位址法得到如下哈希表：
三、鍊位址法的弊端與優化
上一節中我們講解了幾種常用的處理哈希沖突的方法。其中比較常用的是鍊位址法，比如HashMap就是基于鍊位址法的哈希表結構。雖然鍊位址法是一種很好的處理哈希沖突的方法，但是在一些極端情況下鍊位址法也會出現問題。舉個例子，我們現在有這樣一組資料：[48,15,26,4,70,82,59]。我們将這組資料仍然散列存儲到長度為11的數組中，此時則得到了如下的結果：
可以發現，此時的哈希表俨然已經退化成了一個連結清單，當我們在這樣的資料結構中去查找某個元素的話，時間複雜度又變回了o(n)。這顯然不符合我們的預期。是以，當哈希表中的連結清單過長時就需要我們對其進行優化。我們知道，二叉查找樹的查詢效率是遠遠高于連結清單的。是以，當哈希表中的連結清單過長時我們就可以把這個連結清單變成一棵紅黑樹。上面的一組資料優化後可得到如下結果：
紅黑樹是一個可以自平衡的二叉查找樹。它的查詢的時間複雜度為o(lgn)。通過這樣的優化可以提高哈希表的查詢效率。
四、哈希表的擴容與Rehash
在哈希表長度不變的情況下，随着哈希表中插入的元素越來越多，發生哈希沖突的機率會越來越大，相應的查找的效率就會越來越低。這意味着影響哈希表性能的因素除了哈希函數與處理沖突的方法之外，還與哈希表的裝填因子大小有關。
裝填因子。裝填因子 α=
很顯然，α的值越小哈希沖突的機率越小，查找時的效率也就越高。而減小α的值就意味着降低了哈希表的使用率。顯然這是一個沖突的關系，不可能有完美解。為了兼顧彼此，裝填因子的最大值一般選在0.65~0.9之間。比如HashMap中就将裝填因子定為0.75。一旦HashMap的裝填因子大于0.75的時候，為了減少哈希沖突，就需要對哈希表進行擴容操作。比如我們可以将哈希表的長度擴大到原來的2倍。
這裡我們應該知道，擴容并不是在原數組基礎上擴大容量，而是需要申請一個長度為原來2倍的新數組。是以，擴容之後就需要将原來的資料從舊數組中重新散列存放到擴容後的新數組。這個過程我們稱之為Rehash。
接下來我們仍然以[19,24,6,33,51,15,25,72,37,17,4,55,83]這組資料為例來示範哈希表擴容與Rehash的過程。假設哈希表的初始長度為11，裝載因子的最大值定位0.75，擴容前的資料插入如下圖所示：
當我們插入第11個元素的時候發現此時的裝填因子已經大于了0.75，是以觸發了擴容操作。為了友善畫圖，這裡将數組長度擴充到了18。擴容後将[19,24,6,33,51,15,25,72,37,17,4,55,83]這組資料重新散列，會得到如下圖所示的結果：
可以看到擴容前後元素存儲位置大相徑庭。Rehash的操作将會重新散列擴容前已經存儲的資料，這一操作涉及大量的元素移動，是一個非常消耗性能的操作。是以，在開發中我們應該盡量避免Rehash的出現。比如，可以預估元素的個數，事先指定哈希表的長度，這樣可以有效減少Rehash。
五、總結
哈希表是資料結構中非常重要的一個知識點，本篇文章詳細的講解了哈希表的相關概念，讓大家對哈希表有了一個清晰的認識。哈希表彌補了線性表或者樹的查找效率低的問題，通過哈希表在理想的情況下可以将查找某個元素的時間複雜度降低到o(1),但是由于哈希沖突的存在，哈希表的查找效率很難達到理想的效果。另外，哈希表的擴容與Rehash的操作對哈希表存儲時的性能也有很大的影響。由此可見使用哈希表存儲資料也并非一個完美的方案。但是，對于查找性能要求高的情況下哈希表的資料結構還是我們的不二選擇。
最後了解了哈希表對于了解HashMap會有莫大的幫助。畢竟HashMap本身就是基于哈希表實作的。
原作者：馬可沒有鳳梨