HashMap 一直是非常常用的數(shù)據(jù)結構,也是面試中十分常問到的集合類型床估,今天就來說說 HashMap。
但是為什么要專門說明是 Java8 的 HashMap 呢?我們都知道蛋欣,Java8 有很多大的變化和改動,如函數(shù)式編程等如贷,而 HashMap 也有了一個比較大的變化陷虎。
先了解一下 Map
常見的Map類型有以下幾種:
HashMap:
- 無序
- 訪問速度快
- key不允許重復(只允許存在一個null key)
LinkedHashMap:
- 有序
- HashMap 子類
TreeMap:
- TreeMap 中保存的記錄會根據(jù) Key 排序(默認為升序排序),因此使用 Iterator 遍歷時得到的記錄是排過序的
- 因為需要排序杠袱,所以TreeMap 中的 key 必須實現(xiàn) Comparable 接口尚猿,否則會報 ClassCastException 異常
- TreeMap 會按照其 key 的 compareTo 方法來判斷 key 是否重復
除了上面幾種以外,我們還可能看到過一個叫 Hashtable 的類:
Hashtable:
- 一個遺留類楣富,線程安全凿掂,與 HashMap 類似
- 當不需要線程安全時,選擇 HashMap 代替
- 當需要線程安全時纹蝴,使用 ConcurrentHashMap 代替
HashMap
我們現(xiàn)在來正式看一下 HashMap
首先先了解一下 HashMap 內部的一些主要特點:
- 使用哈希表(散列表)來進行數(shù)據(jù)存儲庄萎,并使用鏈地址法來解決沖突
- 當鏈表長度大于等于 8 時,將鏈表轉換為紅黑樹來存儲
- 每次進行二次冪的擴容塘安,即擴容為原容量的兩倍
字段
HashMap 有以下幾個字段:
- Node[] table:存儲數(shù)據(jù)的哈希表糠涛;初始長度 length = 16(
DEFAULT_INITIAL_CAPACITY
),擴容時容量為原先的兩倍(n * 2) - final float loadFactor:負載因子兼犯,確定數(shù)組長度與當前所能存儲的鍵值對最大值的關系脱羡;不建議輕易修改,除非情況特殊
- int threshold:所能容納的 key-value 對極限 免都;threshold = length * Load factor锉罐,當存在的鍵值對大于該值,則進行擴容
- int modCount:HashMap 結構修改次數(shù)(例如每次 put 新值使則自增 1)
- int size:當前 key-value 個數(shù)
方法
hash(Object key)
我們都知道绕娘,Object 類的 hashCode 方法與 HashMap 息息相關脓规,因為 HashMap 便是通過 hashCode 來確定一個 key 在數(shù)組中的存儲位置。(這里大家都應該了解一下 hashCode 與 equals 方法之間的關系與約定险领,這里就不多說了)
但值得注意的是侨舆,HashMap 并非直接使用 hashCode 作為哈希值,而是通過這里的 hash 方法對 hashCode 進行一系列的移位和異或處理绢陌,這樣處理的目的是為了有效地避免哈希碰撞
當然挨下,Java 8 之前的做法和現(xiàn)在的有所不同,Java 8 對此進行了改進脐湾,優(yōu)化了該算法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
put(K key, V value)
put 方法是 HashMap 里面一個十分核心的方法臭笆,關系到了 HashMap 對數(shù)據(jù)的存儲問題。
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
put 方法直接調用了 putVal 方法,這里我為大家加上了注釋愁铺,可以配合下面的流程圖一步步感受:
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
HashMap.Node<K, V>[] tab;
HashMap.Node<K, V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
//初始化哈希表
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//通過哈希值找到對應的位置鹰霍,如果該位置還沒有元素存在,直接插入
tab[i] = newNode(hash, key, value, null);
else {
HashMap.Node<K, V> e;
K k;
//如果該位置的元素的 key 與之相等茵乱,則直接到后面重新賦值
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof HashMap.TreeNode)
//如果當前節(jié)點為樹節(jié)點茂洒,則將元素插入紅黑樹中
e = ((HashMap.TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);
else {
//否則一步步遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//插入元素到鏈尾
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1)
//元素個數(shù)大于等于 8,改造為紅黑樹
treeifyBin(tab, hash);
break;
}
//如果該位置的元素的 key 與之相等瓶竭,則重新賦值
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//前面當哈希表中存在當前key時對e進行了賦值督勺,這里統(tǒng)一對該key重新賦值更新
if (e != null) {
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//檢查是否超出 threshold 限制,是則進行擴容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
主要的邏輯步驟在此:
有個值得注意的有趣的地方:在 Java 8 之前斤贰,HashMap 插入數(shù)據(jù)時一直是插入到鏈表表頭玷氏;而到了 Java 8 之后,則改為了尾部插入腋舌。至于頭插入有什么缺點盏触,其中一個就是在并發(fā)的情況下因為插入而進行擴容時可能會出現(xiàn)鏈表環(huán)而發(fā)生死循環(huán);當然块饺,HashMap 設計出來本身就不是用于并發(fā)的情況的赞辩。
(1)懶加載
我們在 HashMap 的構造函數(shù)中可以發(fā)現(xiàn),哈希表 Node[] table 并沒有在一開始就完成初始化授艰;觀察 put 方法可以發(fā)現(xiàn):
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
當發(fā)現(xiàn)哈希表為空或者長度為 0 時辨嗽,會使用 resize 方法進行初始化,這里很顯然運用了 lazy-load 原則淮腾,當哈希表被首次使用時糟需,才進行初始化
(2)樹化
Java8 中,HashMap 最大的變動就是增加了樹化處理谷朝,當鏈表中元素大于等于 8洲押,這時有可能將鏈表改造為紅黑樹的數(shù)據(jù)結構,為什么我這里說可能呢?
final void treeifyBin(HashMap.Node<K,V>[] tab, int hash) {
int n, index; HashMap.Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
//......
}
我們可以觀察樹化處理的方法 treeifyBin圆凰,發(fā)現(xiàn)當tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY
為 true 時杈帐,只會進行擴容處理,而沒有進行樹化专钉;MIN_TREEIFY_CAPACITY 規(guī)定了 HashMap 可以樹化的最小表容量為 64挑童,這是為了避免在哈希表建立初期,多個鍵值對恰好被放入了同一個鏈表中而導致不必要的轉化跃须。
那么站叼,HashMap 為什么要進行樹化呢?我們都知道菇民,鏈表的查詢效率大大低于數(shù)組尽楔,而當過多的元素連成鏈表投储,會大大降低查詢存取的性能;同時翔试,這也涉及到了一個安全問題轻要,一些代碼可以利用能夠造成哈希沖突的數(shù)據(jù)對系統(tǒng)進行攻擊复旬,這會導致服務端 CPU 被大量占用垦缅。
resize()
擴容方法同樣是 HashMap 中十分核心的方法,同時也是比較耗性能的操作驹碍。
我們都知道數(shù)組是無法自動擴容的壁涎,所以我們需要重新計算新的容量,創(chuàng)建新的數(shù)組志秃,并將所有元素拷貝到新數(shù)組中怔球,并釋放舊數(shù)組的數(shù)據(jù)。
與以往不同的是浮还,Java8 規(guī)定了 HashMap 每次擴容都為之前的兩倍(n*2)竟坛,也正是因為如此,每個元素在數(shù)組中的新的索引位置只可能是兩種情況钧舌,一種為不變担汤,一種為原位置 + 擴容長度(即偏移值為擴容長度大小)洼冻;反觀 Java8 之前崭歧,每次擴容需要重新計算每個值在數(shù)組中的索引位置,增加了性能消耗
接下來簡單給大家說明一下撞牢,上一段話是什么意思: 前面講 put 的時候我們知道每個元素在哈希表數(shù)組中的位置等于 (n - 1) & hash率碾,其中 n 是當前數(shù)組的大小,hash 則是前面講到的 hash 方法計算出來的哈希值
圖中我們可以看到屋彪,擴容前 0001 0101 和 0000 0101 兩個 hash 值最終的計算出來的數(shù)組中的位置都是 0000 0101所宰,即為 5,此時數(shù)組大小為 0000 1111 + 1 即 16
擴容后畜挥,數(shù)組從 16 擴容為兩倍即 32(0001 1111)歧匈,此時原先兩個 hash 值計算出來的結果分別為 0001 0101 和 0000 0101 即 21 和 5,兩個數(shù)之間剛好相差 16砰嘁,即數(shù)組的擴容大小
這個其實很容易理解件炉,數(shù)組擴容為原來的兩倍后,n - 1 改變?yōu)?2n - 1矮湘,即在原先的二進制的最高位發(fā)生了變化
因此進行 & 運算后斟冕,出來的結果只可能是兩種情況,一種是毫無影響缅阳,一種為原位置 + 擴容長度
那么源代碼中是如何判斷是這兩種情況的哪一種呢磕蛇?我們前面說到景描,HashMap 中數(shù)組的大小始終為 16 的倍數(shù),因此 hash & n 和 hash & (2n - 1) 分別計算出來的值中高位是相等的
因此源碼中使用了一個非常簡單的方法(oldCap 是原數(shù)組的大小秀撇,即 n)
if ((e.hash & oldCap) == 0) {
...
} else {
...
}
當 e.hash & oldCap 等于 0 時超棺,元素位置不變,當非 0 時呵燕,位置為原位置 + 擴容長度
get(Object key)
了解了 HashMap 的存儲機制后棠绘,get 方法也很好理解了
final HashMap.Node<K,V> getNode(int hash, Object key) {
HashMap.Node<K,V>[] tab; HashMap.Node<K,V> first, e; int n; K k;
if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) {
//檢查當前位置的第一個元素,如果正好是該元素再扭,則直接返回
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
//否則檢查是否為樹節(jié)點氧苍,則調用 getTreeNode 方法獲取樹節(jié)點
if (first instanceof HashMap.TreeNode)
return ((HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
//遍歷整個鏈表,尋找目標元素
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
主要就四步:
- 哈希表是否為空或者目標位置是否存在元素
- 是否為第一個元素
- 如果是樹節(jié)點泛范,尋找目標樹節(jié)點
- 如果是鏈表結點让虐,遍歷鏈表尋找目標結點
需要資料和視頻資料的朋友,歡迎加群找群主要資料喲
群: 957734884