怎么理解Java中HashMap底層實現、加載因子、容量值及死循環

這篇文章主要介紹“怎么理解Java中HashMap底層實現、加載因子、容量值及死循環”，在日常操作中，相信很多人在怎么理解Java中HashMap底層實現、加載因子、容量值及死循環問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”怎么理解Java中HashMap底層實現、加載因子、容量值及死循環”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

HashMap 簡介

HashMap是一個基于哈希表實現的無序的key-value容器，它鍵和值允許設置為 null，同時它是線程不安全的。

HashMap 底層實現

•  在jdk 1.7中HashMap是以數組+鏈表的實現的

•  在jdk1.8開始引入紅黑樹，HashMap底層變成了數組+鏈表+紅黑樹實現

紅黑樹簡介

紅黑樹是一種特殊的平衡二叉樹，它有如下的特征：

•  節點是紅色或黑色

•  根節點是黑色的

•  所有葉子都是黑色。（葉子是NULL節點）

•  每個紅色節點的兩個子節點都是黑色的（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）

•  從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

所以紅黑樹的時間復雜度為: O(lgn)。

jdk1.8：數組+鏈表+紅黑樹

HashMap的底層首先是一個數組，元素存放的數組索引值就是由該元素的哈希值（key-value中key的哈希值）確定的，這就可能產生一種特殊情況——不同的key哈希值相同。

在這樣的情況下，于是引入鏈表，如果key的哈希值相同，在數組的該索引中存放一個鏈表，這個鏈表就包含了所有key的哈希值相同的value值，這就解決了哈希沖突的問題。

但是如果發生大量哈希值相同的特殊情況，導致鏈表很長，就會嚴重影響HashMap的性能，因為鏈表的查詢效率需要遍歷所有節點。于是在jdk1.8引入了紅黑樹，當鏈表的長度大于8，且HashMap的容量大于64的時候，就會將鏈表轉化為紅黑樹。

// jdk1.8  // HashMap#putVal  // binCount 是該鏈表的長度計數器，當鏈表長度大于等于8時，執行樹化方法  // TREEIFY_THRESHOLD = 8  if (binCount >= TREEIFY_THRESHOLD - 1)      treeifyBin(tab, hash);  // HashMap#treeifyBin      final void treeifyBin(Node<K,V>[] tab, int hash) {      int n, index; Node<K,V> e;      // MIN_TREEIFY_CAPACITY=64      // 若 HashMap 的大小小于64，僅擴容，不樹化      if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)          resize();      else if ((e = tab[index = (n - 1) & hash]) != null) {          TreeNode<K,V> hd = null, tl = null;          do {              TreeNode<K,V> p = replacementTreeNode(e, null);              if (tl == null)                  hd = p;              else {                  p.prev = tl;                  tl.next = p;              }              tl = p;          } while ((ee = e.next) != null);          if ((tab[index] = hd) != null)              hd.treeify(tab);      }  }

加載因子為什么是0.75

所謂的加載因子，也叫擴容因子或者負載因子，它是用來進行擴容判斷的。

假設加載因子是0.5，HashMap初始化容量是16，當HashMap中有16 * 0.5=8個元素時，HashMap就會進行擴容操作。

而HashMap中加載因子為0.75，是考慮到了性能和容量的平衡。

由加載因子的定義，可以知道它的取值范圍是(0, 1]。

•  如果加載因子過小，那么擴容門檻低，擴容頻繁，這雖然能使元素存儲得更稀疏，有效避免了哈希沖突發生，同時操作性能較高，但是會占用更多的空間。

•  如果加載因子過大，那么擴容門檻高，擴容不頻繁，雖然占用的空間降低了，但是這會導致元素存儲密集，發生哈希沖突的概率大大提高，從而導致存儲元素的數據結構更加復雜（用于解決哈希沖突），最終導致操作性能降低。

•  還有一個因素是為了提升擴容效率。因為HashMap的容量（size屬性，構造函數中的initialCapacity變量）有一個要求：它一定是2的冪。所以加載因子選擇了0.75就可以保證它與容量的乘積為整數。 

// 構造函數  public HashMap(int initialCapacity, float loadFactor) {      // &hellip;&hellip;      this.loadFactor = loadFactor;// 加載因子      this.threshold = tableSizeFor(initialCapacity);  }  /**   * Returns a power of two size for the given target capacity.返回2的冪   * MAXIMUM_CAPACITY = 1 << 30   */  static final int tableSizeFor(int cap) {      int n = cap - 1;      n |= n >>> 1;      n |= n >>> 2;     n |= n >>> 4;      n |= n >>> 8;      n |= n >>> 16;      return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;  }

HashMap 的容量為什么是2的 n 次冪

HashMap的默認初始容量是16，而每次擴容是擴容為原來的2倍。這里的16和2倍就保證了HashMap的容量是2的n次冪，那么這樣設計的原因是什么呢？

原因一：與運算高效

與運算&，基于二進制數值，同時為1結果為1，否則就是0。如1&1=1,1&0=0,0&0=0。使用與運算的原因就是對于計算機來說，與運算十分高效。

原因二：有利于元素充分散列，減少 Hash 碰撞

在給HashMap添加元素的putVal函數中，有這樣一段代碼：

// n為容量，hash為該元素的hash值  if ((p = tab[i = (n - 1) & hash]) == null)      tab[i] = newNode(hash, key, value, null);

它會在添加元素時，通過i = (n - 1) & hash計算該元素在HashMap中的位置。

當 HashMap 的容量為 2 的 n 次冪時，他的二進制值是100000……（n個0），所以n-1的值就是011111……（n個1），這樣的話(n - 1) & hash的值才能夠充分散列。

舉個例子，假設容量為16，現在有哈希值為1111，1110，1011，1001四種將被添加，它們與n-1(15的二進制=01111)的哈希值分別為1111、1110、1110、1011，都不相同。

而假設容量不為2的n次冪，假設為10，那么它與上述四個哈希值進行與運算的結果分別是：0101、0100、0001、0001。

可以看到后兩個值發生了碰撞，從中可以看出，非2的n次冪會加大哈希碰撞的概率。所以 HashMap 的容量設置為2的n次冪有利于元素的充分散列。

HashMap 是如何導致死循環的

HashMap會導致死循環是在jdk1.7中，由于擴容時的操作是使用頭插法，在多線程的環境下可能產生循環鏈表，由此導致了死循環。在jdk1.8中改為使用尾插法，避免了該死循環的情況。

到此，關于“怎么理解Java中HashMap底層實現、加載因子、容量值及死循環”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！