​[JDK] HashMap 原理總算整明白了

• 2020 年 3 月 18 日
• 筆記

[JDK] HashMap 原理剖析

簡介

哈希表（hash table）也叫散列表，是一種非常重要的數據結構，應用場景及其豐富，許多緩存技術（比如memcached）的核心其實就是在內存中維護一張大的哈希表，而 HashMap 的實現原理也常常出現在各類的面試題中，重要性可見一斑。本文會對 Java 集合框架中的 HashMap，就 JDK7、JDK8 的源碼實現進行分析。

什麼是哈希表HashMap實現原理源碼分析基礎參數構造器擴容機制存儲結構鏈表紅黑樹性能提升總結REFERENCES更多

手機用戶請橫屏獲取最佳閱讀體驗，REFERENCES中是本文參考的鏈接，如需要鏈接和更多資源，可以關注其他博客發佈地址。

正文

哈希表（hash table）也叫散列表，是一種非常重要的數據結構，應用場景及其豐富，許多緩存技術（比如memcached）的核心其實就是在內存中維護一張大的哈希表，而 HashMap 的實現原理也常常出現在各類的面試題中，重要性可見一斑。本文會對 Java 集合框架中的 HashMap，就 JDK7、JDK8 的源碼實現進行分析。

什麼是哈希表

在討論哈希表之前，我們先大概了解下其他數據結構在新增，查找等基礎操作執行性能差異。

• 數組：採用一段連續的存儲單元來存儲數據。對於指定下標的查找，時間複雜度為O(1)；通過給定值進行查找，需要遍曆數組，逐一比對給定關鍵字和數組元素，時間複雜度為O(n)，當然，對於有序數組，則可採用二分查找，插值查找，斐波那契查找等方式，可將查找複雜度提高為O(logn)；對於一般的插入刪除操作，涉及到數組元素的移動，其平均複雜度也為O(n)
• 線性鏈表：對於鏈表的新增，刪除等操作（在找到指定操作位置後），僅需處理結點間的引用即可，時間複雜度為O(1)，而查找操作需要遍歷鏈表逐一進行比對，複雜度為O(n)
• 二叉樹：對一棵相對平衡的有序二叉樹，對其進行插入，查找，刪除等操作，平均複雜度均為O(logn)。
• 哈希表：相比上述幾種數據結構，在哈希表中進行添加，刪除，查找等操作，性能十分之高，不考慮哈希衝突的情況下，僅需一次定位即可完成，時間複雜度為O(1)，接下來我們就來看看哈希表是如何實現達到驚艷的常數階O(1)的。

我們知道，數據結構的物理存儲結構只有兩種：順序存儲結構和鏈式存儲結構（像棧，隊列，樹，圖等是從邏輯結構去抽象的，映射到內存中，也這兩種物理組織形式），而在上面我們提到過，在數組中根據下標查找某個元素，一次定位就可以達到，哈希表利用了這種特性，哈希表的主幹就是數組。

比如我們要新增或查找某個元素，我們把當前元素的關鍵字，利用某個函數映射到數組中的某個位置，通過數組下標一次定位就可完成操作。

//其中，這個函數function一般稱為哈希函數，這個函數的設計好壞會直接影響到哈希表的優劣。舉個例子，比如我們要在哈希表中執行插入操作：  index = function(key)  

.

這個函數就是我們後面會討論的哈希函數，查找操作同理，先通過哈希函數計算出實際存儲地址，然後從數組中對應地址取出即可。

哈希衝突

　　然而萬事無完美，如果兩個不同的元素，通過哈希函數得出的實際存儲地址相同怎麼辦？也就是說，當我們對某個元素進行哈希運算，得到一個存儲地址，然後要進行插入的時候，發現已經被其他元素佔用了，其實這就是所謂的哈希衝突，也叫哈希碰撞。前面我們提到過，哈希函數的設計至關重要，好的哈希函數會儘可能地保證 計算簡單和散列地址分佈均勻,但是，我們需要清楚的是，數組是一塊連續的固定長度的內存空間，再好的哈希函數也不能保證得到的存儲地址絕對不發生衝突。那麼哈希衝突如何解決呢？哈希衝突的解決方案有多種:

• 開放定址法（發生衝突，繼續尋找下一塊未被佔用的存儲地址）
• 再散列函數法
• 鏈地址法

而HashMap(JDK7)即是採用了鏈地址法，也就是數組+鏈表的方式。 一直到JDK7為止，HashMap的結構都是這麼簡單，基於一個數組以及多個鏈表的實現，hash值衝突的時候，就將對應節點以鏈表的形式存儲。

這樣子的 HashMap 性能上就抱有一定疑問，如果說成百上千個節點在hash時發生碰撞，存儲一個鏈表中，那麼如果要查找其中一個節點，那就不可避免的花費O(n)的查找時間，這將是多麼大的性能損失。這個問題終於在JDK8中得到了解決。再最壞的情況下，鏈表查找的時間複雜度為O(n),而紅黑樹一直是O(logn),這樣會提高HashMap的效率。

JDK7 中 HashMap 採用的是位桶+鏈表的方式，即我們常說的散列鏈表的方式，而 JDK8 中採用的是位桶+鏈表/紅黑樹（有關紅黑樹請查看紅黑樹）的方式，也是非線程安全的。當某個位桶的鏈表的長度達到某個閥值的時候，這個鏈表就將轉換成紅黑樹。

.

HashMap實現原理

核心數組

HashMap 的主幹是一個 Node 數組。Node 是 HashMap 的基本組成單元，每一個 Node 包含一個key-value鍵值對。

 transient Node<K,V>[] table;  

Node是HashMap中的一個靜態內部類。代碼如下

/**       * Basic hash bin node, used for most entries.  (See below for       * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)       */      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) {              this.hash = hash;              this.key = key;              this.value = value;              this.next = next;          }            public final K getKey()        { return key; }          public final V getValue()      { return value; }          public final String toString() { return key + "=" + value; }            public final int hashCode() {              return Objects.hashCode(key) ^ Objects.hashCode(value);          }            public final V setValue(V newValue) {              V oldValue = value;              value = newValue;              return oldValue;          }            public final boolean equals(Object o) {              if (o == this)                  return true;              if (o instanceof Map.Entry) {                  Map.Entry<?,?> e = (Map.Entry<?,?>)o;                  if (Objects.equals(key, e.getKey()) &&                      Objects.equals(value, e.getValue()))                      return true;              }              return false;          }      }  

鏈表和紅黑樹轉換機制

見後文源碼分析

源碼分析

我們大致知道Map內部通過數組來維護數據，元素在放入數組時，會通過hash函數計算存放在數組的哪個下標位置，放入後，如果該位置非空，則將該處數據通過鏈表存儲，如果長度超出指定範圍，則轉換為有序的紅黑樹存儲。那麼，在源碼分析前我們先做個描述上的約定（源碼中使用的是英文單詞bin，含義上可以理解為箱子或是桶）：

• 數組：桶容器（包含多個桶）
• 數組的某一位置對應的元素集合：桶中元素集合
• 數組的某一位置對應的元素集合的存儲結構：鏈表結構桶、樹結構桶
• 數組的某一位置對應的元素集合中的存儲元素：桶中的元素節點

基礎參數

  /* ---------------- Fields -------------- */        /**       * The table, initialized on first use, and resized as       * necessary. When allocated, length is always a power of two.       * (We also tolerate length zero in some operations to allow       * bootstrapping mechanics that are currently not needed.)       */      //元素桶數組      transient Node<K,V>[] table;        /**       * Holds cached entrySet(). Note that AbstractMap fields are used       * for keySet() and values().       */      //Set集合，進行了節點數組的Map.Entry<K,V>      transient Set<Map.Entry<K,V>> entrySet;        /**       * The number of key-value mappings contained in this map.       */       //實際存儲的key-value鍵值對的個數      transient int size;        /**       * The number of times this HashMap has been structurally modified       * Structural modifications are those that change the number of mappings in       * the HashMap or otherwise modify its internal structure (e.g.,       * rehash).  This field is used to make iterators on Collection-views of       * the HashMap fail-fast.  (See ConcurrentModificationException).       */       //用於快速失敗，由於HashMap非線程安全，在對HashMap進行迭代時，如果期間其他線程的參與導致HashMap的結構發生變化了（比如put，remove等操作），需要拋出異常ConcurrentModificationException      transient int modCount;        /**       * The next size value at which to resize (capacity * load factor).       *       * @serial       */      // (The javadoc description is true upon serialization.      // Additionally, if the table array has not been allocated, this      // field holds the initial array capacity, or zero signifying      // DEFAULT_INITIAL_CAPACITY.)      //閾值，當table == {}時，該值為初始容量（初始容量默認為16）；當table被填充了，也就是為table分配內存空間後，threshold一般為 capacity*loadFactory。HashMap在進行擴容時需要參考threshold，後面會詳細談到      int threshold;        /**       * The load factor for the hash table.       *       * @serial       */       //負載因子，代表了table的填充度有多少，默認是0.75      final float loadFactor;  

構造器

HashMap有4個構造器，其他構造器如果用戶沒有傳入 initialCapacity 和 loadFactor 這兩個參數，默認值：initialCapacity默認為16，loadFactory默認為0.75

 /* ---------------- Public operations -------------- */        /**       * Constructs an empty <tt>HashMap</tt> with the specified initial       * capacity and load factor.       *       * @param  initialCapacity the initial capacity       * @param  loadFactor      the load factor       * @throws IllegalArgumentException if the initial capacity is negative       *         or the load factor is nonpositive       */      public HashMap(int initialCapacity, float loadFactor) {          if (initialCapacity < 0)              throw new IllegalArgumentException("Illegal initial capacity: " +                                                 initialCapacity);          if (initialCapacity > MAXIMUM_CAPACITY)              initialCapacity = MAXIMUM_CAPACITY;          if (loadFactor <= 0 || Float.isNaN(loadFactor))              throw new IllegalArgumentException("Illegal load factor: " +                                                 loadFactor);          this.loadFactor = loadFactor;          //此處進行了容量閾值的初始化操作，返回一個比初始化容量大的最接近的一個2的冪次方的值          this.threshold = tableSizeFor(initialCapacity);      }        /**       * Constructs an empty <tt>HashMap</tt> with the specified initial       * capacity and the default load factor (0.75).       *       * @param  initialCapacity the initial capacity.       * @throws IllegalArgumentException if the initial capacity is negative.       */      public HashMap(int initialCapacity) {          this(initialCapacity, DEFAULT_LOAD_FACTOR);      }        /**       * Constructs an empty <tt>HashMap</tt> with the default initial capacity       * (16) and the default load factor (0.75).       */      public HashMap() {          this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted      }        /**       * Constructs a new <tt>HashMap</tt> with the same mappings as the       * specified <tt>Map</tt>.  The <tt>HashMap</tt> is created with       * default load factor (0.75) and an initial capacity sufficient to       * hold the mappings in the specified <tt>Map</tt>.       *       * @param   m the map whose mappings are to be placed in this map       * @throws  NullPointerException if the specified map is null       */      public HashMap(Map<? extends K, ? extends V> m) {          this.loadFactor = DEFAULT_LOAD_FACTOR;          putMapEntries(m, false);      }  

hash 運算

 /**       * Computes key.hashCode() and spreads (XORs) higher bits of hash       * to lower.  Because the table uses power-of-two masking, sets of       * hashes that vary only in bits above the current mask will       * always collide. (Among known examples are sets of Float keys       * holding consecutive whole numbers in small tables.)  So we       * apply a transform that spreads the impact of higher bits       * downward. There is a tradeoff between speed, utility, and       * quality of bit-spreading. Because many common sets of hashes       * are already reasonably distributed (so don't benefit from       * spreading), and because we use trees to handle large sets of       * collisions in bins, we just XOR some shifted bits in the       * cheapest possible way to reduce systematic lossage, as well as       * to incorporate impact of the highest bits that would otherwise       * never be used in index calculations because of table bounds.       */  //計算 HashCode ，並通過異或方式從高位到低位擴展了 hash 集合中的元素。因為散列桶使用的是2的冪次方長度，因此僅在當前二級制碼更高位變化中的散列將發生碰撞。（眾所周知，前文的例子中的是在小的列表中連續行的存儲Float類型的集合。）因此，我們將其應用在擴展高位向下擴散分佈的衝突形式轉換。這是在二進制擴散的一種速度、效率和質量多方面權衡。通常大量的hash集合會被合理分配（所以並不是得益於擴散）。我們使用樹結構來解決大數據集合場景下的桶中元素衝突的問題，我們僅僅是通過XOR（異或）的方式來來移動一些二進制位，實現減少系統性能損失的目的。以及，通過避免由於列表的限制而使用的索引計算的方式來合併高位的衝突。  static final int hash(Object key) {          int h;          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);      }  

從上面的代碼可以看到key的hash值的計算方法。key 的 hash 值高16位不變，低16位與高16位異或作為 key 的最終 hash 值。（h >>> 16，表示無符號右移16位，高位補0，任何數跟0異或都是其本身，因此 key 的 hash 值高16位不變。）

.

後文會繼續討論此處這樣設計的用途，詳見元素節點存放下標的計算。

擴容閾值初始化

/**       * Returns a power of two size for the given target capacity.       */      static final int tableSizeFor(int cap) {          int n = cap - 1;          //由於n不等於0，則n的二進制表示中總會有一bit為1，這時考慮最高位的1。通過無符號右移1位，則將最高位的1右移了1位，再做或操作，使得n的二進制表示中與最高位的1緊鄰的右邊一位也為1，如0000 11xx xxxx。          n |= n >>> 1;          //注意，這個n已經經過了n |= n >>> 1; 操作。假設此時n為0000 11xx xxxx ，則n無符號右移兩位，會將最高位兩個連續的1右移兩位，然後再與原來的n做或操作，這樣n的二進制表示的高位中會有4個連續的1。如00 0011 11xx xxxx 。          n |= n >>> 2;          //這次把已經有的高位中的連續的4個1，右移4位，再做或操作，這樣n的二進制表示的高位中會有8個連續的1。如00 0011 1111 11xx xxxx 。          n |= n >>> 4;          n |= n >>> 8;          n |= n >>> 16;          return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;      }  

以此類推： 注意，容量最大也就是32bit的正數，因此最後n |= n >>> 16; ，最多也就32個1（但是這已經是負數了。在執行 tableSizeFor 之前，對 initialCapacity 做了判斷，如果大於 MAXIMUM_CAPACITY(2 ^ 30)，則取 MAXIMUM_CAPACITY。如果等於 MAXIMUM_CAPACITY(2 ^ 30)，會執行移位操作。所以這裏面的移位操作之後，最大30個1，不會大於等於 MAXIMUM_CAPACITY。30個1，加1之後得2 ^ 30） 。

For Example:

.

// 構造器中threshold（當HashMap的size到達threshold這個閾值時會擴容）。但是，請注意，在構造方法中，並沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算。  this.threshold = tableSizeFor(initialCapacity);  

擴容機制

put

 public V put(K key, V value) {          return putVal(hash(key), key, value, false, true);      }        /**       * Implements Map.put and related methods       *       * @param hash hash for key       * @param key the key       * @param value the value to put       * @param onlyIfAbsent if true, don't change existing value       * @param evict if false, the table is in creation mode.       * @return previous value, or null if none       */      final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                     boolean evict) {          Node<K,V>[] tab; Node<K,V> p; int n, i;          //1. 如果當前map中無數據，執行resize方法進行初始化。並且返回n          if ((tab = table) == null || (n = tab.length) == 0)              n = (tab = resize()).length;          //2.1 如果要插入的鍵值對要存放的這個位置剛好沒有元素，那麼把他封裝成Node對象，放在這個位置上          if ((p = tab[i = (n - 1) & hash]) == null)              tab[i] = newNode(hash, key, value, null);          //2.2 否則的話，說明這上面有元素          else {              Node<K,V> e; K k;              //2.2.1 如果這個元素的key與要插入的一樣，那麼就替換一下。              if (p.hash == hash &&                  ((k = p.key) == key || (key != null && key.equals(k))))                  e = p;              //2.2.2 【紅黑樹結構】如果當前節點是TreeNode類型的數據，執行putTreeVal方法              else if (p instanceof TreeNode)                  e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);              else {                  //2.2.3 【鏈表結構】遍歷這條鏈子上的數據，跟JDK7沒什麼區別                  for (int binCount = 0; ; ++binCount) {                      if ((e = p.next) == null) {                          p.next = newNode(hash, key, value, null);                          //判斷如果鏈表數目是否超過了8，是的話執行treeifyBin方法轉換為紅黑樹結構                          if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st                              treeifyBin(tab, hash);                          break;                      }                      //如果key存在,且值相等，直接覆蓋                     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;      }  

resize 重新調整存放數組的大小

/**      * Initializes or doubles table size.  If null, allocates in      * accord with initial capacity target held in field threshold.      * Otherwise, because we are using power-of-two expansion, the      * elements from each bin must either stay at same index, or move      * with a power of two offset in the new table.      *      * @return the table      */      //初始化或增加數組容量大小，如果為null,則分配符合初始化容量目標的值到變量`threshold`中,否則，因為我們用的是2的冪次方擴展方式，每個桶中的元素，必須保持相同的索引，或在新的數組中移動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;          //如果當前的數組大小大於0          if (oldCap > 0) {              //超過最大值，返回最大值 2^31 -1              if (oldCap >= MAXIMUM_CAPACITY) {                  threshold = Integer.MAX_VALUE;                  return oldTab;              }              //否則，如果當前數組大小的兩倍小於最大容值範圍，且當前數組大小>=默認初始化容量(16) ，則當前擴容閾值左移2位，相當於 * 2 ；注意，此處會將當前容量 * 2 賦值給局部變量 newCap              else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                       oldCap >= DEFAULT_INITIAL_CAPACITY)                  newThr = oldThr << 1; // double threshold          }          //數組大小為0，但是當前的擴容閾值大於0，則更新當前的的擴容閾值到局部變量          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);          }          //如果擴容閾值為0，進行擴容計算，並賦值當前元素個數 * 負載因子（0.75）          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;          //1.1 判斷當前數組是否為空          if (oldTab != null) {              //循環當前數組              for (int j = 0; j < oldCap; ++j) {                  Node<K,V> e;                  //逐個取出非空元素                  if ((e = oldTab[j]) != null) {                      //原地址引用置空                      oldTab[j] = null;                      //判斷元素下一節點是否為null，是的話，進行hash運算獲得平均分佈的下標，存放元素到新的數組中對應下標位置處（單個元素直接存放）                      if (e.next == null)                          //此處就是為什麼要將Map的容量大小定義為2的冪次方的原因，(2^n -1) & hashVal,比如2的4次方（16），對應-1計算後的2進制數位1111 1111，那麼可以看做有8個位置存放數據，剩下的取決於hash函數對於鍵值key的運算結果分佈是否均勻了。這個前文我們提到過HASH的運算方式，屏蔽了高位對低位的hash運算影響，我們結合下面這個下標的計算方式繼續討論。                          newTab[e.hash & (newCap - 1)] = e;                      else if (e instanceof TreeNode)                          //如果是紅黑樹結構，執行split函數，在樹的元素桶中進行節點拆分，就是將當前元素，放到合適的位置（有序），或是取消樹結構（如果現在桶的元素不夠多的時候），該方法僅在調整大小時調用，源碼中有關於桶中元素的拆分和索引計算的論述                          ((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;                              //通過計算e.hash&oldCap==0構造一條鏈，oldCap，低位容量，如果是8，對應0000 1111                              if ((e.hash & oldCap) == 0) {                                  if (loTail == null)                                      loHead = e;                                  else                                      loTail.next = e;                                  loTail = e;                              }                              //通過e.hash&oldCap!=0構造另外一條鏈，newCap,高位容量，如16，對應1111 0000                              else {                                  if (hiTail == null)                                      hiHead = e;                                  else                                      hiTail.next = e;                                  hiTail = e;                              }                          } while ((e = next) != null);                         //遍歷結束以後，將tail指針指向null，e.hash&oldCap==0構造而來的鏈的位置不變                          if (loTail != null) {                              loTail.next = null;                              newTab[j] = loHead;                          }                          //e.hash&oldCap!=0構造而來的鏈的位置在數組j+oldCap位置處                          if (hiTail != null) {                              hiTail.next = null;                              newTab[j + oldCap] = hiHead;                          }                      }                  }              }          }          return newTab;      }  

元素節點存放下標的計算

int oldCap = (oldTab == null) ? 0 : oldTab.length;  //...  //通過hash運算解析存放的位置，因為我們每次初始化的容量是根據擴容閾值判斷和歷史容量的2倍計算而來，此處通過和newCap-1進行與操作，如果容量是2的冪次方，對應減1後的二進制數值一般表示為 1111...,再和對應key的hash值相與後，可以實現數據更均勻的落在散列桶的槽。而分佈的均勻程度，也由hash函數來保證了。  //另外一方面，新的容量由於是舊容量的2倍，也是2的冪次方，高位的數據特徵不會由於擴容操作，影響低位數據的hash運算分佈情況，也避免了重新計算hash的性能損耗  newTab[e.hash & (newCap - 1)] = e;  

table 的長度都是 2 的冪，因此 index 僅與 hash 值的低 n 位有關（此 n 非table.length，而是 2 的冪指數），hash 值的高位都被與操作置為 0 了。

假設 table.length=2^4=16

.

Q: 如果沒有中間這一步異或操作，直接使用(n-1)&hashCode(),又會怎麼樣？

A: 只有 hashCode 的低四位參與了運算，這樣的設計明顯很容易發生碰撞。

Q: 這個異或操作，設計者是如何考慮的？

A: 源碼的注釋中有寫到，設計者權衡了 speed，utility，quality，將高 16 位與低 16 位異或來減少這種影響。設計者考慮到現在的 hashCode 分佈的已經很不錯了，而且當發生較大碰撞時也用樹形存儲降低了衝突。僅僅異或一下，既減少了系統的開銷，也不會造成的因為高位沒有參與下標的計算 ( table 長度比較小時)，從而引起的碰撞。

Q: 為什麼要用異或來實現這個目的？

A: 所謂的異或，就是相反為1，相同為0，說明高位的結構特徵對低位的結構特徵產生了影響，這樣得出的hashCode會包含高位的數據特徵，可以降低低位HashCode發生碰撞的可能性（此處碰撞幾率的控制，原先參考的維度只有hashCode函數,現在加入了高位數據特徵的維度，降低了發生的幾率）

Q: 那前面擴容使用2的冪次方又是為了什麼呢？

A: 2的冪次方擴容，當列表容量擴展為原理來的2倍時，計算對應下標時，低位的數據的 hash 值和 n-1 相與的計算結果是其本身。2^n-1 = 111..1,對應n位二進制數，其數值不會對hash計算的結果產生影響。如果不是2的冪次方，任意一位都可能為0，如容量為10的話，對應二進制數為1010，相與的結果，其中有兩位數字必定為0，增大了碰撞的結果，分析到這裡，真的不得不感慨這樣設計的巧妙。

存儲結構

來段代碼看下執行結果：

   static void mapResize(){          Map<Object, Object> map = new HashMap<>(0);          map.put("x.1", "1.1");      }  

.

hash 碰撞

    static void mapResize(){          Map<Object, Object> map = new HashMap<>(0);          map.put("x.1", "1.1");          //繼續執行          for (int i = 0; i < 9; i++) {              map.put("x.2"+i, "2."+i);          }          for (int i = 0; i < 3; i++) {              map.put("x.3"+i, "3."+i);          }          map.put("x.4", "3.1");        }  

.

擴容中的分鏈操作

如果存儲的數據結構是鏈表桶，在發生哈希碰撞時，會將原來的鏈表同過計算e.hash&oldCap==0分成兩條鏈表,再將兩條鏈表散列到新數組的不同位置上。

.

擴容前數組長度為8，擴容為原數組長度的2倍即16。原來有一條鏈表在tab[2]的位置，擴容以後仍然有一條鏈在tab[2]的位置，另外一條鏈在tab[2+8]即tab[10]的位置處。

鏈表

我們知道當通過hash運算，分佈在一個桶中的元素髮生哈希碰撞的話，會採用鏈表的形式進行存儲。

紅黑樹

那麼，當桶中的元素超過一定範圍之後，由於鏈表遍歷查找複雜度較高，O(n)，而紅黑樹的遍歷查找複雜度為O(log(n))，若桶中鏈表元素超過8時，會自動轉化成紅黑樹；若桶中元素小於等於6時，樹結構還原成鏈表形式。

為什麼此處要使用6和8呢？

紅黑樹的平均查找長度是log(n)，長度為8，查找長度為log(8)=3，鏈表的平均查找長度為n/2，當長度為8時，平均查找長度為8/2=4，這才有轉換成樹的必要；鏈表長度如果是小於等於6，6/2=3，雖然速度也很快的，但是轉化為樹結構和生成樹的時間並不會太短。

中間有個差值7可以防止鏈表和樹之間頻繁的轉換。假設一下，如果設計成鏈表個數超過8則鏈錶轉換成樹結構，鏈表個數小於8則樹結構轉換成鏈表，如果一個HashMap不停的插入、刪除元素，鏈表個數在8左右徘徊，就會頻繁的發生樹轉鏈表、鏈錶轉樹，效率會很低。

其實,源碼中也給出了解釋

Because TreeNodes are about twice the size of regular nodes, we  use them only when bins contain enough nodes to warrant use  (see TREEIFY_THRESHOLD). And when they become too small (due to  removal or resizing) they are converted back to plain bins.  In  usages with well-distributed user hashCodes, tree bins are  rarely used.  Ideally, under random hashCodes, the frequency of  nodes in bins follows a Poisson distribution  (http://en.wikipedia.org/wiki/Poisson_distribution) with a  parameter of about 0.5 on average for the default resizing  threshold of 0.75, although with a large variance because of  resizing granularity. Ignoring variance, the expected  occurrences of list size k are (exp(-0.5)    pow(0.5, k) /  factorial(k)). The first values are:    0:    0.60653066  1:    0.30326533  2:    0.07581633  3:    0.01263606  4:    0.00157952  5:    0.00015795  6:    0.00001316  7:    0.00000094  8:    0.00000006  more: less than 1 in ten million  

大致翻譯過來意思是：因為樹節點的大小約為常規節點的兩倍，所以我們僅在桶中包含足夠多的節點數時才會使用它。當他們在重新調整大小時，如果開始變得更小，此時會轉換為鏈表結構的桶進行存儲。在使用上會通過他們的hash值來使其分佈的更加均勻，樹結構桶是極少被使用的。理想情況下，通過hash運算生成的隨機值，桶中節點的分佈概率是符合泊松分佈的。默認調整大小的平均參數為0.5，擴容閾值為0.75。儘管粒度調整會帶來一些較大幅度的衝突。忽略這些衝突，預期不同列表容量大小而發生的衝突的出現的概率是 exp(-0.5) pow(0.5, k) / factorial(k)。在長度為8時，其發生衝突的概率為千萬分之一。

性能提升

篇末，我們來梳理下 JDK8 較 JDK7 中，做的一些調整來實現的性能上的提升。

數據存儲結構

JDK7中使用數組+鏈表來實現，JDK8 使用的數組+鏈表+紅黑樹

hash算法優化

JDK7默認初始化大小16，加載因子0.75。如果傳入了size，會變為大於等於當前值的2的n次方的最小的數。

 // Find a power of 2 >= toSize   int capacity = roundUpToPowerOf2(toSize);  

為什麼是2次方數？因為 indexFo r方法的時候，h&(length-1) , length是2的次方，那麼 length-1 總是00011111等後面都是1的數，h&它之後，其實就相當於取余，與的效率比取余高，所以用了這種方式達到高效率。 下面是 JDK7 的 indexfor 的實現：

 /**       * Returns index for hash code h.       */      static int indexFor(int h, int length) {          // assert Integer.bitCount(length) == 1 : "length must be a non-zero power of 2";          return h & (length-1);      }  

另外在hash函數裏面方法裏面，數會經過右移，為什麼要右移？因為取余操作都是操作低位，hash碰撞的概率會提高，為了減少hash碰撞，右移就可以將高位也參與運算，減少了hash碰撞。 哈希函數如下：

/**       * Retrieve object hash code and applies a supplemental hash function to the       * result hash, which defends against poor quality hash functions.  This is       * critical because HashMap uses power-of-two length hash tables, that       * otherwise encounter collisions for hashCodes that do not differ       * in lower bits. Note: Null keys always map to hash 0, thus index 0.       */      final int hash(Object k) {          int h = hashSeed;          if (0 != h && k instanceof String) {              return sun.misc.Hashing.stringHash32((String) k);          }            h ^= k.hashCode();            // This function ensures that hashCodes that differ only by          // constant multiples at each bit position have a bounded          // number of collisions (approximately 8 at default load factor).          h ^= (h >>> 20) ^ (h >>> 12);          return h ^ (h >>> 7) ^ (h >>> 4);      }  

而前文分析的 JDK8 的哈希函數比較簡單，可以直接通過右移實現。

/* ---------------- Static utilities -------------- */        /**       * Computes key.hashCode() and spreads (XORs) higher bits of hash       * to lower.  Because the table uses power-of-two masking, sets of       * hashes that vary only in bits above the current mask will       * always collide. (Among known examples are sets of Float keys       * holding consecutive whole numbers in small tables.)  So we       * apply a transform that spreads the impact of higher bits       * downward. There is a tradeoff between speed, utility, and       * quality of bit-spreading. Because many common sets of hashes       * are already reasonably distributed (so don't benefit from       * spreading), and because we use trees to handle large sets of       * collisions in bins, we just XOR some shifted bits in the       * cheapest possible way to reduce systematic lossage, as well as       * to incorporate impact of the highest bits that would otherwise       * never be used in index calculations because of table bounds.       */      static final int hash(Object key) {          int h;          return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);      }  

為什麼 JDK8 的哈希函數會變簡單？JDK8 中我們知道用的是鏈表過度到紅黑樹，效率會提高，所以 JDK8 提高查詢效率的地方由紅黑樹去實現，沒必要像 JDK7 通過複雜友誼來減少碰撞(避免鏈表過長)。

擴容機制優化

• JDK8 增加了鏈表數據處理的優化，通過擴容進行分鏈，分割鏈表數據，操作高位和低位的數據，減少移動帶來的性能損耗。
• JDK7 用的是頭插法，而 JDK8 及之後使用的都是尾插法，那麼他們為什麼要這樣做呢？因為 JDK7 是用單鏈表進行的縱向延伸，當採用頭插法時會容易出現逆序且環形鏈表死循環問題。但是在 JDK8 之後是因為加入了紅黑樹使用尾插法，能夠避免出現逆序且鏈表死循環的問題。
• 擴容後數據存儲位置的計算方式也不一樣：
• 在 JDK7 的時候是直接用hash值和需要擴容的二進制數進行&（這裡就是為什麼擴容的時候為啥一定必須是2的多少次冪的原因所在，因為如果只有2的n次冪的情況時最後一位二進制數才一定是1，這樣能最大程度減少hash碰撞）（hash值 & length-1）
• 而在 JDK8 的時候直接用了 JDK7 的時候計算的規律，也就是擴容前的原始位置+擴容的大小值=JDK8的計算方式，而不再是 JDK7 的那種異或的方法。但是這種方式就相當於只需要判斷Hash值的新增參與運算的位是0還是1就直接迅速計算出了擴容後的儲存方式。

.

在計算hash值的時候，JDK7 用了9次擾動處理=4次位運算+5次異或，而 JDK8 只用了2次擾動處理=1次位運算+1次異或。

• 擴容流程對比

.

元素節點操作複雜度

• JDK7 的時候使用的是數組+ 單鏈表的數據結構。
• 但是在 JDK8 及之後時，使用的是數組+鏈表+紅黑樹的數據結構（當鏈表的深度達到8的時候，也就是默認閾值，就會自動擴容把鏈錶轉成紅黑樹的數據結構來把時間複雜度從O(n)變成O(log(n)提高了效率）

.

擴容時機

JDK7的時候是先進行擴容後進行插入，而在JDK8的時候則是先插入後進行擴容。

• JDK8

//其實就是當這個Map中實際插入的鍵值對的值的大小如果大於這個默認的閾值的時候（初始是16*0.75=12）的時候才會觸發擴容，  //這個是在JDK1.8中的先插入後擴容  if (++size > threshold)              resize();  

其實這個問題也是 JDK8 對 HashMap 中，主要是因為對鏈錶轉為紅黑樹進行的優化，因為你插入這個節點的時候有可能是普通鏈表節點，也有可能是紅黑樹節點，

• JDK7

void addEntry(int hash, K key, V value, int bucketIndex) {          //這裡當前數組如果大於等於12（假如）閾值的話，並且當前的數組的Entry數組還不能為空的時候就擴容      　　if ((size >= threshold) && (null != table[bucketIndex])) {  　　　　　　 //擴容數組，比較耗時         　　 resize(2 * table.length);          　　hash = (null != key) ? hash(key) : 0;          　　bucketIndex = indexFor(hash, table.length);      　　}        　　createEntry(hash, key, value, bucketIndex);  　　}     void createEntry(int hash, K key, V value, int bucketIndex) {      　　Entry<K,V> e = table[bucketIndex];  　　　　//把新加的放在原先在的前面，原先的是e，現在的是new，next指向e     　　 table[bucketIndex] = new Entry<>(hash, key, value, e);//假設現在是new      　　size++;  　　}  

在 JDK7 中的話，是先進行擴容後進行插入的，就是當你發現你插入的桶是不是為空，如果不為空說明存在值就發生了hash衝突，那麼就必須得擴容，但是如果不發生Hash衝突的話，說明當前桶是空的（後面並沒有掛有鏈表），那就等到下一次發生 Hash 衝突的時候在進行擴容，但是當如果以後都沒有發生hash衝突產生，那麼就不會進行擴容了，減少了一次無用擴容，也減少了內存的使用。

JDK8 動態轉換鏈表和紅黑樹結構（以8為分界線）

前文已分析，不再贅述，源碼中也有對應解釋。

總結

哈希表如何解決Hash衝突

.

為什麼HashMap具備下述特點：鍵-值（key-value）都允許為空、線程不安全、不保證有序、存儲位置隨時間變化

.

為什麼 HashMap 中 String、Integer 這樣的包裝類適合作為 key 鍵

.

HashMap 中的 key若 Object類型， 則需實現哪些方法

.

REFERENCES

• JDK7與JDK8中HashMap的實現
• JDK7 HashMap實現原理及源碼分析
• 由阿里巴巴Java開發規約HashMap條目引發的故事
• HashMap源碼註解 之 靜態工具方法hash()、tableSizeFor()（四）
• 從JDK7與JDK8對比詳細分析HashMap的原理與優化
• HashMap原理jdk7和jdk8的區別
• 美團面試題：Hashmap的結構，1.7和1.8有哪些區別，史上最深入的分析
• Java源碼分析：HashMap 1.8 相對於1.7 到底更新了什麼？
• HashMap實現原理及源碼分析
• JDK7與JDK8中HashMap的實現

.