摘要：哈希表碰撞攻擊就是通過精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個退化的單鏈表，此時哈希表各種操作的時間均提升了一個數(shù)量級，因此會消耗大量資源，導(dǎo)致系統(tǒng)無法快速響應(yīng)請求，從而達到拒絕服務(wù)攻擊的目的。

似乎所有的java面試或者考察都繞不開hash，準確說是必問集合，問集合必問hash表。雖然一直以來都經(jīng)常的使用HashMap，但是卻一直沒有看過源碼，可能是沒有意識到閱讀源碼的好處，經(jīng)過前幾篇的一個分析，發(fā)現(xiàn)閱讀源碼讓自己對集合有了更加深刻的了解，因此會一直將這個系列進行下去，這次要說的HashMap。

HashMap的基本概況

HashMap是一個Hash表（之前有寫過數(shù)據(jù)結(jié)構(gòu)的文章，專門對哈希表做過講解），其數(shù)據(jù)以鍵值對的結(jié)構(gòu)進行存儲，在遇到?jīng)_突的時候會使用鏈表來進行解決，JDK8以后引入了紅黑樹的模式，具體會在文中分析。

其次，HashMap是非線程安全的，Key和Value都允許為空，Key重復(fù)會覆蓋、Value允許重復(fù)。補充一句，在多線程下我們可以使用concurrentHashMap。

HashMap和Hashtable的區(qū)別

定義

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

HashMap沒有什么要說的，直接切入正題，初始化一個HashMap。

初始化

HashMap map = new HashMap();

通過這個方法會調(diào)用HashMap的無參構(gòu)造方法。

//兩個常量 向下追蹤
public HashMap() {
  this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR);
}

//無參構(gòu)造創(chuàng)建對象之后 會有兩個常量
//DEFAULT_INITIAL_CAPACITY 默認初始化容量 16  這里值得借鑒的是位運算
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//DEFAULT_LOAD_FACTOR 負載因子默認為0.75f 負載因子和擴容有關(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)儲存的Node的數(shù)量，包括數(shù)組中的和鏈表中的，邏輯長度
transient int size;

threshold 決定能放入的數(shù)據(jù)量，一般情況下等于 Capacity * LoadFactor

通過上述代碼我們不難發(fā)現(xiàn)，HashMap的底層還是數(shù)組（注意，數(shù)組會在第一次put的時候通過 resize() 函數(shù)進行分配），數(shù)組的長度為2的N次冪。

在HashMap中，哈希桶數(shù)組table的長度length大小必須為2的n次方(一定是合數(shù))，這是一種非常規(guī)的設(shè)計，常規(guī)的設(shè)計是把桶的大小設(shè)計為素數(shù)。相對來說素數(shù)導(dǎo)致沖突的概率要小于合數(shù)，Hashtable初始化桶大小為11，就是桶大小設(shè)計為素數(shù)的應(yīng)用（Hashtable擴容后不能保證還是素數(shù)）。HashMap采用這種非常規(guī)設(shè)計，主要是為了在取模和擴容時做優(yōu)化，同時為了減少沖突，HashMap定位哈希桶索引位置時，也加入了高位參與運算的過程。

那么Node是什么呢？

//一個靜態(tài)內(nèi)部類 其實就是Map中元素的具體存儲對象  
static class Node implements Map.Entry {
          //每個儲存元素key的哈希值
        final int hash;
          //這就是key-value
        final K key;
        V value;
          //next 追加的時候使用，標記鏈表的下一個node地址
        Node next;
        
        Node(int hash, K key, V value, Node next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

此時我們就擁有了一個空的HashMap，下面我們看一下put

put

JDK8 HashMap put的基本思路：

對key的hashCode()進行hash后計算數(shù)組下標index;

如果當前數(shù)組table為null，進行resize()初始化；

如果沒碰撞直接放到對應(yīng)下標的位置上；

如果碰撞了，且節(jié)點已經(jīng)存在，就替換掉 value；

如果碰撞后發(fā)現(xiàn)為樹結(jié)構(gòu)，掛載到樹上。

如果碰撞后為鏈表，添加到鏈表尾，并判斷鏈表如果過長(大于等于TREEIFY_THRESHOLD，默認8)，就把鏈表轉(zhuǎn)換成樹結(jié)構(gòu)；

數(shù)據(jù) put 后，如果數(shù)據(jù)量超過threshold，就要resize。

public V put(K key, V value) {
  //調(diào)用putVal方法 在此之前會對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ōu)良
  return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//進行添加操作
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
  Node[] tab; Node p; int n, i;
  //如果當前數(shù)組table為null，進行resize()初始化
  if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;
  //(n - 1) & hash 計算出下標 如果該位置為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)
      //紅黑樹是為了防止哈希表碰撞攻擊，當鏈表鏈長度為8時，及時轉(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é)點
          p.next = newNode(hash, key, value, null);
          //這個判斷是用來判斷是否要轉(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;
}

在剛才的代碼中我們提到了紅黑樹是為了防止哈希表碰撞攻擊，當鏈表鏈長度為8時，及時轉(zhuǎn)成紅黑樹，提高map的效率。那么接下來說一說什么是哈希表碰撞攻擊。

現(xiàn)在做web開發(fā)RESTful風格的接口相當?shù)钠占埃虼撕芏嗟臄?shù)據(jù)都是通過json來進行傳遞的，而json數(shù)據(jù)收到之后會被轉(zhuǎn)為json對象，通常都是哈希表結(jié)構(gòu)的，就是Map。
我們知道理想情況下哈希表插入和查找操作的時間復(fù)雜度均為O(1)，任何一個數(shù)據(jù)項可以在一個與哈希表長度無關(guān)的時間內(nèi)計算出一個哈希值（key），從而得到下標。但是難免出現(xiàn)不同的數(shù)據(jù)被定位到了同一個位置，這就導(dǎo)致了插入和查找操作的時間復(fù)雜度不為O(1)，這就是哈希碰撞。
java的中解決哈希碰撞的思路是單向鏈表和黑紅樹，上文提到紅黑樹是JDK8之后添加，為了防止哈希表碰撞攻擊，為什么？。
不知道你有沒有設(shè)想過這樣一種場景，添加的所有數(shù)據(jù)都碰撞在一起，那么這些數(shù)據(jù)就會被組織到一個鏈表中，隨著鏈表越來越長，哈希表會退化為單鏈表。哈希表碰撞攻擊就是通過精心構(gòu)造數(shù)據(jù)，使得所有數(shù)據(jù)全部碰撞，人為將哈希表變成一個退化的單鏈表，此時哈希表各種操作的時間均提升了一個數(shù)量級，因此會消耗大量CPU資源，導(dǎo)致系統(tǒng)無法快速響應(yīng)請求，從而達到拒絕服務(wù)攻擊（DoS）的目的。
我們需要注意的是紅黑樹實際上并不能解決哈希表攻擊問題，只是減輕影響，防護該種攻擊還需要其他的手段，譬如控制POST數(shù)據(jù)的數(shù)量。

擴容resize()

不管是list還是map，都會遇到容量不足需要擴容的時候，但是不同于list，HashMap的擴容設(shè)計的非常巧妙，首先在上文提到過數(shù)組的長度為2的N次方，也就是說初始為16，擴容一次為32...
好處呢？就是上文提到的擴容是性能優(yōu)化和減少碰撞，就是體現(xiàn)在此處。

數(shù)組下標計算： index = (table.length - 1) & hash ，由于 table.length 也就是capacity 肯定是2的N次方，使用 & 位運算意味著只是多了最高位，這樣就不用重新計算 index，元素要么在原位置，要么在原位置+ oldCapacity.
如果增加的高位為0，resize 后 index 不變；高位為1在原位置+ oldCapacity。resize 的過程中原來碰撞的節(jié)點有一部分會被分開。

擴容簡單說有兩步：

1.擴容

創(chuàng)建一個新的Entry空數(shù)組，長度是原數(shù)組的2倍。

2.ReHash

遍歷原Entry數(shù)組，把所有的Entry重新Hash到新數(shù)組。

//HashMap的源碼真的長  0.0  這段改天補上
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.如果多個線程同時使用put方法添加元素會丟失元素

假設(shè)正好存在兩個put的key發(fā)生了碰撞，那么根據(jù)HashMap的實現(xiàn)，這兩個key會添加到數(shù)組的同一個位置，這樣最終就會發(fā)生其中一個線程的put的數(shù)據(jù)被覆蓋。

2.多線程同時擴容會造成死循環(huán)

多線程同時檢查到擴容，并且執(zhí)行擴容操作，在進行rehash的時候會造成閉環(huán)鏈表，從而在get該位置元素的時候，程序?qū)M入死循環(huán)?！咀C明HashMap高并發(fā)下問題會在以后的文章中出現(xiàn)】

如何讓HashMap實現(xiàn)線程安全？

直接使用Hashtable

Collections.synchronizeMap方法

使用ConcurrentHashMap 下篇文章就是分析ConcurrentHashMap是如何實現(xiàn)線程安全的

總結(jié)

HashMap 在第一次 put 時初始化，類似 ArrayList 在第一次 add 時分配空間。

HashMap 的 bucket 數(shù)組大小一定是2的n次方

HashMap 在 put 的元素數(shù)量大于 Capacity LoadFactor（默認16 0.75） 之后會進行擴容

負載因子是可以修改的，也可以大于1，但是建議不要輕易修改，除非情況非常特殊

JDK8處于提升性能的考慮，在哈希碰撞的鏈表長度達到TREEIFY_THRESHOLD（默認8)后，會把該鏈表轉(zhuǎn)變成樹結(jié)構(gòu)

JDK8在 resize 的時候，通過巧妙的設(shè)計，減少了 rehash 的性能消耗

擴容是一個特別耗性能的操作，所以當在使用HashMap的時候，估算map的大小，初始化的時候給一個大致的數(shù)值，避免map進行頻繁的擴容

我不能保證每一個地方都是對的，但是可以保證每一句話，每一行代碼都是經(jīng)過推敲和斟酌的。希望每一篇文章背后都是自己追求純粹技術(shù)人生的態(tài)度。
永遠相信美好的事情即將發(fā)生。