HashMap是Java使用頻率很高的容器對(duì)象,內(nèi)部使用了很多優(yōu)化算法,源碼非常值得學(xué)習(xí).
關(guān)于HashMap
- 非線程安全
HashTable對(duì)put和get使用了synchronized關(guān)鍵字,線程安全,但是已經(jīng)被廢棄,ConcurrentHashMap是推薦使用的線程安全,高并發(fā)Map實(shí)現(xiàn)
- key-value存儲(chǔ)
- key和value都可以為null,多個(gè)為null的key會(huì)被后面的覆蓋
- key要求為不可變對(duì)象(引用類型必須重寫hashCode和equals方法)
為了確保同一個(gè)對(duì)象的hash計(jì)算后的值唯一,不同的對(duì)象hash計(jì)算后的值一定不等.
- HashMap內(nèi)部存儲(chǔ)結(jié)構(gòu)為數(shù)組+鏈表+紅黑樹(shù)(JDK1.8開(kāi)始)
HashMap存儲(chǔ)結(jié)構(gòu)
在HashMap內(nèi)部,有一個(gè)Node[] table 字段,Node類型就是數(shù)據(jù)保存在HashMap內(nèi)部時(shí)的實(shí)際對(duì)象,Node實(shí)現(xiàn)Map.Entry接口,本質(zhì)就是一個(gè)鍵值對(duì),Node對(duì)象會(huì)持有下一個(gè)結(jié)點(diǎn)的引用,由此可知Node對(duì)象又維護(hù)了一個(gè)單向鏈表.
//HashMap中Node對(duì)象
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {...}
...
}
HashMap使用哈希表的意義
HashMap使用了哈希表來(lái)存儲(chǔ),當(dāng)key值哈希沖突之后使用鏈表保存沖突的值,當(dāng)數(shù)據(jù)哈希計(jì)算之后得到數(shù)組下標(biāo),把數(shù)據(jù)放在對(duì)應(yīng)下標(biāo)的鏈表上.
Map<String,Integer> map = new HashMap<>();
map.put("key",123);
使用hash算法是為了盡量減少hash沖突,如果默認(rèn)的node數(shù)組很大,那么發(fā)生沖突的幾率也會(huì)減小,但是會(huì)浪費(fèi)很多的內(nèi)存空間,為了平衡效率和空間,HashMap采用了負(fù)載因子(loadFactor)和擴(kuò)容提高空間使用率,提高存取效率.075是對(duì)空間和時(shí)間效率的一個(gè)平衡選擇,不建議自行修改,除非對(duì)內(nèi)存和時(shí)間效率有取舍有要求時(shí)才會(huì)進(jìn)行修改.
負(fù)載因子的作用是控制HashMap擴(kuò)容的時(shí)機(jī),默認(rèn)為0.75,HashMap初始的table大小為16.
簡(jiǎn)單來(lái)說(shuō) : 當(dāng)存儲(chǔ)數(shù)量>table.length*0.75時(shí),就會(huì)觸發(fā)HashMap擴(kuò)容
//HashMap成員變量
//默認(rèn)負(fù)載因子為0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//默認(rèn)桶的大小,1左移4位,就是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4
根據(jù)上面這段注釋,可以知道HashMap內(nèi)部的數(shù)組只有在第一次使用的時(shí)候才會(huì)被初始化,在必要的時(shí)候會(huì)進(jìn)行擴(kuò)容,而且數(shù)組的長(zhǎng)度總是2的n次方數(shù),使用2的n次方的原因是為了在模運(yùn)算和擴(kuò)容是進(jìn)行優(yōu)化,同時(shí)為了減少?zèng)_突,HashMap定位哈希桶索引位置時(shí),使用了高位運(yùn)算.
HashMap使用了很多的算法和優(yōu)化提高性能,但是當(dāng)數(shù)據(jù)量很大時(shí),哈希沖突無(wú)法避免,使用鏈表會(huì)導(dǎo)致數(shù)據(jù)的查找性能急劇下降,所以在JDK1.8加入了紅黑樹(shù),當(dāng)鏈表長(zhǎng)度達(dá)到8時(shí).鏈表會(huì)轉(zhuǎn)為紅黑樹(shù),利用紅黑樹(shù)快速增刪改查的特點(diǎn)提高HashMap的性能.
由于紅黑樹(shù)是另一個(gè)知識(shí)點(diǎn),不會(huì)在HashMap的小結(jié)中出現(xiàn).
功能實(shí)現(xiàn)-方法
HashMap的內(nèi)部實(shí)現(xiàn)了很多算法和功能,其中三個(gè)最具有代表性的方法是:根據(jù)key計(jì)算哈希桶數(shù)組索引下標(biāo),put方法,擴(kuò)容.所以對(duì)這三個(gè)方法進(jìn)行深入.
1.確定哈希桶數(shù)組索引位置
不管增刪改查,第一步操作都是根據(jù)key的hash值獲取key在哈希桶中的下標(biāo).由于HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組+鏈表,由于數(shù)組的訪問(wèn)速度是最快的,所以應(yīng)該盡量將存入的元素分布在不同的數(shù)組下標(biāo)中,使得每個(gè)位置上的元素只有一個(gè),當(dāng)使用hash算法求得這個(gè)位置的時(shí)候,對(duì)應(yīng)下標(biāo)的元素就是所需元素,不需要遍歷該位置上的鏈表,所以查詢效率會(huì)很高.
數(shù)組在在內(nèi)存中是連續(xù)的,所以查詢效率是最高的,而鏈表是不連續(xù)的內(nèi)存空間,每一次查詢都需要遍歷鏈表.
確定下標(biāo)的步驟:
- 步驟1
- 取key的hashCode
- key的hashCode無(wú)符號(hào)右移16位
- 右移后的值與右移前的值做與運(yùn)算.
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- 步驟2
- 將調(diào)用hash(Object key)方法后獲取的值和哈希桶長(zhǎng)度-1做與運(yùn)算
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
int n ;
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
...
}
這里就是hash算法確定下標(biāo)的算法,本質(zhì)上的流程為:取key的hashCode值送朱、高位運(yùn)算邪蛔、取模運(yùn)算滞谢。
由于HashMap使用了hashCode,所以只要確保key對(duì)象的不變性,那么調(diào)用hash(Object key)就一定能獲取相同的哈希值,其次因?yàn)橐_保下標(biāo)要在哈希桶內(nèi),所以比較容易想到的是對(duì)哈希值和桶長(zhǎng)度進(jìn)行取模,這樣就能保證元素的分布相對(duì)均勻.但是模運(yùn)算消耗較大,所以在HashMap中的做法是使用h&(table.length-1),根據(jù)之前的分析可以,哈希桶的長(zhǎng)度是2的n次方,所以table.length-1之后,二進(jìn)制后的數(shù)字全部都是1,所以無(wú)論h的值是什么,都相當(dāng)于取模的結(jié)果,但是&比%效率更高.
例如table.length = 16, h =5;
1111&0101 = 0101 ,即等于5,哈希桶下標(biāo)為5
2.HashMap的put方法
- ①判斷HashMap的哈希桶是否為null,通過(guò)resize()方法進(jìn)行擴(kuò)容.
- ②判斷哈希桶下標(biāo)是否存在元素,不存在則插入元素
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//①第一次初始化table長(zhǎng)度,
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//②判斷下標(biāo)位置元素是否為空,如果為空插入一個(gè)新的值
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
...//這里涉及到hash沖突后的處理
}
}
- ③當(dāng)前元素不為空,證明發(fā)生了hash沖突,所以判斷兩個(gè)新舊兩個(gè)key的值是否相同或相等,如果相等,用新value覆蓋舊value
- ④如果新插入的結(jié)點(diǎn)是TreeNode,即判斷table[i]是否為紅黑樹(shù),如果是則在樹(shù)中插入該值,否則繼續(xù)執(zhí)行后序代碼
- ⑤遍歷table[i],判斷鏈表中結(jié)點(diǎn)是否有后繼結(jié)點(diǎn),如果后繼結(jié)點(diǎn)為空則插入到隊(duì)尾,同時(shí)判斷當(dāng)前鏈表長(zhǎng)度是否大于8,如果大于8,則將鏈表轉(zhuǎn)為紅黑樹(shù)
- ⑥在遍歷鏈表的過(guò)程中,如果發(fā)現(xiàn)新值的key已存在鏈表中,則覆蓋舊的value為新value
- ⑦插入成功后,判斷實(shí)際存在的鍵值對(duì)數(shù)量size是否大于負(fù)載容量thredshold,如果超過(guò),就調(diào)用resize()進(jìn)行擴(kuò)容
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
...
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
//當(dāng)前鏈表為紅黑樹(shù)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//將新值插入到鏈表隊(duì)尾,
p.next = newNode(hash, key, value, null);
//判斷當(dāng)前鏈表長(zhǎng)度是否大于8,是就轉(zhuǎn)為紅黑樹(shù)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
⑥覆蓋鏈表中的舊value
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
++modCount;
if (++size > threshold)
//擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}
3.擴(kuò)容機(jī)制
擴(kuò)容就是重新計(jì)算HashMap中哈希桶的大小,向HashMap中不斷添加元素,而數(shù)組必須在初始化定義長(zhǎng)度,當(dāng)數(shù)組不足以存放更多的元素,就需要擴(kuò)大數(shù)組的長(zhǎng)度,方法是使用一個(gè)新的數(shù)組代替已有的數(shù)組.就像裝水時(shí)小桶換大桶.
擴(kuò)容步驟:
- ①判斷舊的數(shù)組是否大于0,如果大于0且小于HashMap最大允許容量,則新的數(shù)組長(zhǎng)度為舊數(shù)組長(zhǎng)度*2
- ②將舊數(shù)組的負(fù)載容量(長(zhǎng)度負(fù)載因子)2作為新數(shù)組的負(fù)載容量
- ③創(chuàng)建一個(gè)新的Node數(shù)組,長(zhǎng)度為舊數(shù)組長(zhǎng)度*2
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
//如果舊的哈希桶長(zhǎng)度大于最大可值,則將最大負(fù)載設(shè)為Integer的最大值,返回舊哈希桶
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//將舊桶的大小左移1位,相當(dāng)于乘2,就是新桶的大小,同時(shí)新桶數(shù)量必須小于最大容量,并且舊桶長(zhǎng)度大于默認(rèn)容量
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
...
}
-
④遍歷舊數(shù)組,判斷元素哈希值&舊數(shù)組長(zhǎng)度是否為0,如果為0則將元素放在原下標(biāo),如果不為0則key的新下標(biāo)的值等于原下標(biāo)+舊數(shù)組長(zhǎng)度.
圖中n為舊數(shù)組長(zhǎng)度,key1為key在舊數(shù)組中的hash值,key2是key在新數(shù)組中hash計(jì)算后的值
圖3-1 原key在新的哈希桶下標(biāo)位計(jì)算方法
由圖中可以得知,只要判斷原key在高位新增的是0或是1,就能得到新的下標(biāo).
圖3-2 key在新數(shù)組中下標(biāo)計(jì)算方法
源碼實(shí)現(xiàn)
final Node<K,V>[] resize() {
...
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
//計(jì)算原索引
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//放在原下標(biāo)
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//放在新的下標(biāo),下標(biāo)位置=原下標(biāo)+舊數(shù)組成長(zhǎng)度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
...
}
