我們再看看構造方法
構造方法
/** * Constructs an empty HashMap 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. * 傳入初始容量大小，使用默認負載因子值 來初始化HashMap對象 */public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR);}/** * Constructs an empty HashMap 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 an empty HashMap 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 * 傳入初始容量大小和負載因子 來初始化HashMap對象 */public HashMap(int initialCapacity, float loadFactor) { // 初始容量不能小於0，否則報錯 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 初始容量不能大於最大值，否則為最大值 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; //負載因子不能小於或等於0，不能為非數字 if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // 初始化負載因子 this.loadFactor = loadFactor; // 初始化threshold大小 this.threshold = tableSizeFor(initialCapacity);}/** * Returns a power of two size for the given target capacity. * 找到大於或等於 cap 的最小2的整數次冪的數 */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;}在這源碼中，loadFactor負載因子是一個非常重要的參數，因為他能夠反映HashMap桶數組的使用情況， 這樣的話，HashMap的時間複雜度就會出現不同的改變。
當這個負載因子屬於低負載因子的時候，HashMap所能夠容納的鍵值對數量就是偏少的，擴容後，重新將鍵值對 存儲在桶數組中，鍵與鍵之間產生的碰撞會下降，鏈表的長度也會隨之變短。
但是如果增加負載因子當這個負載因子大於1的時候，HashMap所能夠容納的鍵值對就會變多，這樣碰撞就會增加， 這樣的話鏈表的長度也會增加，
一般情況下負載因子我們都不會去修改。都是默認的0.75。
擴容機制
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 */final Node[] resize() { //引用擴容前的Entry數組 Node[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { // 擴容前的數組大小如果已經達到最大(2^30)了 //在這裡去判斷是否達到最大的大小 if (oldCap >= MAXIMUM_CAPACITY) { //修改閾值為int的最大值(2^31-1)，這樣以後就不會擴容了 threshold = Integer.MAX_VALUE; return oldTab; } // 如果擴容後小於最大值 而且 舊數組桶大於初始容量16， 閾值左移1(擴大2倍) 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 // 如果數組桶容量<=0 且 舊閾值 <=0 // 新容量=默認容量 // 新閾值= 負載因子*默認容量 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 如果新閾值為0 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; // 如果舊數組桶不是空，則遍歷桶數組，並將鍵值對映射到新的桶數組中 //在這裡還有一點詭異的，1.7是不存在後邊紅黑樹的，但是1.8就是有紅黑樹 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 // 如果不是紅黑樹，那也就是說他鏈表長度沒有超過8，那麼還是鏈表， //那麼還是會按照鏈表處理 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;} 所以說在經過resize這個方法之後，元素的位置要麼就是在原來的位置，要麼就是在原來的位置移動2次冪的位置上。 源碼上的註釋也是可以翻譯出來的
/** * 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，則分配符合字段閾值中保存的初始容量目標。 否則，因為我們使用的是2次冪擴展， 所以每個bin中的元素必須保持相同的索引，或者在新表中以2的偏移量移動。 */ final Node[] resize() ..... 所以說他的擴容其實很有意思，就有了三種不同的擴容方式了，
- 在HashMap剛初始化的時候，使用默認的構造初始化，會返回一個空的table，並且 thershold為0，因此第一次擴容的時候默認值就會是16. 同時再去計算thershold = DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY = 16*0.75 = 12.
- 如果說指定初始容量的初始HashMap的時候，那麼這時候計算這個threshold的時候就變成了 threshold = DEFAULT_LOAD_FACTOR * threshold(當前的容量)
- 如果HashMap不是第一次擴容，已經擴容過了，那麼每次table的容量和threshold也會變成原來的2倍。
之前看1.7的源碼的時候，是沒有這個紅黑樹的，而是在1.8 之後做了相應的優化。 使用的是2次冪的擴展(指長度擴為原來2倍)。 而且在擴充HashMap的時候，不需要像JDK1.7的實現那樣重新計算hash，這樣子他就剩下了計算hash的時間了。
看完這個源碼，翻譯了一節節的英文，算是大致明白了一點源碼內容了，有什麼討論的問題咱們可以一起討論一下，感謝觀看。
分享到:
閱讀更多 科技伍小黑 的文章
