1、HashMap源碼解析（JDK8） 基礎原理： 對比上一篇《Java中的容器（集合）之ArrayList源碼解析》而言，本篇只解析HashMap常用的核心方法的源碼。 HashMap是一個以鍵值對存儲的容器。 hashMap底層實現為數組+鏈表+紅黑樹（鏈表超過8時轉為紅黑樹，JDK7為數組+鏈 ...
1、HashMap源碼解析（JDK8）
基礎原理：
- 對比上一篇《Java中的容器（集合）之ArrayList源碼解析》而言，本篇只解析HashMap常用的核心方法的源碼。
- HashMap是一個以鍵值對存儲的容器。
- hashMap底層實現為數組+鏈表+紅黑樹（鏈表超過8時轉為紅黑樹，JDK7為數組+鏈表）。
- HashMap會根據key的hashCode得到對應的hash值，再去數組中找尋對應的數組位置（下標）。
- hash方法如下：
static final int hash(Object key) { int h; //hashCode()返回散列值，這是Object中的一個方法 // ^ 按位異或，& 按位與，|按位或；&&邏輯與，||邏輯或 // >>> 無符號右移 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }
HashMap的一些屬性：
- 關於其中載入因數屬性（DEFAULT_LOAD_FACTOR ，loadFactor），主要是針對元素量而言，越大元素放的越多，空間利用率高，不過容易碰撞，查找時間多；越小元素放的越少，不容易碰撞，不過浪費空間，查找時間少。
- 關於threshold屬性，它是HashMap的擴容標準，計算規則為容量*載入因數，比如預設情況為16*0.75=12，達到這個值的時候就會進行擴容（擴容操作比較耗費性能）。
- 源碼及釋義如下：
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { // 序列號 private static final long serialVersionUID = 362498820763181265L; // 預設的初始容量，需為2的冪次方（為了減少哈希碰撞），<< 表示左移，運算規則為乘以2的n次方，1<<4=16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 最大容量，如果由某個帶參構造函數隱式的指定了更高的值，需為2的冪次方且小於1 << 30 static final int MAXIMUM_CAPACITY = 1 << 30; // 構造函數中未指定時使用的載入因數，即預設載入因數 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 當傳入的節點大於2且至少為8的時候，鏈表節點轉為紅黑樹 static final int TREEIFY_THRESHOLD = 8; // 當節點小於為6的時候，紅黑樹退化為鏈表 static final int UNTREEIFY_THRESHOLD = 6; // 紅黑樹中對應的最小表容量應該最少為4*TREEIFY_THRESHOLD，以避免在調整大小和紅黑樹閾值之間的衝突。 static final int MIN_TREEIFY_CAPACITY = 64; // 在第一次使用的時候初始化表，且根據需要設置大小，分配的大小總是2的冪次方 transient Node<k,v>[] table; // 保存元素的集，需要註意的是，它使用的AbstractMap欄位是keySet()和values()。 transient Set<map.entry<k,v>> entrySet; // 此映射中包含的鍵值映射數，鍵值是一個整體，不等於數組的長度（因為存在哈希碰撞之後的鏈表和紅黑樹） transient int size; // 每次擴容和更改map結構的計數器 transient int modCount; // 下一個要調整大小的大小值（容量*載入因數） int threshold; // hash表的載入因數 final float loadFactor; }
靜態內部類Node：
- 源碼及釋義如下：
//靜態內部類，實現了Map.Entry<K,V>介面 static class Node<K,V> implements Map.Entry<K,V> { final int hash;//哈希值，用於與其他元素的哈希值進行比較 final K key;//鍵 V value;//值 Node<K,V> next;//下一個節點 //構造器 Node(int hash, K key, V value, Node<K,V> next) { this.hash = hash; this.key = key; this.value = value; this.next = next; } public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
JDK8增加了樹節點靜態內部類用於紅黑樹：
- 部分源碼及釋義如下：
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K, V> parent; // red-black tree links 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 */ public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; this.threshold = tableSizeFor(initialCapacity); } /** * 指定容量以及預設載入因數0.75構造一個空的HashMap */ public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } /** * 以預設容量16以及預設載入因數0.75構造一個空的HashMap */ public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted } /** * 以另一個Map的鍵值對構造一個新的HashMap。新HashMap的容量最少足夠存儲舊HashMap的鍵值對數，載入因數為預設載入因數0.75 */ public HashMap(Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }
- 其中第四個構造函數有用到putMapEntries()這個方法，其源碼如下：
/** * 實現map.putall和map構造函數 */ final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) { int s = m.size(); //判斷m是否為空 if (s > 0) { //判斷table是否初始化 if (table == null) { // pre-size //計算m的總容量，計算規則為使用容量/載入因數+1 float ft = ((float)s / loadFactor) + 1.0F; //將m總容量與HashMap規定的最大容量相比得到最終容量 int t = ((ft < (float)MAXIMUM_CAPACITY) ? (int)ft : MAXIMUM_CAPACITY); //判斷最終容量是否大於擴容閾值（擴容閾值計算規則：容量*載入因數） if (t > threshold) threshold = tableSizeFor(t); } //如果m的鍵值對數大於擴容閾值，則進行擴容 else if (s > threshold) resize(); //將m中的鍵值對添加到新HashMap中 for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) { K key = e.getKey(); V value = e.getValue(); putVal(hash(key), key, value, false, evict); } } }
- 針對putMapEntries()方法中的擴容操作，可以查看resize()方法，源碼及釋義如下：
/** * 初始化表或者將表容量翻倍，如果為空則分配初始容量，否則以2的冪次方擴容，需要保持索引一致 * @return */ 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; } //判斷舊容量的兩倍容量（左移表示乘以2的n次方）是否小於最大容量，且舊容量是否大於等於預設容量 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) //擴容兩倍 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 //否則新容量設置為預設容量（因為舊容量小於0） newCap = DEFAULT_INITIAL_CAPACITY; //新閾值設置為預設容量乘以預設載入因數，即16*0.75 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<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //此方法返回的新table //如果舊table為空，則初始化 table = newTab; //否則將舊table的值放入新table if (oldTab != null) { //舊table的值迴圈放入新table for (int j = 0; j < oldCap; ++j) { Node<K,V> e; //判斷當前節點是否有值 if ((e = oldTab[j]) != null) { //舊table節點置為空 oldTab[j] = null; //如果該節點沒有子節點，則返回新table，元素放入的位置為e的哈希值按位與（新容量-1） if (e.next == null) newTab[e.hash & (newCap - 1)] = e; //否則如果該節點屬於紅黑樹節點，將其切割賦給新紅黑樹 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); //保持索引一致 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; //舊索引 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); //舊索引放入table if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //新索引放入table if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
- 關於put的源碼及釋義如下（對應原理可以查看《Java中的容器（集合）》第七條）：
//put元素到map中 public V put(K key, V value) { //實際調用的是putVal()方法 return putVal(hash(key), key, value, false, true); } //putVal()方法用於實際操作插入元素 final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //table未初始化，調用resize()進行擴容（使用的都是預設值） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //判斷(n - 1) & hash]索引處的table是否為空，為空，則插入新節點（table為空，此時插入的節點是在數組中） if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); //table不為空 else { Node<K,V> e; K k; //判斷節點的hash以及key是否相等，是則覆蓋。 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //否則如果屬於樹節點，使用putTreeVal插入節點數據（putTreeVal是針對紅黑樹的putVal方法），有興趣的可以看一下putTreeVal方法 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); //如果大於規則節點數（8），則轉為紅黑樹存儲 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); //跳出迴圈 break; } //判斷插入元素與鏈表中原有元素的hash以及key是否相等 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) //相等，跳出迴圈 break; //迴圈鏈表 p = e; } } //存在鍵值對的key 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; }
- 關於get的源碼及釋義如下：
//通過指定key從map中get值 public V get(Object key) { Node<K,V> e; //實際調用的是getNode()方法 return (e = getNode(hash(key), key)) == null ? null : e.value; } //getNode()方法用於實際操作查詢元素值 final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //判斷存在table是否初始化 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //總是檢查第一個節點，如果第一個節點與需要查詢的節點的hash以及key相等，則返回第一個節點 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; //如果存在多個節點 if ((e = first.next) != null) { //如果屬於紅黑樹，則調用紅黑樹中的getTreeNode方法查詢，有興趣的可以看一下getTreeNode方法 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); //否則在鏈表中查詢 do { //如果鏈表節點與需要查詢的節點的hash以及key相等，則返回鏈表節點 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } return null; }
（以上所有內容皆為個人筆記，如有錯誤之處還望指正。）
