本文已收錄于:https://github.com/danmuking/all-in-one(持續更新)
數據結構
JDK1.8 之前
JDK1.8 之前 HashMap 采用 數組和鏈表 結合的數據結構。如下圖:
HashMap 將 key 的 hashCode 經過擾動函數處理過后得到 hash 值,然后通過(n - 1) & hash
判斷當前元素存放的位置(n 指的是數組的長度),如果當前位置存在元素的話,就判斷該元素與要存入的元素的 hash 值以及 key 是否相同,如果相同的話,直接覆蓋,不相同就通過拉鏈法解決沖突。
什么是拉鏈法?
拉鏈法就是將鏈表和數組相結合。也就是說創建一個鏈表數組,數組中每一格就是一個鏈表。若遇到哈希沖突,則將沖突的值加到鏈表中即可。
JDK1.8 之后
在JDK1.8之中,由于考慮到搜索鏈表的時間復雜度為 O(n),鏈表過長的話,遍歷鏈表將會花費過長的時間,因此,JDK1.8中,對 HashMap 的數據結構進行了一定的優化。
當滿足一定條件時,會將鏈表轉換為紅黑樹結構(具體細節見下文),搜索紅黑樹的時間復雜度為 O(logn),這可以為 HashMap 帶來一定的性能提升
在 JDK1.8 中,還對 HashMap 中計算 hashcode 的函數進行了優化
JDK 1.8 的 hash 方法 相比于 JDK 1.7 hash 方法更加簡化。
static final int hash(Object key) {int h;// key.hashCode():返回散列值也就是hashcode// ^:按位異或// >>>:無符號右移,忽略符號位,空位都以0補齊return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}
對比一下 JDK1.7 的 HashMap 的 hash 方法源碼.
static int hash(int h) {// This function ensures that hashCodes that differ only by// constant multiples at each bit position have a bounded// number of collisions (approximately 8 at default load factor).h ^= (h >>> 20) ^ (h >>> 12);return h ^ (h >>> 7) ^ (h >>> 4);
}
JDK1.8 的 hash 擾動次數更少,性能更好。
類圖
HashMap 的繼承關系很簡單,繼承于 AbstractMap 并且是實現了 Cloneable 和 Serializable 接口
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable
- AbstractMap : 表明它是一個 Map,支持實現 k-v 形式的查詢操作
- Cloneable :表明它具有拷貝能力,可以進行深拷貝或淺拷貝操作。
- Serializable : 表明它可以進行序列化操作,也就是可以將對象轉換為字節流進行持久化存儲或網絡傳輸
核心源碼解讀
重要變量:
// 默認的初始容量是16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
// 最大容量
static final int MAXIMUM_CAPACITY = 1 << 30;
// 默認的負載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
// 當桶上的結點數大于等于這個值時會轉成紅黑樹
static final int TREEIFY_THRESHOLD = 8;
// 當桶上的結點數小于等于這個值時樹轉鏈表
static final int UNTREEIFY_THRESHOLD = 6;
// 鏈表轉化為紅黑樹所需的最小數組容量
// 鏈表轉換為紅黑樹需要MIN_TREEIFY_CAPACITY和TREEIFY_THRESHOLD兩個條件同時滿足
static final int MIN_TREEIFY_CAPACITY = 64;
// 存儲元素的數組,總是2的冪次倍
transient Node<k,v>[] table;
// 存放元素的個數,注意這個不等于數組的長度。
transient int size;
// 閾值(容量*負載因子) 當size超過閾值時,會進行擴容
int threshold;
// 負載因子
final float loadFactor;
loadFactor 負載因子
loadFactor 負載因子是控制 HashMap 中數組存放數據的疏密程度,loadFactor 影響的是單位長度的數組中存放的數據數量,loadFactor 越大,單位長度的數組中存放的元素就越多,反之,loadFactor 越小,單位長度的數組中存放的元素就越少
loadFactor 太大會導致導致查找元素效率低,因為數據密集,平均鏈表長度更長。
loadFactor 太小導致數組的利用率低,存放的數據會很分散,很多數組位置空閑
loadFactor 的默認值為 0.75f 是官方給出的一個比較好的臨界值。
threshold 閾值
threshold = capacity * loadFactor
,當size > threshold
的時候,就會進行數組擴容。
Node 節點
// 繼承自 Map.Entry<K,V>
static class Node<K,V> implements Map.Entry<K,V> {final int hash;// 哈希值,存放元素到hashmap中時用來與其他元素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; }// 重寫hashCode()方法public final int hashCode() {return Objects.hashCode(key) ^ Objects.hashCode(value);}public final V setValue(V newValue) {V oldValue = value;value = newValue;return oldValue;}// 重寫 equals() 方法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;}
}
初始化
HashMap 中有四個構造方法,其中常用的有三個:
// 默認構造函數。
public HashMap() {// 懶加載,初始化的時候不分配空間。this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted}// 指定初始化容量的構造函數public HashMap(int initialCapacity) {this(initialCapacity, DEFAULT_LOAD_FACTOR);}// 指定“容量大小”和“負載因子”的構造函數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;// 初始容量暫時存放到 threshold ,在resize中再賦值給 newCap 進行table初始化// tableSizeFor的作用是找到和initialCapacity最接近的2的次冪,// 因為 HashMap 的容量一定是2的次冪this.threshold = tableSizeFor(initialCapacity);}static final int tableSizeFor(int cap) {int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
HashMap 同樣使用懶加載,第一次初始化的時候不分配數組空間,第一次空間分配發生在以第一次調用 put 方法時
put 方法
步驟
向 HashMap 中添加元素需要經過一下步驟:
- 計算 key 的 hash 值,并定位到對應的數組位置
- 如果定位到的數組位置沒有元素 就直接插入。
- 如果定位到的數組位置有元素,就和要插入的 key 比較。如果 key 相同就直接覆蓋,如果 key 不相同,就需要遍歷所有元素,如果找到相同的 key 就覆蓋,否則插入到末尾。
public V put(K key, V value) {// 實際調用 putVal 方法return putVal(hash(key), key, value, false, 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未初始化或者長度為0,進行擴容// 這里會將 table 賦值給 tab,tab.length 賦值給 n,接下來經常有這種寫法if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// (n - 1) & hash 確定元素存放在哪個桶中,桶為空,新生成結點放入桶中(此時,這個結點是放在數組中)if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);// 桶中已經存在元素(處理hash沖突)else {Node<K,V> e; K k;//快速判斷第一個節點table[i]的key是否與插入的key一樣,若相同就直接使用插入的值p替換掉舊的值e。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 {// 遍歷鏈表,如果在鏈表中找到相同的key就覆蓋,否則添加到尾部for (int binCount = 0; ; ++binCount) {// 已經到達鏈表的尾部if ((e = p.next) == null) {// 在尾部插入新結點p.next = newNode(hash, key, value, null);// 結點數量達到閾值(默認為 8 ),執行 treeifyBin 方法// 這個方法會根據 HashMap 數組來決定是否轉換為紅黑樹。// 只有當數組長度大于或者等于 64 的情況下,才會執行轉換紅黑樹操作,以減少搜索時間。// 否則,就是只是對數組擴容。if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);// 跳出循環break;}// 如果找到key相同的節點,結束遍歷,接下來將會覆蓋舊值if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))// 相等,跳出循環break;// 用于遍歷桶中的鏈表,與前面的e = p.next組合,可以遍歷鏈表p = e;}}// 表示在桶中找到key值、hash值與插入元素相等的結點if (e != null) {// 記錄e的valueV oldValue = e.value;// onlyIfAbsent為false或者舊值為nullif (!onlyIfAbsent || oldValue == null)//用新值替換舊值e.value = value;// 訪問后回調afterNodeAccess(e);// 返回舊值return oldValue;}}// 結構性修改++modCount;// 實際大小大于閾值則擴容if (++size > threshold)resize();// 插入后回調afterNodeInsertion(evict);return null;
}
get 方法
步驟
從 HashMap 中獲取元素的步驟與插入元素的步驟差不多:
- 計算 key 對應的 hash 值,計算對應的數組位置
- 快速比較對應數組位置的元素是不是要獲取的元素,是則返回,不是則遍歷對應位置的鏈表
- 遍歷鏈表,如果找到相同的key則返回,否則遍歷到最后一個節點返回 null
public V get(Object key) {Node<K,V> e;return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {// 比較第一個元素是否相等,相等則快速返回if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;// 遍歷鏈表if ((e = first.next) != null) {// 在樹中getif (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);// 在鏈表中getdo {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;
}
resize 方法
擴容也是 HashMap 中一個重要的知識點。進行擴容,將會遍歷原數組中的所有數據,并重新計算其在新數組中的對應位置,將其轉移到新數組中。因此 resize 相當耗時,在程序中需要盡量避免。
很多文章會說在resize的過程中會**重新計算hash的值,這是錯誤的。**在擴容時將會沿用之前的hash,僅僅重新計算在新數組中的位置。
步驟
resize 的流程很簡單,大體來說只有兩步:
- 創建原數組2倍大小的數組
- 將原數組元素移動到新數組
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倍else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}// 下面兩個條件是初始化 HashMap 時觸發else if (oldThr > 0) // initial capacity was placed in threshold// 創建對象時初始化容量大小放在threshold中,此時只需要將其作為新的數組容量newCap = oldThr;else {// signifies using defaults 無參構造函數創建的對象在這里計算容量和閾值newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}if (newThr == 0) {// 創建時指定了初始化容量或者負載因子,在這里進行閾值初始化,// 或者擴容前的舊容量小于16,在這里計算新的resize上限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;if (oldTab != null) {// 把每個bucket都移動到新的buckets中for (int j = 0; j < oldCap; ++j) {Node<K,V> e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null)// 只有一個節點,直接計算元素新的位置即可newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode)// 將紅黑樹拆分成2棵子樹,如果子樹節點數小于等于 UNTREEIFY_THRESHOLD(默認為 6),則將子樹轉換為鏈表。// 如果子樹節點數大于 UNTREEIFY_THRESHOLD,則保持子樹的樹結構。((TreeNode<K,V>)e).split(this, newTab, j, oldCap);else {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;elseloTail.next = e;loTail = e;}// 原索引+oldCapelse {if (hiTail == null)hiHead = e;elsehiTail.next = e;hiTail = e;}} while ((e = next) != null);// 原索引放到bucket里if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 原索引+oldCap放到bucket里if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}}return newTab;
}
resize 如何計算數據在新數組中位置?
if ((e.hash & oldCap) == 0) {// 。。。
// 原索引+oldCap
else {// 。。。
}
為什么可以使用(e.hash & oldCap) == 0
來計算數據在新數組中的位置呢?因為在 HashMap 中數組的長度一定是2的次冪(不知道的話請重新閱讀上面的內容),并且擴容時新數組大小是舊數組的 2 倍。因此可以通過 hash 是否可以被2整除來決定元素應該放在原下標
還是原下標+舊數組長度
。代碼中使用e.hash & oldCap
位運算來加快計算速度,舉個簡單的例子來理解一下這個運算:
hash 實際上是一個int類型,轉換為二進制就是32個bit。假設現在有一個大小為16的HashMap,數組下標范圍就是0~15,因此可以使用hash的最后4個bit進行表示:
在擴容后大小變為16*2=32,數組下標范圍為0~31,可以使用hash的最后5個bit進行表示:
可以發現,每擴容一次就需要多使用一個bit,而根據多使用的這個bit是0還是1就可以將元素分布到原下標
和原下標+舊數組長度
。
點關注,不迷路
好了,以上就是這篇文章的全部內容了,如果你能看到這里,非常感謝你的支持!
如果你覺得這篇文章寫的還不錯, 求點贊👍 求關注?? 求分享👥 對暖男我來說真的 非常有用!!!
白嫖不好,創作不易,各位的支持和認可,就是我創作的最大動力,我們下篇文章見!
如果本篇博客有任何錯誤,請批評指教,不勝感激 !
最后推薦我的IM項目DiTing(https://github.com/danmuking/DiTing-Go),致力于成為一個初學者友好、易于上手的 IM 解決方案,希望能給你的學習、面試帶來一點幫助,如果人才你喜歡,給個Star?叭!