【Java】HashMap原始碼分析——常用方法詳解
上一篇介紹了HashMap的基本概念,這一篇著重介紹HasHMap中的一些常用方法:
put()
get()
**resize()**
首先介紹resize()這個方法,在我看來這是HashMap中一個非常重要的方法,是用來調整HashMap中table的容量的,在很多操作中多需要重新計算容量。
原始碼如下:
1 final Node<K,V>[] resize() { 2Node<K,V>[] oldTab = table; 3int oldCap = (oldTab == null) ? 0 : oldTab.length; 4int oldThr = threshold; 5int newCap, newThr = 0; 6if (oldCap > 0) { 7if (oldCap >= MAXIMUM_CAPACITY) { 8threshold = Integer.MAX_VALUE; 9return oldTab; 10} 11else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 12oldCap >= DEFAULT_INITIAL_CAPACITY) 13newThr = oldThr << 1; // double threshold 14} 15else if (oldThr > 0) // initial capacity was placed in threshold 16newCap = oldThr; 17else {// zero initial threshold signifies using defaults 18newCap = DEFAULT_INITIAL_CAPACITY; 19newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 20} 21if (newThr == 0) { 22float ft = (float)newCap * loadFactor; 23newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 24(int)ft : Integer.MAX_VALUE); 25} 26threshold = newThr; 27@SuppressWarnings({"rawtypes","unchecked"}) 28Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 29table = newTab; 30if (oldTab != null) { 31for (int j = 0; j < oldCap; ++j) { 32Node<K,V> e; 33if ((e = oldTab[j]) != null) { 34oldTab[j] = null; 35if (e.next == null) 36newTab[e.hash & (newCap - 1)] = e; 37else if (e instanceof TreeNode) 38((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 39else { // preserve order 40Node<K,V> loHead = null, loTail = null; 41Node<K,V> hiHead = null, hiTail = null; 42Node<K,V> next; 43do { 44next = e.next; 45if ((e.hash & oldCap) == 0) { 46if (loTail == null) 47loHead = e; 48else 49loTail.next = e; 50loTail = e; 51} 52else { 53if (hiTail == null) 54hiHead = e; 55else 56hiTail.next = e; 57hiTail = e; 58} 59} while ((e = next) != null); 60if (loTail != null) { 61loTail.next = null; 62newTab[j] = loHead; 63} 64if (hiTail != null) { 65hiTail.next = null; 66newTab[j + oldCap] = hiHead; 67} 68} 69} 70} 71} 72return newTab; 73}
可以看到這段程式碼非常龐大,其內容可以分為兩大部分:
第一部分計算並生成新的雜湊表(空表):
1 // 記錄原表 2 Node<K,V>[] oldTab = table; 3 // 得到原來雜湊表的總長度,及原來總容量 4 int oldCap = (oldTab == null) ? 0 : oldTab.length; 5 // 得到原來最佳容量 6 int oldThr = threshold; 7 // 存放新的總容量、新最佳容量的變數 8 int newCap, newThr = 0; 9 if (oldCap > 0) { 10 // 原來總容量達到或超過HashMap的最大容量,則最佳容量設定為int型別的最大值 11 // 且原來容量不變,直接返回,不做後需調整 12if (oldCap >= MAXIMUM_CAPACITY) { 13threshold = Integer.MAX_VALUE; 14return oldTab; 15} 16// 讓新的總容量等於原來容量的二倍 17else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && 18oldCap >= DEFAULT_INITIAL_CAPACITY) 19// 新的最佳容量也變為原來的二倍 20newThr = oldThr << 1; 21 } 22 // 原來總容量為0,將新的總容量設定為最佳容量,構造方法出入引數是一個派生的Map的時候,就會使用派生的Map計算出新的最佳容量 23 else if (oldThr > 0) 24newCap = oldThr; 25 else { 26 // 原來總容量和原來最佳容量都沒有定義 27 // 新的總容量設為預設值16 28 // 新的最佳容量=預設負載因子×預設容量=0.75×16=12 29newCap = DEFAULT_INITIAL_CAPACITY; 30newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); 31 } 32 // 判斷上述操作後新的最佳容量是否計算,若沒有,就利用負載因子和新的總容量計算 33 if (newThr == 0) { 34float ft = (float)newCap * loadFactor; 35newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? 36(int)ft : Integer.MAX_VALUE); 37 } 38 // 更新當前的最佳容量 39 threshold = newThr; 40 @SuppressWarnings({"rawtypes","unchecked"}) 41 // 生成新的雜湊表,即一維陣列 42 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 43 // 更新雜湊表 44 table = newTab;
可以看出上述操作僅僅是生成了一張大小合適的雜湊表,但表還是空的,後面的操作就是把以前的表中的元素重新排列,移動到當前表中合適的位置!
第二部分將原表元素移動到新表合適的位置:
1 // 先判斷原表是或否為空 2 if (oldTab != null) { 3// 遍歷原表(一維陣列)中的所有元素, 4for (int j = 0; j < oldCap; ++j) { 5// 記錄原來一維陣列中下標為j的元素 6Node<K,V> e; 7// 只對有效元素進行操作 8if ((e = oldTab[j]) != null) { 9//將原表中的元素置空 10oldTab[j] = null; 11if (e.next == null) 12// 當前元素沒有後繼,那麼直接把它放在新表中合適位置 13// 其中e.hash & (newCap - 1)在我上一篇部落格有介紹 14// 就是以該節點的hash值和新表總容量取餘,將餘數作為下標 15newTab[e.hash & (newCap - 1)] = e; 16else if (e instanceof TreeNode) 17// 當前元素有後繼,且後繼是紅黑樹 18// 進行有關紅黑樹的相應操作 19// 這裡不詳細介紹紅黑樹的操作 20((TreeNode<K,V>)e).split(this, newTab, j, oldCap); 21else { 22// 這裡就進行有關連結串列的移動 23// 這兩組結點變數,分別代表兩條不同連結串列的頭和尾 24// 低位的頭和尾 25Node<K,V> loHead = null, loTail = null; 26// 高位的頭和尾 27Node<K,V> hiHead = null, hiTail = null; 28// 下一節點 29Node<K,V> next; 30do { 31// 讓next等於當前結點的後繼結點 32next = e.next; 33// 這個位運算實際上判斷的是該節點在新表中的位置是否發生改變 34// 成立則說明沒有改變,還是原來表中下標為j的位置 35if ((e.hash & oldCap) == 0) { 36// 若是首結點,則讓低位的頭等於當前結點 37if (loTail == null) 38loHead = e; 39else 40// 若不是首結點,則讓低位的尾等於當前結點 41loTail.next = e; 42// 讓低位的尾移動到當前 43loTail = e; 44} 45// 這裡就說明其在新表中的位置發生了改變,則要將其放入另一條連結串列 46else { 47// 若是首結點,則讓高位的頭等於當前結點 48if (hiTail == null) 49hiHead = e; 50else 51// 若不是首結點,則讓高位的尾等於當前結點 52hiTail.next = e; 53// 讓高位的尾移動到當前 54hiTail = e; 55} 56} while ((e = next) != null); 57// 原來位置的這條連結串列還存在 58if (loTail != null) { 59// 置空低位的尾的next 60loTail.next = null; 61// 將該連結串列的頭結點放入新表下標為j的位置,即原表中的原位置 62newTab[j] = loHead; 63} 64// 新位置上的連結串列存在 65if (hiTail != null) { 66// 置空高位的尾的next 67hiTail.next = null; 68// 將該連結串列的頭結點放入新表中下標為j+原表長度的位置 69newTab[j + oldCap] = hiHead; 70} 71} 72} 73} 74 } 75 return newTab;
連結串列的移動如圖:
可以看出,這個方法可以使得單個結點重新雜湊,連結串列可以拆分成兩條,紅黑樹重新移動,這樣使得新的雜湊表分佈比以前均勻!
下面來分析put方法:
原始碼如下:
1public V put(K key, V value) { 2return putVal(hash(key), key, value, false, true); 3}
這裡我們可以知道其呼叫了內部的一個putVal方法:
首先第一個引數是通過內部的hash方法(在前一篇部落格有介紹過)計算出鍵物件的hash(int型別)值,再把key和value物件傳過去,置於後面兩個引數先不著急
先來看下putVal方法是如何說明的:
1 /** 2* Implements Map.put and related methods 3* 4* @param hash hash for key 5* @param key the key 6* @param value the value to put 7* // 看以看出,put方法傳入的onlyIfAbsent是false,那麼就會改變原來已存在的值 8* @param onlyIfAbsent if true, don't change existing value 9* // 這個引數先不考慮,往後慢慢分析 10* @param evict if false, the table is in creation mode. 11* @return previous value, or null if none 12*/ 13final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)
該方法內容:
1// 用於儲存原表 2Node<K,V>[] tab; 3// 儲存下標為hash的結點 4Node<K,V> p; 5// n用來記錄表長 6int n, i; 7// 先檢查原表是否存在,或者是空表 8if ((tab = table) == null || (n = tab.length) == 0) 9// 如果為空就生成一張大小為16的新表 10n = (tab = resize()).length; 11if ((p = tab[i = (n - 1) & hash]) == null) 12// 如果以該方法形參hash對錶長取餘,令其作為下標的表中的元素為空,那麼就產生一個新結點放在這個位置 13tab[i] = newNode(hash, key, value, null); 14else { 15// 如果該結點不空,那麼就會出現兩種情況:連結串列和紅黑樹 16Node<K,V> e; K k; 17if (p.hash == hash && 18((k = p.key) == key || (key != null && key.equals(k)))) 19// 如果當前結點的hash並且key值(指標值和內容值)相等,由於onlyIfAbsent是false,那麼就會改變這個結點的V值,先用e將其儲存起來 20e = p; 21else if (p instanceof TreeNode) 22// 如果當前結點是一棵紅黑樹,那麼就進行紅黑樹的平衡,這裡不討論紅黑樹的問題 23e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); 24else { 25// 這裡就對連結串列進行操作 26// 從頭開始遍歷這條連結串列 27for (int binCount = 0; ; ++binCount) { 28if ((e = p.next) == null) { 29// 如果該節點的next為空 30// 就需要新增一個結點追加其後 31p.next = newNode(hash, key, value, null); 32if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 33// 這裡進行紅黑樹閾值的判斷,由於TREEIFY_THRESHOLD預設值是8,binCount是從0開始,那麼當連結串列長度大於等於8的時候,就將該連結串列轉換成紅黑樹,並且結束迴圈 34treeifyBin(tab, hash); 35break; 36} 37// 這裡和之前的判斷是一樣的 38if (e.hash == hash && 39((k = e.key) == key || (key != null && key.equals(k)))) 40break; 41// 讓p = p->next 42p = e; 43} 44} 45// 若e非空,則就是說明原表中存在hash值相等,且key的值或內容相同的結點 46if (e != null) { 47// 將原來的V值儲存 48V oldValue = e.value; 49// 判斷是否是需要進行覆蓋原來V值的操作 50if (!onlyIfAbsent || oldValue == null) 51// 覆蓋原來的V值 52e.value = value; 53// 這個方法是一個空的方法,預留的一個操作,不用去管它 54afterNodeAccess(e); 55// 由於在這裡面的操作只是替換了原來的V值,並沒有改變原來表的大小,直接返回oldValue 56return oldValue; 57} 58} 59// 運算元自增 60++modCount; 61// 實際大小自增 62// 若其大於最佳容量進行擴容的操作,使其分佈均勻 63if (++size > threshold) 64resize(); 65// 這也是一個空的方法,預留操作 66afterNodeInsertion(evict); 67// 並沒有替換原來的V值,返回null 68return null;
下來是get方法,邏輯相對簡單不難分析:
1 public V get(Object key) { 2Node<K,V> e; 3return (e = getNode(hash(key), key)) == null ? null : e.value; 4 }
同樣也是通過hash方法計算出key物件的hash值,呼叫內部的getNode方法:
1 final Node<K,V> getNode(int hash, Object key) { 2// 記錄表物件 3Node<K,V>[] tab; 4// 記錄第一個結點和當前節點 5Node<K,V> first, e; 6// 記錄表長 7int n; 8// 記錄K值 9K k; 10// 表非空或者長度大於0才對其操作 11// 並且key的hash值對錶長取餘為下標,其所對應的雜湊表中的結點存在 12if ((tab = table) != null && (n = tab.length) > 0 && 13(first = tab[(n - 1) & hash]) != null) { 14// 當前結點滿足情況,直接返回給該節點 15if (first.hash == hash && 16((k = first.key) == key || (key != null && key.equals(k)))) 17return first; 18// 後面就分為兩種情況:在紅黑樹或者連結串列中查詢 19if ((e = first.next) != null) { 20// 當前結點是紅黑樹,進行紅黑樹的查詢 21if (first instanceof TreeNode) 22return ((TreeNode<K,V>)first).getTreeNode(hash, key); 23// 進行連結串列的遍歷 24do { 25if (e.hash == hash && 26((k = e.key) == key || (key != null && key.equals(k)))) 27return e; 28} while ((e = e.next) != null); 29} 30} 31return null; 32 }
若有不足還請指出!