無論是數(shù)組還是鏈表猜拾，其對(duì)數(shù)據(jù)的查詢表現(xiàn)都比較無力泳梆，要想知道一個(gè)元素是否在數(shù)組或鏈表中，只能從前向后挨個(gè)對(duì)比拓瞪。出現(xiàn)這個(gè)問題的根源在于，我們沒有辦法直接根據(jù)一個(gè)元素找到它存儲(chǔ)的位置助琐，那有沒有辦法消除這個(gè)對(duì)比的過程呢祭埂？

哈希表就是解決查詢問題的一種方案。在后續(xù)將會(huì)分析的二叉排序樹中兵钮，還會(huì)將數(shù)據(jù)排序以進(jìn)行二分查找蛆橡，將時(shí)間復(fù)雜度從O(n)降低到O(lg n)。

哈希表與Hash函數(shù)

通俗來講矢空，哈希表就是通過關(guān)鍵字來獲取數(shù)據(jù)的一種數(shù)據(jù)結(jié)構(gòu)航罗，它通過把關(guān)鍵字映射為表中的位置來獲取元素，這種映射主要是使用Hash函數(shù)屁药。

Hash函數(shù)粥血，實(shí)際上是建立起key值與int值映射關(guān)系的函數(shù)。這就好比我們每個(gè)人都有一個(gè)身份證號(hào)一樣酿箭，無論是男是女复亏，出生在何處，都可以通過身份證號(hào)來分辨缭嫡，這就是把人的信息映射成一串?dāng)?shù)字的典型做法缔御。Hash函數(shù)和此類似，不過是把任意的Java對(duì)象妇蛀，映射成一個(gè)int數(shù)值耕突，供哈希表使用。

而哈希表评架，就是一個(gè)數(shù)組眷茁，只是其元素不是按照數(shù)組的規(guī)則排列的。任何一個(gè)元素要放進(jìn)哈希表中纵诞，都必須先通過Hash函數(shù)獲取到一個(gè)int數(shù)值上祈，這個(gè)數(shù)值經(jīng)過處理后將作為它的存放位置，然后這個(gè)元素才能放進(jìn)哈希表中浙芙。

可以發(fā)現(xiàn)登刺，數(shù)組與哈希表的操作不同之處主要在于，前者是直接插入嗡呼，后者需要通過Hash函數(shù)計(jì)算后再插入纸俭。可以通過下圖對(duì)比來理解：

數(shù)組的插入

哈希表的插入

哈希表完全繼承了數(shù)組的優(yōu)點(diǎn)南窗，又顯著的提高了查詢的速度揍很，通過Hash函數(shù)使得查詢速度達(dá)到了O(1)廊宪。既然有了哈希表，它這么優(yōu)秀女轿，為何還需要數(shù)組的存在呢箭启？那是因?yàn)镠ash表是有缺陷的，這個(gè)缺陷就是哈希碰撞蛉迹。

哈希碰撞

Hash函數(shù)所做的事傅寡，就是無論什么對(duì)象，都根據(jù)一個(gè)規(guī)則映射為一個(gè)int值北救。被轉(zhuǎn)換的對(duì)象有無數(shù)種可能荐操，但是int的值是有限的，它只有2³²個(gè)珍策，這樣一來托启，必然會(huì)有不同的對(duì)象，映射得到相同的int值攘宙，這就是所謂的哈希碰撞屯耸。發(fā)生碰撞之后，就要把不同的元素插入到相同的位置蹭劈，這時(shí)候單純的使用一維數(shù)組已經(jīng)無法滿足需求了疗绣。

解決哈希碰撞的方法

要解決哈希碰撞，我們可以想到多種解決方案铺韧。例如使用二維數(shù)組多矮，將碰撞的元素按順序存儲(chǔ)起來，類似下圖：

二維數(shù)組存儲(chǔ)

這樣的方式有一個(gè)很大的詬病哈打，因?yàn)閿?shù)組大小是固定的塔逃，所以第二維的數(shù)組長(zhǎng)度都是一樣的，但是哈希碰撞一定是比較少發(fā)生的情況料仗，也就是我們聲明了一個(gè)很大的數(shù)組湾盗，但是其中大部分都是閑置的，這就浪費(fèi)了大量的內(nèi)存罢维。

還有一些方案是考慮了哈希表的散列化淹仑，將元素插入到空閑的位置去丙挽。因?yàn)楣１砘静粫?huì)像數(shù)組一樣每個(gè)位置都有元素肺孵，這樣就可以將碰撞的元素插入到這些空閑的位置中區(qū)，這種方案稱為定址法颜阐。但是這個(gè)方法在擴(kuò)展性上表現(xiàn)不佳平窘，我們這里就不再浪費(fèi)篇幅來解釋它了。

目前比較通用的方法凳怨，就是使用數(shù)組+鏈表組合的方式瑰艘。當(dāng)出現(xiàn)哈希碰撞時(shí)是鬼，在該位置的數(shù)據(jù)就通過鏈表的方式鏈接起來，如下圖所示：

哈希表的結(jié)構(gòu)示意圖

這是當(dāng)前比較理想的方法紫新，既繼承了數(shù)組的優(yōu)點(diǎn)均蜜，又在碰撞時(shí)繼承了鏈表的優(yōu)點(diǎn)，這也是哈希表強(qiáng)大的地方之一芒率。

在JDK1.7及之前的版本中囤耳，HashMap的存儲(chǔ)結(jié)構(gòu)和上圖是一致的，在JDK1.8之后還加入了紅黑樹以進(jìn)一步優(yōu)化偶芍，在后續(xù)文章中我們會(huì)對(duì)其進(jìn)行詳盡的分析充择。

哈希表的優(yōu)缺點(diǎn)

哈希表是一種優(yōu)化存儲(chǔ)的思想，具體存儲(chǔ)元素的依然是其他的數(shù)據(jù)結(jié)構(gòu)匪蟀。設(shè)計(jì)良好的哈希表椎麦，能同時(shí)兼?zhèn)鋽?shù)組和鏈表的優(yōu)點(diǎn)，它能在插入和查找時(shí)都具備良好的性能材彪。然而設(shè)計(jì)不好的哈希表观挎，有可能會(huì)出現(xiàn)較多的哈希碰撞，導(dǎo)致鏈表過長(zhǎng)段化，從而哈希表會(huì)更像一個(gè)鏈表键兜。還有當(dāng)數(shù)據(jù)量很大時(shí)，為防止鏈表過長(zhǎng)穗泵，就需要對(duì)數(shù)組進(jìn)行擴(kuò)容普气，這時(shí)就涉及到了數(shù)組的拷貝，其對(duì)性能的影響也很嚴(yán)重佃延，所以需要提前對(duì)可能的情況有良好的預(yù)測(cè)现诀，才能真正發(fā)揮哈希表的優(yōu)勢(shì)。

上一篇：Java集合源碼分析之基礎(chǔ)（一）：數(shù)組與鏈表

下一篇：Java集合源碼分析之基礎(chǔ)（三）：樹與二叉樹

我是飛機(jī)醬履肃，如果您喜歡我的文章仔沿，可以關(guān)注我~

編程之路，道阻且長(zhǎng)尺棋。唯封锉，路漫漫其修遠(yuǎn)兮，吾將上下而求索膘螟。