前言
似乎所有的java面試或者考察都繞不開(kāi)hash，準(zhǔn)確說(shuō)是必問(wèn)集合，問(wèn)集合必問(wèn)hash表聚霜。雖然一直以來(lái)都經(jīng)常的使用HashMap，但是卻一直沒(méi)有看過(guò)源碼珠叔，可能是沒(méi)有意識(shí)到閱讀源碼的好處蝎宇，經(jīng)過(guò)前幾篇的一個(gè)分析，發(fā)現(xiàn)閱讀源碼讓自己對(duì)集合有了更加深刻的了解祷安，因此會(huì)一直將這個(gè)系列進(jìn)行下去姥芥，這次要說(shuō)的HashMap。
HashMap的基本概況
HashMap是一個(gè)Hash表（之前有寫(xiě)過(guò)數(shù)據(jù)結(jié)構(gòu)的文章汇鞭，專(zhuān)門(mén)對(duì)哈希表做過(guò)講解）凉唐，其數(shù)據(jù)以鍵值對(duì)的結(jié)構(gòu)進(jìn)行存儲(chǔ)庸追，在遇到?jīng)_突的時(shí)候會(huì)使用鏈表來(lái)進(jìn)行解決，JDK8以后引入了紅黑樹(shù)的模式台囱，具體會(huì)在文中分析淡溯。
其次，HashMap是非線程安全的簿训，Key和Value都允許為空咱娶，Key重復(fù)會(huì)覆蓋、Value允許重復(fù)强品。補(bǔ)充一句膘侮，在多線程下我們可以使用concurrentHashMap。
HashMap和Hashtable的區(qū)別
HashMap
定義
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
HashMap沒(méi)有什么要說(shuō)的的榛，直接切入正題琼了，初始化一個(gè)HashMap。
初始化
HashMap map = new HashMap();
通過(guò)這個(gè)方法會(huì)調(diào)用HashMap的無(wú)參構(gòu)造方法夫晌。
//兩個(gè)常量 向下追蹤
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//無(wú)參構(gòu)造創(chuàng)建對(duì)象之后 會(huì)有兩個(gè)常量
//DEFAULT_INITIAL_CAPACITY 默認(rèn)初始化容量 16 這里值得借鑒的是位運(yùn)算
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//DEFAULT_LOAD_FACTOR 負(fù)載因子默認(rèn)為0.75f 負(fù)載因子和擴(kuò)容有關(guān) 后文詳談
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//最大容量為2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//以Node<K,V>為元素的數(shù)組表伦，長(zhǎng)度必須為2的n次冪
transient Node<K,V>[] table;
//已經(jīng)儲(chǔ)存的Node<key,value>的數(shù)量，包括數(shù)組中的和鏈表中的慷丽，邏輯長(zhǎng)度
transient int size;
threshold 決定能放入的數(shù)據(jù)量，一般情況下等于 Capacity * LoadFactor
通過(guò)上述代碼我們不難發(fā)現(xiàn)鳄哭，HashMap的底層還是數(shù)組（注意要糊，數(shù)組會(huì)在第一次put的時(shí)候通過(guò) resize() 函數(shù)進(jìn)行分配），數(shù)組的長(zhǎng)度為2的N次冪妆丘。
在HashMap中锄俄，哈希桶數(shù)組table的長(zhǎng)度length大小必須為2的n次方(一定是合數(shù))，這是一種非常規(guī)的設(shè)計(jì)勺拣，常規(guī)的設(shè)計(jì)是把桶的大小設(shè)計(jì)為素?cái)?shù)奶赠。相對(duì)來(lái)說(shuō)素?cái)?shù)導(dǎo)致沖突的概率要小于合數(shù)，Hashtable初始化桶大小為11药有，就是桶大小設(shè)計(jì)為素?cái)?shù)的應(yīng)用（Hashtable擴(kuò)容后不能保證還是素?cái)?shù)）毅戈。HashMap采用這種非常規(guī)設(shè)計(jì)，主要是為了在取模和擴(kuò)容時(shí)做優(yōu)化愤惰，同時(shí)為了減少?zèng)_突苇经，HashMap定位哈希桶索引位置時(shí)，也加入了高位參與運(yùn)算的過(guò)程宦言。
那么Node<K,V>是什么呢扇单？
//一個(gè)靜態(tài)內(nèi)部類(lèi) 其實(shí)就是Map中元素的具體存儲(chǔ)對(duì)象
static class Node<K,V> implements Map.Entry<K,V> {
//每個(gè)儲(chǔ)存元素key的哈希值
final int hash;
//這就是key-value
final K key;
V value;
//next 追加的時(shí)候使用，標(biāo)記鏈表的下一個(gè)node地址
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
此時(shí)我們就擁有了一個(gè)空的HashMap奠旺，下面我們看一下put
put
JDK8 HashMap put的基本思路：
- 對(duì)key的hashCode()進(jìn)行hash后計(jì)算數(shù)組下標(biāo)index;
- 如果當(dāng)前數(shù)組table為null蜘澜，進(jìn)行resize()初始化施流；
- 如果沒(méi)碰撞直接放到對(duì)應(yīng)下標(biāo)的位置上；
- 如果碰撞了鄙信，且節(jié)點(diǎn)已經(jīng)存在瞪醋，就替換掉 value；
- 如果碰撞后發(fā)現(xiàn)為樹(shù)結(jié)構(gòu)扮碧，掛載到樹(shù)上趟章。
- 如果碰撞后為鏈表，添加到鏈表尾慎王，并判斷鏈表如果過(guò)長(zhǎng)(大于等于TREEIFY_THRESHOLD蚓土，默認(rèn)8)，就把鏈表轉(zhuǎn)換成樹(shù)結(jié)構(gòu)赖淤；
- 數(shù)據(jù) put 后蜀漆，如果數(shù)據(jù)量超過(guò)threshold，就要resize咱旱。
public V put(K key, V value) {
//調(diào)用putVal方法 在此之前會(huì)對(duì)key做hash處理
return putVal(hash(key), key, value, false, true);
}
//hash
static final int hash(Object key) {
int h;
// h = key.hashCode() 為第一步 取hashCode值
// h ^ (h >>> 16) 為第二步 高位參與運(yùn)算
//具體的算法就不解釋了 作用就是性能更加優(yōu)良
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
//進(jìn)行添加操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當(dāng)前數(shù)組table為null确丢，進(jìn)行resize()初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//(n - 1) & hash 計(jì)算出下標(biāo) 如果該位置為null 說(shuō)明沒(méi)有碰撞就賦值到此位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//反之 說(shuō)明碰撞了
Node<K,V> e; K k;
//判斷 key是否存在 如果存在就覆蓋原來(lái)的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//沒(méi)有存在 判斷是不是紅黑樹(shù)
else if (p instanceof TreeNode)
//紅黑樹(shù)是為了防止哈希表碰撞攻擊，當(dāng)鏈表鏈長(zhǎng)度為8時(shí)吐限，及時(shí)轉(zhuǎn)成紅黑樹(shù)鲜侥，提高map的效率
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//都不是 就是鏈表
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
//將next指向新的節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
//這個(gè)判斷是用來(lái)判斷是否要轉(zhuǎn)化為紅黑樹(shù)結(jié)構(gòu)
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
// key已經(jīng)存在直接覆蓋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)
resize();
afterNodeInsertion(evict);
return null;
}
在剛才的代碼中我們提到了紅黑樹(shù)是為了防止哈希表碰撞攻擊，當(dāng)鏈表鏈長(zhǎng)度為8時(shí)诸典，及時(shí)轉(zhuǎn)成紅黑樹(shù)描函，提高map的效率。那么接下來(lái)說(shuō)一說(shuō)什么是哈希表碰撞攻擊狐粱。
現(xiàn)在做web開(kāi)發(fā)RESTful風(fēng)格的接口相當(dāng)?shù)钠占耙ㄔⅲ虼撕芏嗟臄?shù)據(jù)都是通過(guò)json來(lái)進(jìn)行傳遞的，而json數(shù)據(jù)收到之后會(huì)被轉(zhuǎn)為json對(duì)象肌蜻，通常都是哈希表結(jié)構(gòu)的互墓，就是Map。
我們知道理想情況下哈希表插入和查找操作的時(shí)間復(fù)雜度均為O(1)蒋搜，任何一個(gè)數(shù)據(jù)項(xiàng)可以在一個(gè)與哈希表長(zhǎng)度無(wú)關(guān)的時(shí)間內(nèi)計(jì)算出一個(gè)哈希值（key）篡撵，從而得到下標(biāo)。但是難免出現(xiàn)不同的數(shù)據(jù)被定位到了同一個(gè)位置豆挽，這就導(dǎo)致了插入和查找操作的時(shí)間復(fù)雜度不為O(1)酸休，這就是哈希碰撞。
java的中解決哈希碰撞的思路是單向鏈表和黑紅樹(shù)祷杈，上文提到紅黑樹(shù)是JDK8之后添加斑司，為了防止哈希表碰撞攻擊，為什么？宿刮。
不知道你有沒(méi)有設(shè)想過(guò)這樣一種場(chǎng)景互站，添加的所有數(shù)據(jù)都碰撞在一起，那么這些數(shù)據(jù)就會(huì)被組織到一個(gè)鏈表中僵缺，隨著鏈表越來(lái)越長(zhǎng)胡桃，哈希表會(huì)退化為單鏈表。哈希表碰撞攻擊就是通過(guò)精心構(gòu)造數(shù)據(jù)磕潮，使得所有數(shù)據(jù)全部碰撞翠胰，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)自脯，因此會(huì)消耗大量CPU資源之景，導(dǎo)致系統(tǒng)無(wú)法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊（DoS）的目的膏潮。
我們需要注意的是紅黑樹(shù)實(shí)際上并不能解決哈希表攻擊問(wèn)題锻狗，只是減輕影響，防護(hù)該種攻擊還需要其他的手段焕参，譬如控制POST數(shù)據(jù)的數(shù)量轻纪。
擴(kuò)容resize()
不管是list還是map，都會(huì)遇到容量不足需要擴(kuò)容的時(shí)候叠纷，但是不同于list刻帚，HashMap的擴(kuò)容設(shè)計(jì)的非常巧妙，首先在上文提到過(guò)數(shù)組的長(zhǎng)度為2的N次方涩嚣，也就是說(shuō)初始為16崇众，擴(kuò)容一次為32...
好處呢？就是上文提到的擴(kuò)容是性能優(yōu)化和減少碰撞缓艳，就是體現(xiàn)在此處。
數(shù)組下標(biāo)計(jì)算： index = (table.length - 1) & hash 看峻，由于 table.length 也就是capacity 肯定是2的N次方阶淘，使用 & 位運(yùn)算意味著只是多了最高位，這樣就不用重新計(jì)算 index互妓，元素要么在原位置溪窒，要么在原位置+ oldCapacity.
如果增加的高位為0，resize 后 index 不變冯勉；高位為1在原位置+ oldCapacity澈蚌。resize 的過(guò)程中原來(lái)碰撞的節(jié)點(diǎn)有一部分會(huì)被分開(kāi)。
擴(kuò)容簡(jiǎn)單說(shuō)有兩步：
1.擴(kuò)容
創(chuàng)建一個(gè)新的Entry空數(shù)組灼狰，長(zhǎng)度是原數(shù)組的2倍宛瞄。
2.ReHash
遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組交胚。
//HashMap的源碼真的長(zhǎng) 0.0 這段改天補(bǔ)上
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
為什么HashMap是線程不安全的
由于源碼過(guò)長(zhǎng)份汗，HashMap的其他方法就不寫(xiě)了盈电。下面說(shuō)一下關(guān)于HashMap的一些問(wèn)題
1.如果多個(gè)線程同時(shí)使用put方法添加元素會(huì)丟失元素
假設(shè)正好存在兩個(gè)put的key發(fā)生了碰撞，那么根據(jù)HashMap的實(shí)現(xiàn)杯活，這兩個(gè)key會(huì)添加到數(shù)組的同一個(gè)位置匆帚，這樣最終就會(huì)發(fā)生其中一個(gè)線程的put的數(shù)據(jù)被覆蓋。
2.多線程同時(shí)擴(kuò)容會(huì)造成死循環(huán)
多線程同時(shí)檢查到擴(kuò)容旁钧，并且執(zhí)行擴(kuò)容操作吸重，在進(jìn)行rehash的時(shí)候會(huì)造成閉環(huán)鏈表，從而在get該位置元素的時(shí)候歪今，程序?qū)?huì)進(jìn)入死循環(huán)嚎幸。【證明HashMap高并發(fā)下問(wèn)題會(huì)在以后的文章中出現(xiàn)】
如何讓HashMap實(shí)現(xiàn)線程安全彤委？
- 直接使用Hashtable
- Collections.synchronizeMap方法
- 使用ConcurrentHashMap 下篇文章就是分析ConcurrentHashMap是如何實(shí)現(xiàn)線程安全的
總結(jié)
- HashMap 在第一次 put 時(shí)初始化鞭铆，類(lèi)似 ArrayList 在第一次 add 時(shí)分配空間。
- HashMap 的 bucket 數(shù)組大小一定是2的n次方
- HashMap 在 put 的元素?cái)?shù)量大于 Capacity * LoadFactor（默認(rèn)16 * 0.75） 之后會(huì)進(jìn)行擴(kuò)容
- 負(fù)載因子是可以修改的焦影，也可以大于1车遂，但是建議不要輕易修改，除非情況非常特殊
- JDK8處于提升性能的考慮斯辰，在哈希碰撞的鏈表長(zhǎng)度達(dá)到TREEIFY_THRESHOLD（默認(rèn)8)后舶担，會(huì)把該鏈表轉(zhuǎn)變成樹(shù)結(jié)構(gòu)
- JDK8在 resize 的時(shí)候，通過(guò)巧妙的設(shè)計(jì)彬呻，減少了 rehash 的性能消耗
- 擴(kuò)容是一個(gè)特別耗性能的操作衣陶，所以當(dāng)在使用HashMap的時(shí)候，估算map的大小闸氮，初始化的時(shí)候給一個(gè)大致的數(shù)值剪况，避免map進(jìn)行頻繁的擴(kuò)容
我不能保證每一個(gè)地方都是對(duì)的，但是可以保證每一句話蒲跨，每一行代碼都是經(jīng)過(guò)推敲和斟酌的译断。希望每一篇文章背后都是自己追求純粹技術(shù)人生的態(tài)度。
永遠(yuǎn)相信美好的事情即將發(fā)生或悲。
