HashMap源碼解析(JDK1.8)

---

目錄

定義

構造函數

數據結構

存儲實現源碼分析

刪除操作源碼分析

hashMap遍歷和異常解析

---

1. 定義

HashMap實現了Map接口，繼承AbstractMap。其中Map接口定義了鍵映射到值的規則，而AbstractMap類提供 Map 接口的骨干實現，以最大限度地減少實現此接口所需的工作，其實AbstractMap類已經實現了Map

---

2. 構造函數

HashMap提供了四個構造函數：

HashMap()：構造一個具有默認初始容量 (16) 和默認加載因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity)：構造一個帶指定初始容量和默認加載因子 (0.75) 的空 HashMap。

HashMap(int initialCapacity, float loadFactor)：構造一個帶指定初始容量和加載因子的空 HashMap。

HashMap(Map<? extends K, ? extends V> m)：使用與指定映射相同的映射構造一個新的hashmap，默認加載因子0.75，和初始化足夠容納指定映射中的映射的初始容量。

在這里提到了兩個參數：初始容量，加載因子。這兩個參數是影響HashMap性能的重要參數，其中容量表示哈希表中桶的數量，初始容量是創建哈希表時的容量，加載因子是哈希表在其容量自動增加之前可以達到多滿的一種尺度，它衡量的是一個散列表的空間的使用程度，負載因子越大表示散列表的裝填程度越高，反之愈小。對于使用鏈表法的散列表來說，查找一個元素的平均時間是O(1+a)，因此如果負載因子越大，對空間的利用更充分，然而后果是查找效率的降低；如果負載因子太小，那么散列表的數據將過于稀疏，對空間造成嚴重浪費。系統默認負載因子為0.75，一般情況下我們是無需修改的。

HashMap是一種支持快速存取的數據結構，要了解它的性能必須要了解它的數據結構。

---

3. 數據結構

我們知道在Java中最常用的兩種結構是數組和模擬指針(引用)，幾乎所有的數據結構都可以利用這兩種來組合實現，HashMap也是如此。實際上HashMap是一個“鏈表散列”。

在Jdk1.8中HashMap的實現方式做了一些改變，但是基本思想還是沒有變得，只是在一些地方做了優化，下面來看一下這些改變的地方,**數據結構的存儲由數組+鏈表的方式，變化為數組+鏈表+紅黑樹的存儲方式，當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹。**在性能上進一步得到提升。

從上圖我們可以發現數據結構由數組+鏈表組成，一個長度為16的數組中，每個元素存儲的是一個鏈表的頭結點。那么這些元素是按照什么樣的規則存儲到數組中呢。一般情況是通過hash(key.hashCode())%len獲得，也就是元素的key的哈希值對數組長度取模得到。比如上述哈希表中，12%16=12,28%16=12,108%16=12,140%16=12。所以12、28、108以及140都存儲在數組下標為12的位置。

從上圖我們可以看出HashMap底層實現還是數組，只是數組的每一項都是一條鏈，當鏈表長度超過了閾值，將鏈表轉換為紅黑樹。其中參數initialCapacity就代表了該數組的長度。

下面為HashMap雙參數構造函數的源碼：

public HashMap(int initialCapacity, float loadFactor) {// 判斷容量initialCapacity 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);//tableSizeFor：返回傳入initialCapacity的最小接近的幾次冪。this.loadFactor = loadFactor;this.threshold = tableSizeFor(initialCapacity);}//返回給定目標容量的兩倍冪，比如傳入15，返回的是16，即返回傳入值最小接近幾次冪的值。 static final int tableSizeFor(int cap) {//比如傳入12，n = cap - 1 = 11；int n = cap - 1;// 0000 1011 = 11 初始 n// 0000 0101 = 5 n >>> 1// 0000 1111 = 15 結果：n = 15 接著做下面的運算，最后結果還是 15 + 1 = 16n |= 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(Map<? extends K, ? extends V> m)

public HashMap(Map<? extends K, ? extends V> m) {this.loadFactor = DEFAULT_LOAD_FACTOR;putMapEntries(m, false);}final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {int s = m.size();if (s > 0) {// 判斷table是否為null， 源碼：transient Node<K,V>[] table;if (table == null) { // pre-size//獲取數組里面的值，如果數組里面的值大于MAXIMUM_CAPACITY，則取MAXIMUM_CAPACITY，否則就是ft。//比如說map的大小為15，那么ft = 20；float ft = ((float)s / loadFactor) + 1.0F;int t = ((ft < (float)MAXIMUM_CAPACITY) ?(int)ft : MAXIMUM_CAPACITY);//判斷是否達到最大用來，t > threshold，那么進行tablesize重計算。if (t > threshold) threshold = tableSizeFor(t);}else if (s > threshold)//如果s大于threshold（threshold= capacity * load factor），那么需要擴容resize();for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {//獲取key，value，再根據key獲取hash值，再把值放到對應的地址。K key = e.getKey();V value = e.getValue();putVal(hash(key), key, value, false, evict);}}}

再看看** putVal(hash(key), key, value, false, evict);方法中的hash方法**

//獲取key的hash值static final int hash(Object key) {int h;// int 32位 1111 1111 1111 1111 0000 0000 0000 0000// 對象的hashCode值 ^(異或：相同為1，不同為0) 對象的hashCode值的高位(前16位) // 目的：提高hashCode的隨機性return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

---

4. 存儲實現

源碼：

public V put(K key, V value) {//根據傳入參數key，獲取hashCode的值return putVal(hash(key), key, value, false, true);}//onlyIfAbsent = false;(默認)// evict = true;(默認)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數組是否為null或長度為0.if ((tab = table) == null || (n = tab.length) == 0)// 初始化table長度n = (tab = resize()).length;// 假設 i = 16； i = (n - 1) & hash ； i表示元素在tab數組中存儲的位置。// p = tab[i], 判斷 p鏈表是否為null// (n - 1) & hash 取余運算，目的優化計算速度。if ((p = tab[i = (n - 1) & hash]) == null)// 如果為null，創建節點，直接存放到tab[i]位置tab[i] = newNode(hash, key, value, null);else {// tab[i] 有元素Node<K,V> e; K k;// hash值相同，key相同，是同一元素，那么直接=。if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))e = p;// 判斷是否為樹結構， JDK1.8 有了紅黑樹的優化方案。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的下一個元素 = newNode(hash, key, value, null)；p.next = newNode(hash, key, value, null);// 判斷當前鏈表的數量是否大于數結構的閾值if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st// 如果大于則轉換結構// 鏈表 --> 紅黑樹 (優化查詢性能)// static final int TREEIFY_THRESHOLD = 8; 鏈表長度達到7時轉換成紅黑樹treeifyBin(tab, hash);break;}// 當前的鏈表包含要插入的值，結束遍歷if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}// 判斷插入的值是否存在hashmap中，如果存在老值if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}// 修改次數+1++modCount;// 判斷當前數組大小是否大于閾值，大于則要擴容。if (++size > threshold)resize();afterNodeInsertion(evict);return null;}

再看看 resize擴容方法

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;}// oldCap << 1 乘以2 = newCap。 MAXIMUM_CAPACITY = 1 << 30else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&oldCap >= DEFAULT_INITIAL_CAPACITY)// oldThr 乘以2 = newThrnewThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaults// 如果調用的無參構造方法，則進入這個分支。newCap=初始容量（8）；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"})// 創建一個新的 *2 的容量的數組Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];table = newTab;// 準備重新對元素進行定位。if (oldTab != null) {for (int j = 0; j < oldCap; ++j) {Node<K,V> e;// 獲取第j個位置的元素。if ((e = oldTab[j]) != null) {// 清空原數組oldTab[j] = null;// 判斷原有j位置上是否還有元素if (e.next == null)// 如果沒有，則重新計算，進行元素保存// 例如16，e.hash & 31 = 新元素的位置 newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 紅黑樹拆分((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else { // preserve orderNode<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do {// 遍歷鏈表，將鏈表節點按順序進行分組next = e.next;// old鏈表添加到一組if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;}// 計算原有元素在擴容后的位置。else {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);if (loTail != null) {loTail.next = null;newTab[j] = loHead;}if (hiTail != null) {hiTail.next = null;// 原位置 j + 原容量 = 新的位置。 newTab[j + oldCap] = hiHead;}}}}}return newTab;}

---

5. 刪除操作源碼分析

源碼：

public V remove(Object key) {Node<K,V> e;return (e = removeNode(hash(key), key, null, false, true)) == null ?null : e.value;}final Node<K,V> removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node<K,V>[] tab; Node<K,V> p; int n, index;if ((tab = table) != null && (n = tab.length) > 0 &&// 元素要存儲的位置p(p = tab[index = (n - 1) & hash]) != null) {Node<K,V> node = null, e; K k; V v;// hash沒有沖突情況if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))//定位刪除節點nodenode = p;// 有沖突，不只是一個元素在同一位置上else if ((e = p.next) != null) {// 判斷是否為紅黑樹，定位刪除元素if (p instanceof TreeNode)node = ((TreeNode<K,V>)p).getTreeNode(hash, key);else {do {//那就是鏈表結構，定位刪除元素if (e.hash == hash &&((k = e.key) == key ||(key != null && key.equals(k)))) {node = e;break;}p = e;} while ((e = e.next) != null);}}// node要刪除的元素if (node != null && (!matchValue || (v = node.value) == value ||(value != null && value.equals(v)))) {if (node instanceof TreeNode)// 紅黑樹刪除節點((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);else if (node == p)// 鏈表刪除節點tab[index] = node.next;else// 否則判斷數組中p位置的對象下一個元素 = 刪除元素的下一個元素。p.next = node.next;++modCount;--size;afterNodeRemoval(node);return node;}}return null;}

---

6. hashMap遍歷和異常解析

測試代碼：

HashMap<Integer, String> map = new HashMap<>(16);map.put(20, "abc");map.put(3, "abc");map.put(12, "abc");map.put(5, "abc");map.put(16, "abc");System.out.println("遍歷結果：");for (Integer key : map.keySet()) {System.out.print(key + " -> ");}

輸出結果：

當調整put順序，代碼如下：

HashMap<Integer, String> map = new HashMap<>(16);map.put(12, "abc");map.put(5, "abc");map.put(16, "abc");map.put(20, "abc");map.put(3, "abc");System.out.println("遍歷結果：");for (Integer key : map.keySet()) {System.out.print(key + " -> ");}

輸出結果：

可以看到：兩者的輸出結果是一樣的。也就是說，輸入的順序是無法保證，但不管怎么put操作，輸出的結果是一樣的。因為它是按hash結構進行輸出的，如下

源碼如下：

final Node<K,V> nextNode() {Node<K,V>[] t;Node<K,V> e = next;if (modCount != expectedModCount)// 如果迭代過程中進行操作，modCount 會被修改，所以就會報錯：ConcurrentModificationException()throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();if ((next = (current = e).next) == null && (t = table) != null) {// 尋找數組中下一個hash槽不為null的節點。do {} while (index < t.length && (next = t[index++]) == null);}return e;}

遍歷的時候進行添加或刪除等操作，會報錯，附上報錯截圖：

---

參考博客：

java提高篇（二三）-----HashMap：https://www.cnblogs.com/chenssy/p/3521565.html

HashMap實現原理及源碼分析詳解：https://www.bilibili.com/video/av53287823/?p=1

總結

以上是生活随笔為你收集整理的HashMap源码解析(JDK1.8)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。