「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) {
- // ……
- 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初始容量為什么是2的n次冪及擴容為什么是2倍的形式
HashMap 是如何導致死循環的
HashMap會導致死循環是在jdk1.7中，由于擴容時的操作是使用頭插法，在多線程的環境下可能產生循環鏈表，由此導致了死循環。在jdk1.8中改為使用尾插法，避免了該死循環的情況。
