原創(chuàng)作品，轉(zhuǎn)載請注明出處。
概述
本文學(xué)習(xí)知識點(diǎn)
1.HashMap的存儲結(jié)構(gòu)怎么實(shí)現(xiàn),它有什么特點(diǎn)。
2.HashMap的工作原理。
3.put和get方法實(shí)現(xiàn)源碼分析。
4.hash值有什么作用？如何進(jìn)行hash？equals和hashCode方法有什么作用?
5.何謂負(fù)載因子，有什么作用?
6.何時會觸發(fā)擴(kuò)容，以及如何擴(kuò)容？
Map<String, String> map = new HashMap<String, String>();
map.put("liuyi", "劉一");
map.put("wanger", "王二");
map.put("zhangsan", "張三");
map.put("lisi", "李四");
map.put("wangwu", "王五");
map.put("zhaoliu", "趙六");
map.put("chenqi", "陳七");
map.put("yangba", "楊八");
map.put("zhoujiu", "周九");
for (Map.Entry<String, String> entry : map.entrySet()) {
System.out.println(entry.getValue() + "\t" + entry.getKey());
}
想想上面代碼的輸出結(jié)果是什么樣？運(yùn)行后，可能的結(jié)果是：
趙六 zhaoliu
劉一 liuyi
王五 wangwu
王二 wanger
陳七 chenqi
李四 lisi
周九 zhoujiu
張三 zhangsan
楊八 yangba
從這個結(jié)果可以窺探出，HashMap存儲的順序和迭代時讀取的順序不相同，并非有序存儲。來看看底層如何存儲，如下圖為Eclipse debug時的存儲結(jié)構(gòu)：
從圖中來看，HashMap內(nèi)部用一個table（Entry元素數(shù)組）來存儲元素，索引中的每個元素又采用鏈表的結(jié)構(gòu)進(jìn)行存儲，用于存儲相同索引的元素。其中Entry類就是一個節(jié)點(diǎn)類，具有鏈接下一個節(jié)點(diǎn)的功能，內(nèi)部存儲了元素的key,value,hash,next引用，Entry的結(jié)構(gòu)如下，采用內(nèi)部類的方式實(shí)現(xiàn)：
HashMap的特性
1.實(shí)現(xiàn)了Map接口，里面的方法全部被HashMap實(shí)現(xiàn)。
2.允許null鍵和null值。這點(diǎn)和Hashtable不同，Hashtable不允許。
3.非線程安全，這點(diǎn)也和Hashtable不同，Hashtable為線程安全的。
4.不保證有序，即元素的插入和讀取順序不保證一致，這一點(diǎn)從開始的示例程序和圖就能看出來。
5.也不保證元素的順序始終不變，在擴(kuò)容時，元素的順序會重新被打亂。
有兩個參數(shù)能夠影響HashMap的結(jié)構(gòu)：
1.initial capacity：table的初始容量（并非存放元素節(jié)點(diǎn)的容量大小，僅僅是table表的大?。J(rèn)初始容量為16。
2.load factor：負(fù)載因子，用于確定table的容量達(dá)到多大比例時，對容量進(jìn)行擴(kuò)容的一個參數(shù)。默認(rèn)值為0.75，即默認(rèn)超過12個時開始擴(kuò)容，擴(kuò)容時，會重新計算所有元素的hash值(rehashed)，以確定其在新table上的索引下標(biāo)，因此，擴(kuò)容會改變原有hashtable的結(jié)構(gòu)，元素的順序也會重新改變。每次擴(kuò)容后，容量的大小都是原來的2倍。至于為什么默認(rèn)負(fù)載因子設(shè)置為0.75，按照官方的API說法，是因?yàn)橥ǔ?.75能夠在時間復(fù)雜度和空間復(fù)雜度上達(dá)到最好的平衡效果。在設(shè)置初始容量時應(yīng)該考慮到所需的條目數(shù)及其加載因子，以便最大限度地減少 rehash 操作次數(shù)。
put方法的實(shí)現(xiàn) JDK1.7
put方法的步驟：
1.對key的hashcode值再計算hash。
2.用計算出的hash值，與表的length求&算出索引位置。
3.如果索引碰撞，遍歷鏈表，判斷是否有key存在，若存在更新value值。（不過在JDK1.8中鏈表元素超過8個時，會把鏈表結(jié)構(gòu)轉(zhuǎn)換成紅黑樹結(jié)構(gòu)存儲，提高查詢的性能）
4.若未碰撞，直接放入表中。
5.放入前，如果元素個數(shù)超過負(fù)載因子的比例，則進(jìn)行rehash，擴(kuò)容，之會插入。
6.null key的元素永遠(yuǎn)會放到index為0的鏈表里面。
get方法實(shí)現(xiàn)
步驟：
1.null key走特殊邏輯。
2.key的hashcode計算hash值。
3.hash值計算表索引。
4.遍歷索引下的鏈表，找到就返回，找不到返回null。
hash方法的實(shí)現(xiàn)
如下為hash方法的實(shí)現(xiàn)源碼：
hash方法中：對key的hashCode值進(jìn)行了異或，邏輯右移等多個操作，目的是盡量減小沖突。因?yàn)閠able的容量是2的冪，直接用hashcode，低位會很容易碰撞，因此做了多次移位和異或操作，保證高位和低位都參與到hash的計算中，減少碰撞。
計算下標(biāo)的時候，是這樣實(shí)現(xiàn)的(使用&位操作，而非%求余)：
hash & (length - 1)
設(shè)計者認(rèn)為這方法很容易發(fā)生碰撞。為什么這么說呢？不妨思考一下，在n - 1為15(0x1111)時，其實(shí)散列真正生效的只是低4bit的有效位，當(dāng)然容易碰撞了。
時間復(fù)雜度：讀取O(1) + O(n)，1為找索引的時間，n為鏈表元素的個數(shù)。插入O(1)。所以，如果沖突很頻繁，某些鏈表非常長，就會影響HashMap的讀取速度。這一點(diǎn)在JDK1.8中進(jìn)行了性能提升，鏈表長度超過8則改為紅黑樹的存儲結(jié)構(gòu)實(shí)現(xiàn)。
resize擴(kuò)容實(shí)現(xiàn)
實(shí)現(xiàn)如下：
步驟：
1.創(chuàng)建新的table。
2.將舊table的元素重新計算hash，根據(jù)hash計算新table的索引，插入新table。
3.新table覆蓋原table的引用，更新threshold值為新table * 負(fù)載因子的大小。
總結(jié)
讓我們來回答幾個問題，以加深對HashMap的理解：
1. 什么時候會使用HashMap？他有什么特點(diǎn)？
是基于Map接口的實(shí)現(xiàn)，存儲鍵值對時，它可以接收null的鍵值，是非同步的，HashMap存儲著Entry(hash, key, value, next)對象。
2. 你知道HashMap的工作原理嗎？
通過put和get存儲和獲取對象。存儲對象時，我們將K/V傳給put方法時，它調(diào)用hashCode計算hash從而得到table位置，進(jìn)一步存儲，HashMap會根據(jù)當(dāng)前table的占用情況自動調(diào)整容量(超過Load Facotr則resize為原來的2倍)。獲取對象時，我們將K傳給get，它調(diào)用hashCode計算hash從而得到table位置，并進(jìn)一步調(diào)用equals()方法確定鍵值對。如果發(fā)生碰撞的時候，Hashmap通過鏈表將產(chǎn)生碰撞沖突的元素組織起來，在Java 8中，如果一個table中碰撞沖突的元素超過某個限制(默認(rèn)是8)，則使用紅黑樹來替換鏈表，從而提高速度。
3. 你知道get和put的原理嗎？equals()和hashCode()的都有什么作用？
通過對key的hashCode()進(jìn)行hashing，并計算下標(biāo)( n-1 & hash)，從而獲得buckets的位置。如果產(chǎn)生碰撞，則利用key.equals()方法去鏈表或樹中去查找對應(yīng)的節(jié)點(diǎn)
4. 你知道hash的實(shí)現(xiàn)嗎？為什么要這樣實(shí)現(xiàn)？
在Java 1.8的實(shí)現(xiàn)中，是通過hashCode()的高16位異或低16位實(shí)現(xiàn)的：(h = k.hashCode()) ^ (h >>> 16)，主要是從速度、功效、質(zhì)量來考慮的，這么做可以在bucket的n比較小的時候，也能保證考慮到高低bit都參與到hash的計算中，同時不會有太大的開銷。
5. 何時會觸發(fā)擴(kuò)容，以及如何擴(kuò)容？
如果table超過了負(fù)載因子(默認(rèn)0.75)比例的容量，則會重新resize一個原來長度兩倍的HashMap，并且重新調(diào)用hash方法計算元素在新table的索引，并挨個插入。
白天在加班加點(diǎn)的干活，還要抽出時間成為技術(shù)知識的分享者，分享不易。
喜歡我的文章請點(diǎn)贊，歡迎打賞，成為我們堅持的動力。
