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

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

HashMap的基本概況

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

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

HashMap和Hashtable的區別

定義

public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

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

初始化

HashMap map = new HashMap();

通過這個方法會調用HashMap的無參構造方法。

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

//無參構造創建對象之后 會有兩個常量
//DEFAULT_INITIAL_CAPACITY 默認初始化容量 16  這里值得借鑒的是位運算
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//DEFAULT_LOAD_FACTOR 負載因子默認為0.75f 負載因子和擴容有關 后文詳談
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//最大容量為2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;

//以Node為元素的數組，長度必須為2的n次冪
transient Node[] table;

//已經儲存的Node的數量，包括數組中的和鏈表中的，邏輯長度
transient int size;

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

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

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

那么Node是什么呢？

//一個靜態內部類 其實就是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后計算數組下標index;

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

如果沒碰撞直接放到對應下標的位置上；

如果碰撞了，且節點已經存在，就替換掉 value；

如果碰撞后發現為樹結構，掛載到樹上。

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

數據 put 后，如果數據量超過threshold，就要resize。

public V put(K key, V value) {
  //調用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)  為第二步 高位參與運算
  //具體的算法就不解釋了 作用就是性能更加優良
  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;
  //如果當前數組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時，及時轉成紅黑樹，提高map的效率
      e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value);
    //都不是 就是鏈表 
    else {
      for (int binCount = 0; ; ++binCount) {
        if ((e = p.next) == null) {
          //將next指向新的節點
          p.next = newNode(hash, key, value, null);
          //這個判斷是用來判斷是否要轉化為紅黑樹結構
          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
            treeifyBin(tab, hash);
          break;
        }
        // key已經存在直接覆蓋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時，及時轉成紅黑樹，提高map的效率。那么接下來說一說什么是哈希表碰撞攻擊。

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

擴容resize()

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

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

擴容簡單說有兩步：

1.擴容

創建一個新的Entry空數組，長度是原數組的2倍。

2.ReHash

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

//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的其他方法就不寫了。下面說一下關于HashMap的一些問題

1.如果多個線程同時使用put方法添加元素會丟失元素

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

2.多線程同時擴容會造成死循環

多線程同時檢查到擴容，并且執行擴容操作，在進行rehash的時候會造成閉環鏈表，從而在get該位置元素的時候，程序將會進入死循環。【證明HashMap高并發下問題會在以后的文章中出現】

如何讓HashMap實現線程安全？

直接使用Hashtable

Collections.synchronizeMap方法

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

總結

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

HashMap 的 bucket 數組大小一定是2的n次方

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

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

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

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

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

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