摘要：哈希表碰撞攻擊就是通過精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)，因此會(huì)消耗大量資源，導(dǎo)致系統(tǒng)無法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊的目的。
前言
似乎所有的java面試或者考察都繞不開hash，準(zhǔn)確說是必問集合，問集合必問hash表。雖然一直以來都經(jīng)常的使用HashMap，但是卻一直沒有看過源碼，可能是沒有意識(shí)到閱讀源碼的好處，經(jīng)過前幾篇的一個(gè)分析，發(fā)現(xiàn)閱讀源碼讓自己對(duì)集合有了更加深刻的了解，因此會(huì)一直將這個(gè)系列進(jìn)行下去，這次要說的HashMap。
HashMap的基本概況
HashMap是一個(gè)Hash表（之前有寫過數(shù)據(jù)結(jié)構(gòu)的文章，專門對(duì)哈希表做過講解），其數(shù)據(jù)以鍵值對(duì)的結(jié)構(gòu)進(jìn)行存儲(chǔ)，在遇到?jīng)_突的時(shí)候會(huì)使用鏈表來進(jìn)行解決，JDK8以后引入了紅黑樹的模式，具體會(huì)在文中分析。
其次，HashMap是非線程安全的，Key和Value都允許為空，Key重復(fù)會(huì)覆蓋、Value允許重復(fù)。補(bǔ)充一句，在多線程下我們可以使用concurrentHashMap。
HashMap和Hashtable的區(qū)別
HashMap
定義
public class HashMap extends AbstractMap implements Map, Cloneable, Serializable
HashMap沒有什么要說的，直接切入正題，初始化一個(gè)HashMap。
初始化
HashMap map = new HashMap();
通過這個(gè)方法會(huì)調(diào)用HashMap的無參構(gòu)造方法。
//兩個(gè)常量 向下追蹤
public HashMap() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}
//無參構(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為元素的數(shù)組，長度必須為2的n次冪
transient Node[] table;
//已經(jīng)儲(chǔ)存的Node的數(shù)量，包括數(shù)組中的和鏈表中的，邏輯長度
transient int size;
threshold 決定能放入的數(shù)據(jù)量，一般情況下等于 Capacity * LoadFactor
通過上述代碼我們不難發(fā)現(xiàn)，HashMap的底層還是數(shù)組（注意，數(shù)組會(huì)在第一次put的時(shí)候通過 resize() 函數(shù)進(jìn)行分配），數(shù)組的長度為2的N次冪。
在HashMap中，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))，這是一種非常規(guī)的設(shè)計(jì)，常規(guī)的設(shè)計(jì)是把桶的大小設(shè)計(jì)為素?cái)?shù)。相對(duì)來說素?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)算的過程。
那么Node是什么呢？
//一個(gè)靜態(tài)內(nèi)部類 其實(shí)就是Map中元素的具體存儲(chǔ)對(duì)象
static class Node implements Map.Entry {
//每個(gè)儲(chǔ)存元素key的哈希值
final int hash;
//這就是key-value
final K key;
V value;
//next 追加的時(shí)候使用，標(biāo)記鏈表的下一個(gè)node地址
Node next;
Node(int hash, K key, V value, Node 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()初始化；
如果沒碰撞直接放到對(duì)應(yīng)下標(biāo)的位置上；
如果碰撞了，且節(jié)點(diǎn)已經(jīng)存在，就替換掉 value；
如果碰撞后發(fā)現(xiàn)為樹結(jié)構(gòu)，掛載到樹上。
如果碰撞后為鏈表，添加到鏈表尾，并判斷鏈表如果過長(大于等于TREEIFY_THRESHOLD，默認(rèn)8)，就把鏈表轉(zhuǎn)換成樹結(jié)構(gòu)；
數(shù)據(jù) put 后，如果數(shù)據(jù)量超過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[] tab; Node 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 說明沒有碰撞就賦值到此位置
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//反之 說明碰撞了
Node e; K k;
//判斷 key是否存在 如果存在就覆蓋原來的value
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//沒有存在 判斷是不是紅黑樹
else if (p instanceof TreeNode)
//紅黑樹是為了防止哈希表碰撞攻擊，當(dāng)鏈表鏈長度為8時(shí)，及時(shí)轉(zhuǎn)成紅黑樹，提高map的效率
e = ((TreeNode)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è)判斷是用來判斷是否要轉(zhuǎn)化為紅黑樹結(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;
}
在剛才的代碼中我們提到了紅黑樹是為了防止哈希表碰撞攻擊，當(dāng)鏈表鏈長度為8時(shí)，及時(shí)轉(zhuǎn)成紅黑樹，提高map的效率。那么接下來說一說什么是哈希表碰撞攻擊。
現(xiàn)在做web開發(fā)RESTful風(fēng)格的接口相當(dāng)?shù)钠占埃虼撕芏嗟臄?shù)據(jù)都是通過json來進(jìn)行傳遞的，而json數(shù)據(jù)收到之后會(huì)被轉(zhuǎn)為json對(duì)象，通常都是哈希表結(jié)構(gòu)的，就是Map。我們知道理想情況下哈希表插入和查找操作的時(shí)間復(fù)雜度均為O(1)，任何一個(gè)數(shù)據(jù)項(xiàng)可以在一個(gè)與哈希表長度無關(guān)的時(shí)間內(nèi)計(jì)算出一個(gè)哈希值（key），從而得到下標(biāo)。但是難免出現(xiàn)不同的數(shù)據(jù)被定位到了同一個(gè)位置，這就導(dǎo)致了插入和查找操作的時(shí)間復(fù)雜度不為O(1)，這就是哈希碰撞。
java的中解決哈希碰撞的思路是單向鏈表和黑紅樹，上文提到紅黑樹是JDK8之后添加，為了防止哈希表碰撞攻擊，為什么？。
不知道你有沒有設(shè)想過這樣一種場(chǎng)景，添加的所有數(shù)據(jù)都碰撞在一起，那么這些數(shù)據(jù)就會(huì)被組織到一個(gè)鏈表中，隨著鏈表越來越長，哈希表會(huì)退化為單鏈表。哈希表碰撞攻擊就是通過精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個(gè)退化的單鏈表，此時(shí)哈希表各種操作的時(shí)間均提升了一個(gè)數(shù)量級(jí)，因此會(huì)消耗大量CPU資源，導(dǎo)致系統(tǒng)無法快速響應(yīng)請(qǐng)求，從而達(dá)到拒絕服務(wù)攻擊（DoS）的目的。
我們需要注意的是紅黑樹實(shí)際上并不能解決哈希表攻擊問題，只是減輕影響，防護(hù)該種攻擊還需要其他的手段，譬如控制POST數(shù)據(jù)的數(shù)量。
擴(kuò)容resize()
不管是list還是map，都會(huì)遇到容量不足需要擴(kuò)容的時(shí)候，但是不同于list，HashMap的擴(kuò)容設(shè)計(jì)的非常巧妙，首先在上文提到過數(shù)組的長度為2的N次方，也就是說初始為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 的過程中原來碰撞的節(jié)點(diǎn)有一部分會(huì)被分開。
擴(kuò)容簡(jiǎn)單說有兩步：
1.擴(kuò)容
創(chuàng)建一個(gè)新的Entry空數(shù)組，長度是原數(shù)組的2倍。
2.ReHash
遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組。
//HashMap的源碼真的長 0.0 這段改天補(bǔ)上
final Node[] resize() {
Node[] 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[] newTab = (Node[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node 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)e).split(this, newTab, j, oldCap);
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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是線程不安全的
由于源碼過長，HashMap的其他方法就不寫了。下面說一下關(guān)于HashMap的一些問題
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)?！咀C明HashMap高并發(fā)下問題會(huì)在以后的文章中出現(xiàn)】
如何讓HashMap實(shí)現(xiàn)線程安全？
直接使用Hashtable
Collections.synchronizeMap方法
使用ConcurrentHashMap 下篇文章就是分析ConcurrentHashMap是如何實(shí)現(xiàn)線程安全的
總結(jié)
HashMap 在第一次 put 時(shí)初始化，類似 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處于提升性能的考慮，在哈希碰撞的鏈表長度達(dá)到TREEIFY_THRESHOLD（默認(rèn)8)后，會(huì)把該鏈表轉(zhuǎn)變成樹結(jié)構(gòu)
JDK8在 resize 的時(shí)候，通過巧妙的設(shè)計(jì)，減少了 rehash 的性能消耗
擴(kuò)容是一個(gè)特別耗性能的操作，所以當(dāng)在使用HashMap的時(shí)候，估算map的大小，初始化的時(shí)候給一個(gè)大致的數(shù)值，避免map進(jìn)行頻繁的擴(kuò)容
我不能保證每一個(gè)地方都是對(duì)的，但是可以保證每一句話，每一行代碼都是經(jīng)過推敲和斟酌的。希望每一篇文章背后都是自己追求純粹技術(shù)人生的態(tài)度。永遠(yuǎn)相信美好的事情即將發(fā)生。
