概述
HashMap是在JDK1.2中引入的一種K/V對形式的集合類.
在底層,HashMap通過數組和單鏈表組合的結構形式來存儲數據,數組在這作為一個外部結構,數組中的每個節點被稱做Bucket(桶),而桶是由在單鏈表構成,JDK1.8之後為了解決長鏈表下,查詢和插入效率低下的情況,又引入了紅黑樹的作為桶的實現方式,
桶中的各節點是由HashMap定義的Node內部類生成的,是普通的鏈表節點類.
注意:HashMap是線程不安全的,在JDK1.8之前多線程情況下甚至可能會出現環路(後面會講),所以多線程狀態下還是要使用ConcurrentHashMap的.
重點參數
HashMap的參數不多,除去當做默認屬性的靜態常量和底層數組對象,就只有以下五個
transient Node[] table; transient int size transient int modCount; int threshold; final float loadFactor;
table就是整個HashMap的底層數組,table的初始化並不在構造函數中完成,而是在resize()方法中完成.
table的初始化可能有點繞,構造函數中最多指定了閾值threshold和負載因子loadFactor並沒有容量相關,但是在resize()方法中會根據舊容量和舊閾值判斷新容量是等於默認容量,舊閾值或者兩倍舊容量,最後根據新容量創建新數組
loadFactor就是所謂的負載因子,默認為0.75,是控制擴容時機的關鍵屬性,因為擴容發生在當前元素個數超過閾值時,而閾值等於當前容量乘以負載因子.
modCount為修改計數,是fast-fail機制的關鍵參數.在對Map中的元素做新增/刪除操作時會自增,但修改不會(putVal()方法中覆蓋原值)
新增邏輯
- HashMap的新增過程重點主要還是定位,如何確定元素在數組中的位置,HashMap採用的就是Hash算法首先HashMap會根據Key的hash值,按照表達式(n - 1) & hash計算出桶的下標
- 如果此時桶為空,會創建一個新的Node,作為鏈表的第一個元素,直接存放在數組中.(以前還聽說過什麼鏈表首節點為空的情況,是假的.)
- 如果節點存在又會區分樹節點(TreeNode)和普通節點(Node)兩種情況.
普通節點會直接從首節點往下遍歷找到尾節點,並將帶插入節點添加到末尾
樹節點會調用,TreeNode的方法插入到樹中.
另外新增前會判斷底層數組table是否初始化,新增後會判斷該桶大小是否超過的8,超過則轉化為紅黑樹,再判斷整個數組是否需要擴容.
Hash同時也叫散列,可以把任意長度的輸入通過算法,換算成固定長度的輸出,不同元素通過Hash算法獲得的下標一致可以被稱之為衝突或者碰撞,Hash算法的要求就是使元素儘量少的發生碰撞,從而均勻的散佈在數組中.而發生碰撞時,像HashMap這種以一個列表下掛的方式可以被稱為拉鍊法.
查找邏輯
此處的查找邏輯是指調用get()方法,通過key值查找的情況,如果自己遍歷的另說.
- 同樣是根據表達式(n - 1) & hash計算出桶的下標(可以說是相當重要了),若得到的桶為空,直接返回null
- 不為空時則會遍歷整個桶,並根據key.equals(k)判斷是否相等
- 遍歷的方法也會根據節點類型的不同而不同,但是區分節點前直接存放在數組中的頭結點是要先進行判斷的.感覺上性能影響不大吧
從查找的過程可以看出,確定桶下標的計算不存在隨機性,時間複雜度就為O(1),具體的性能體現在遍歷這一塊,鏈表查詢的時間複雜度為O(n),所以鏈表越長遍歷時間也就越長,插入和查找的效率也就越低.所以在JDK1.8之後引入的紅黑樹作為桶的另一種實現方法.當鏈表長度大於8時,桶的實現會轉化為紅黑樹.
HashMap的性能很大一部分取決於Hash算法..
RESIZE邏輯
通過插入和查找我們可以知道,在數組大小不變的情況下,鏈表越長或者說樹的高度越高都會導致操作性能降低,所以此時很有必要通過擴容數組的方式,重新排列桶中元素,降低鏈表長度,減少樹的高度.
首先,觸發擴容的情況是size > threshold即元素個數大於閾值.整個擴容過程可以簡單的拆分為以下幾步:
- 對數組進行擴充,一般情況下是數組容量和閾值都變為原來的兩倍,此間會有上限判斷,容量最大為1 << 30也就是2^30.
- 遍歷舊數組,重新判斷元素的位置並散佈到新數組.
resize()方法中重新散佈元素的方法還是很有意思的(除去單元素鏈表和紅黑樹(桶的容量在1~7之間)
首先將新數組分為兩部分lo和hi(源碼是loHead和hiHead,我猜是low和high,怎麼縮寫這麼隨意),lo表示0到舊容量大小部分,hi表示餘下算是新加入的部分,並以此創建兩個鏈表的節點
根據表達式e.hash & oldCap判斷元素是否分佈在lo部分,是就掛到lo鏈表下面,否就掛到hi鏈表下面.
lo鏈表掛到和舊數組相同位置的桶,而hi則掛到下標為原下標 + 舊數組容量的桶.
此處的依據就是e.hash & (oldCap - 1) + oldCap == e.hash & (oldCap << 1) -1
可以看出resize()方法會調整全部的元素散列情況,因此過於頻繁的resize會降低HashMap的性能,因此如果一開始可以大概知道所需要存放的元素個數時,儘量直接指定容量大小.
JDK1.7之前的resize()方法在併發條件下可能會發生閉環問題,但在JDK1.8之後不會在出現,但並不代表HashMap可以在併發條件下使用了,小部分情況還是會出現數據丟失等問題.
HashMap的懶加載問題
查看HashMap的源碼，你會發現底層數組table的創建其實並不是在構造函數中完成的，而是resize()方法中,這就是所謂的懶加載,數組對象並非是在一開始就創建的，而是在第一次插入操作之前完成的。
關於HashMap一些問題
擾動函數
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
擾動函數的邏輯很簡單就是將hashCode的高16位和低16位異或.
擾動函數的作用就是增加散列的隨機性,使元素能夠更均勻的分佈在數組中,減少衝突從而捎帶提高性能.
至於為什麼,可以看hash(*)用到的地方,hash(*)被用來計算元素的下標.而下標的計算公式如下
tab[i = (n - 1) & hash] // n表示數組的長度
因為HashMap的容量一定會是2的次冪,所以減1之後轉化為二進制會變為一串0加一串1的,例如長度為4時,減去1,就會變為000…00011(前面30個0),再結合&可以發現他只使用了hashCode的末尾幾位,高位是全部沒用.
而經過擾動函數,將高16位和低16位異或之後相當於高低位都用到了,其散列的隨機性也就增加了.
HashMap的容量為什麼一定要是2的次冪
容量為2次冪有兩個優點
- 在下標運算的時候使用(length - 1) & hash)代替hash % length，相對來說位運算性能更佳，速度更快。
- 而在採用(length - 1) & hash的方式計算下標之後，如果不是二次冪的容量，出現碰撞的幾率將會大大增加，例如我們取17作為容量((17 -1) => 0001000)，經過&與運算，可以想象會有一大批的元素直接掛在0號桶。
可以說這是一整套的策略，如果使用hash & length的話，也不用要求容量一定是二次冪，但各方面的性能總是會差一點的。
HashMap和HashTable的區別
- 最大的區別就是HashTable是線程安全的,暴力的加方法級synchronized.而HashMap是線程不安全的,併發情況下可能會出現數據丟失等情況.
- HashTable不允許null值,而HashMap允許null值.(包括key和value)
- HashCode的使用不同,HashTable是直接調用hashCode,而HashMap會經過擾動函數.而且HashMap中用&代替了%
- HashTable數組默認是11,且增長為2n+1,而HashMap默認為16,增長為2n,且硬性要求長度為2的次冪.
- HashTable並不是和HashMap一樣繼承自AbstractMap的,它繼承自一個獨立的父類AbstractDictionary
- 還有就是遍歷方法的不同.瞭解不深先不說話.
作者：孤酒
鏈接：https://juejin.im/post/5c0cd04de51d451dac076cc9
來源：掘金
感謝您的觀看，喜歡的小夥伴可以點個贊！！！專注Java、大數據知識乾貨及相關領域動態分享，請多多關注哦！
