Java中HashMap源碼分析
- 2019 年 10 月 4 日
- 筆記
JDK的1.6,1.7版本中，HashMap使用數組+鏈表來實現的，通過計算Map中的key的的hash值來確定該key在數組中index的位置。計算key在數組中位置，使用的是hash演算法，HashMap中定位到桶的位置 是根據Key的hash值與數組的長度取模來計算的。取模可以改為：hashCode & （length – 1)。看下JDK8中的hash 演算法：
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
在此版本中，同一hash值的鏈表都存儲在一個鏈表裡。但是當位於一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。
在JDK1.8中，HashMap使用的是數組+鏈表+紅黑樹實現。當鏈表長度超過閾值（8）時，將鏈錶轉換為紅黑樹，這樣大大減少了查找時間。
HashMap是基於hashing的原理，我們使用put(key, value)存儲對象到HashMap中，使用get(key)從HashMap中獲取對象。當我們給put()方法傳遞鍵和值時，先對Key調用hashCode方法，來計算hash值，返回的hash值用來找bucket對象，來放entry鍵值對。
HashMap創建的時候，會創建一個Entry數組，HashMap是有entry數組組成的，每個Entry對象都是null。每個Entry存放的有hash,key,value,next。
HashMap中最主要的兩個方法：get(key)和put(key, value)；
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key), key)) == null ? null : e.value; } /** * Implements Map.get and related methods * * @param hash hash for key * @param key the key * @return the node, or null if none */ final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //該hash值所在的元素是保存在table[(tab.length-1)&hash]這個位置，所以需要確保在該位置上有Node if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //判斷是否保存在該鏈表的第一個位置 if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
首先，如果key為null，則直接從哈希表的第一個位置table[0]對應的鏈表上查找。記住，key為null的鍵值對永遠都放在以table[0]為頭結點的鏈表中，當然不一定是存放在頭結點table[0]中。如果key不為null，則先求的key的hash值，根據hash值找到在table中的索引，在該索引對應的單鏈表中查找是否有鍵值對的key與目標key相等，有就返回對應的value，沒有則返回null。
get(key)方法時獲取key的hash值，計算hash&(n-1)得到在鏈表數組中的位置first=tab[hash&(n-1)],先判斷first的key是否與參數key相等，不等就遍歷後面的鏈表找到相同的key值返回對應的Value值即可。
put(key, value)方法：
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; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } 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; }
1，判斷鍵值對數組tab[]是否為空或為null，否則以默認大小resize()；2，根據鍵值key計算hash值得到插入的數組索引i，如果tab[i]==null，直接新建節點添加，否則轉入33，判斷當前數組中處理hash衝突的方式為鏈表還是紅黑樹(check第一個節點類型即可),分別處理紅黑樹源碼：
//紅黑樹 static final class TreeNode<k,v> extends LinkedHashMap.Entry<k,v> { TreeNode<k,v> parent; // 父節點 TreeNode<k,v> left; //左子樹 TreeNode<k,v> right;//右子樹 TreeNode<k,v> prev; // needed to unlink next upon deletion boolean red; //顏色屬性 TreeNode(int hash, K key, V val, Node<k,v> next) { super(hash, key, val, next); } //返回當前節點的根節點 final TreeNode<k,v> root() { for (TreeNode<k,v> r = this, p;;) { if ((p = r.parent) == null) return r; r = p; } }
HashMap 各常量、成員變數作用
// 創建 HashMap 時未指定初始容量情況下的默認容量 2 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; 3 4 // HashMap 的最大容量 5 static final int MAXIMUM_CAPACITY = 1 << 30; 6 7 // HashMap 默認的裝載因子,當 HashMap 中元素數量超過 容量*裝載因子 時，進行 resize()操作 8 static final float DEFAULT_LOAD_FACTOR = 0.75f; 9 10 // 用來確定何時將解決 hash 衝突的鏈錶轉變為紅黑樹 11 static final int TREEIFY_THRESHOLD = 8; 12 13 // 用來確定何時將解決 hash 衝突的紅黑樹轉變為鏈表 14 static final int UNTREEIFY_THRESHOLD = 6; 15 16 /* 當需要將解決 hash 衝突的鏈錶轉變為紅黑樹時，需要判斷下此時數組容量， 若是由於數組容量太小（小於 MIN_TREEIFY_CAPACITY ）導致的 hash衝突太多，則不進行鏈錶轉變為紅黑樹操作，轉為利用 resize() 函數對 hashMap 擴容 */ 17 static final int MIN_TREEIFY_CAPACITY = 64;
載入因子（默認0.75）：map中值如果填充比很大，說明利用的空間很多，如果一直不進行擴容的話，鏈表就會越來越長，這樣查找的效率很低，擴容之後，將原來鏈表數組的每一個鏈表分成奇偶兩個子鏈表分別掛在新鏈表數組的散列位置，這樣就減少了每個鏈表的長度，增加查找效率。
1 //保存Node<K,V>節點的數組 2 transient Node<K,V>[] table; 3 4 //由 hashMap 中 Node<K,V> 節點構成的 set 5 transient Set<Map.Entry<K,V>> entrySet; 6 7 //記錄 hashMap 當前存儲的元素的數量 8 transient int size; 9 10 //記錄 hashMap 發生結構性變化的次數（注意 value 的覆蓋不屬於結構性變化） 11 transient int modCount; 12 13 //threshold的值應等於 table.length * loadFactor, size 超過這個值時進行 resize()擴容 14 int threshold; 15 16 //記錄 hashMap 裝載因子 17 final float loadFactor;
HasMap的擴容機制resize()源碼：
構造hash表時，如果不指明初始大小，默認大小為16（即Node數組大小16），如果Node[]數組中的元素達到（填充比Node.length）重新調整HashMap大小 變為原來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 */ final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; /*如果舊錶的長度不是空*/ if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } /*把新表的長度設置為舊錶長度的兩倍，newCap=2*oldCap*/ else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) /*把新表的門限設置為舊錶門限的兩倍，newThr=oldThr*2*/ newThr = oldThr << 1; // double threshold } /*如果舊錶的長度的是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); } 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;//把新表賦值給table if (oldTab != null) {//原表不是空要把原表中數據移動到新表中 /*遍歷原來的舊錶*/ for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null)//說明這個node沒有鏈表直接放在新表的e.hash & (newCap - 1)位置 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); /*如果e後邊有鏈表,到這裡表示e後面帶著個單鏈表，需要遍歷單鏈表，將每個結點重*/ 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為偶數一隊，e.hash&oldCap為奇數一對 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) {//lo隊不為null，放在新表原位置 loTail.next = null; newTab[j] = loHead; } if (hiTail != null) {//hi隊不為null，放在新表j+oldCap位置 hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
在java jdk8中對HashMap的源碼進行了優化，在jdk7中，HashMap處理「碰撞」的時候，都是採用鏈表來存儲，當碰撞的結點很多時，查詢時間是O（n）。在jdk8中，HashMap處理「碰撞」增加了紅黑樹這種數據結構，當碰撞結點較少時，採用鏈表存儲，當較大時（>8個），採用紅黑樹（特點是查詢時間是O（logn））存儲（有一個閥值控制，大於閥值(8個)，將鏈表存儲轉換成紅黑樹存儲）。
你可能還知道哈希碰撞會對hashMap的性能帶來災難性的影響。如果多個hashCode()的值落到同一個桶內的時候，這些值是存儲到一個鏈表中的。最壞的情況下，所有的key都映射到同一個桶中，這樣hashmap就退化成了一個鏈表——查找時間從O(1)到O(n)。
隨著HashMap的大小的增長，get()方法的開銷也越來越大。由於所有的記錄都在同一個桶里的超長鏈表內，平均查詢一條記錄就需要遍歷一半的列表。
JDK1.8HashMap的紅黑樹是這樣解決的：
如果某個桶中的記錄過大的話（當前是TREEIFY_THRESHOLD = 8），HashMap會動態的使用一個專門的treemap實現來替換掉它。這樣做的結果會更好，是O(logn)，而不是糟糕的O(n)。
關於HashMap的總結：
1.當兩個對象的hashcode相同會發生什麼？
HashMap底層是由數組以及鍵值對組成的，它之所以有相當快的查詢速度主要是因為它是通過計算散列碼來確定存儲位置的，HashMap中主要是通過key的hashCode來計算hash值的，只要hashCode相同，計算出來的hash值就一樣。如果存儲的對象對多了，就有可能不同的對象所算出來的hash值是相同的，這就出現了所謂的hash衝突，解決hash衝突的方法有很多，HashMap底層是通過鏈表來解決hash衝突的。
哈希表是由數組+鏈表組成的，因為hashcode相同，所以它們的bucket位置相同，『碰撞』會發生。因為HashMap使用LinkedList存儲對象，這個Entry會存儲在LinkedList中，這個存儲的位置一般情況是通過hash(key)%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數組下標為12的位置。
2.如果兩個鍵的hashcode相同，你如何獲取值對象？
HashMap會使用鍵對象的hashcode找到bucket位置，找到bucket位置之後，會調用keys.equals()方法去找到LinkedList中正確的節點，最終找到要找的值對象。從HashMap中get元素時，首先計算key的hashCode，找到數組中對應位置的某一元素，然後通過key的equals方法在對應位置的鏈表中找到需要的元素。
3.如果HashMap的大小超過了負載因子(load factor)定義的容量，怎麼辦
默認的負載因子大小為0.75，也就是說，當一個map填滿了75%的bucket時候，和其它集合類(如ArrayList等)一樣，將會創建原來HashMap大小的兩倍的bucket數組，來重新調整map的大小，並將原來的對象放入新的bucket數組中。這個過程叫作rehashing，因為它調用hash方法找到新的bucket位置。
4.重新調整HashMap大小存在什麼問題?
當重新調整HashMap大小的時候，確實存在條件競爭，因為如果兩個執行緒都發現HashMap需要重新調整大小了，它們會同時試著調整大小。在調整大小的過程中，存儲在LinkedList中的元素的次序會反過來，因為移動到新的bucket位置的時候，HashMap並不會將元素放在LinkedList的尾部，而是放在頭部，這是為了避免尾部遍歷(tail traversing)。如果條件競爭發生了，那麼就死循環了。
