Java源碼解析之HashMap的put、resize方法詳解
一、HashMap 簡(jiǎn)介
HashMap 底層采用哈希表結(jié)構(gòu) 數(shù)組加鏈表加紅黑樹(shù)實(shí)現(xiàn)，允許儲(chǔ)存null鍵和null值
數(shù)組優(yōu)點(diǎn)：通過(guò)數(shù)組下標(biāo)可以快速實(shí)現(xiàn)對(duì)數(shù)組元素的訪問(wèn)，效率高
鏈表優(yōu)點(diǎn)：插入或刪除數(shù)據(jù)不需要移動(dòng)元素，只需要修改節(jié)點(diǎn)引用效率高
二、源碼分析
2.1 繼承和實(shí)現(xiàn)
public class HashMap<K,V> extends AbstractMap<K,V>
implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
繼承AbstractMap<K,V>
實(shí)現(xiàn)了map接口 cloneable接口和可序列化接口
2.2 屬性
//hashmap默認(rèn)容量為 16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 HashMap默認(rèn)容量 16 //最大容量為2的30 1073741824 static final int MAXIMUM_CAPACITY = 1 << 30; // //默認(rèn)加載因子為0.75 static final float DEFAULT_LOAD_FACTOR = 0.75f; //鏈表轉(zhuǎn)為紅黑樹(shù)的閾值 static final int TREEIFY_THRESHOLD = 8; //紅黑樹(shù)轉(zhuǎn)為鏈表的閾值 static final int UNTREEIFY_THRESHOLD = 6; //鏈表轉(zhuǎn)為紅黑樹(shù)時(shí)數(shù)組容量必須大于64 static final int MIN_TREEIFY_CAPACITY = 64; // transient Node<K,V>[] table; transient Set<Map.Entry<K,V>> entrySet; transient int size; //用于快速失敗機(jī)制 在對(duì)HashMap進(jìn)行迭代時(shí)，如果期間其他線程的參與導(dǎo)致HashMap的結(jié)構(gòu)發(fā)生變化了（比如put，remove等操作），直接拋出ConcurrentModificationException異常 transient int modCount; //擴(kuò)容閾值，計(jì)算方法為數(shù)組容量*填充因子 int threshold; //加載因子 填充因子 final float loadFactor;
loadFactor決定數(shù)組何時(shí)進(jìn)行擴(kuò)容，而且為什么是0.75f
它也叫擴(kuò)容因子 比如數(shù)組長(zhǎng)度為32，所以數(shù)組擴(kuò)容閾值為32*0.75=24當(dāng)數(shù)組中數(shù)據(jù)個(gè)數(shù)為24時(shí)數(shù)組進(jìn)行擴(kuò)容，
數(shù)組容量在創(chuàng)建的時(shí)候就確定，擴(kuò)容時(shí)重新創(chuàng)建一個(gè)指定容量的數(shù)組，然后講舊數(shù)組的值復(fù)制到新數(shù)組中，擴(kuò)容過(guò)程非常耗時(shí)，所以0.75時(shí)基于容量和性能之間平衡的結(jié)果。
- 如果加載因子過(guò)大，也就是擴(kuò)容閾值會(huì)變大，擴(kuò)容門(mén)檻高，這樣容量的占用率就會(huì)降低，但哈希碰撞的幾率就會(huì)增加，效率下降
- 如果加載因子過(guò)小，擴(kuò)容閾值變小，擴(kuò)容門(mén)檻低，容量占用變大但哈希碰撞幾率下降
此外用于存儲(chǔ)數(shù)據(jù)的table字段使用transient修飾，通過(guò)transient修飾的字段在序列化的時(shí)候?qū)⒈慌懦谕?，那么HashMap在序列化后進(jìn)行反序列化時(shí)，是如何恢復(fù)數(shù)據(jù)的呢？HashMap通過(guò)自定義的readObject/writeObject方法自定義序列化和反序列化操作。這樣做主要是出于以下兩點(diǎn)考慮：
1.table一般不會(huì)存滿，即容量大于實(shí)際鍵值對(duì)個(gè)數(shù)，序列化table未使用的部分不僅浪費(fèi)時(shí)間也浪費(fèi)空間；
2.key對(duì)應(yīng)的類型如果沒(méi)有重寫(xiě)hashCode方法，那么它將調(diào)用Object的hashCode方法，該方法為native方法，在不同JVM下實(shí)現(xiàn)可能不同；換句話說(shuō)，同一個(gè)鍵值對(duì)在不同的JVM環(huán)境下，在table中存儲(chǔ)的位置可能不同，那么在反序列化table操作時(shí)可能會(huì)出錯(cuò)。
所以在HashXXX類中（如HashTable，HashSet，LinkedHashMap等等），我們可以看到，這些類用于存儲(chǔ)數(shù)據(jù)的字段都用transient修飾，并且都自定義了readObject/writeObject方法。readObject/writeObject方法
2.3 節(jié)點(diǎn)類型Node內(nèi)部類
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;
}
}
Node包含四個(gè)字段
final int hash;
final K key;
V value;
Node<K,V> next;//包含鏈表下一個(gè)節(jié)點(diǎn)
HashMap通過(guò)hash方法計(jì)算key的哈希值，然后通過(guò)（n-1）&hash得到key在數(shù)組中存放的下標(biāo)，當(dāng)兩個(gè)key相同時(shí)，會(huì)以鏈地址法處理哈希碰撞
在鏈表中查找數(shù)據(jù)必須從第一個(gè)元素開(kāi)始，時(shí)間復(fù)雜度為O n 所以當(dāng)鏈表長(zhǎng)度越來(lái)越長(zhǎng)時(shí)HashMap的查詢效率就會(huì)越來(lái)越低
所以為了解決這個(gè)問(wèn)題JDK1.8實(shí)現(xiàn)了數(shù)組+鏈表+紅黑樹(shù)來(lái)解決 當(dāng)鏈表長(zhǎng)度超過(guò)8個(gè)時(shí)并且數(shù)組長(zhǎng)度大于64時(shí)進(jìn)行樹(shù)化，轉(zhuǎn)化后查詢時(shí)間復(fù)雜度為O(logN).
2.4 紅黑樹(shù)的節(jié)點(diǎn)
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);
}
包含左右孩子節(jié)點(diǎn)和雙親結(jié)點(diǎn)，和前驅(qū)節(jié)點(diǎn)，還有節(jié)點(diǎn)是否時(shí)紅或者黑
三、構(gòu)造方法
3.1 構(gòu)造器1
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
最常用的構(gòu)造器。默認(rèn)的填充因子 0.75f 這里的填充因子后面會(huì)講到。
3.2 構(gòu)造器2
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
給定容量構(gòu)造器
3.3 構(gòu)造器3
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)// 如果小于0，拋出異常
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)//大于最大值
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))//若填充因子小于0或者判斷非法
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
static final int tableSizeFor(int cap) {
int n = cap - 1; 讓cap-1再賦值給n的目的是另找到的目標(biāo)值大于或等于原值
n |= 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;
}
給定容量和填充因子。
這里的tableSizeFor會(huì)將傳進(jìn)的容量值進(jìn)行**大于等于最近**二次冪處理。跟循環(huán)數(shù)組的處理方式差不多
3.4 構(gòu)造器4
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
四、put
public V put(K key, V value) {
//底層是調(diào)用putval
return putVal(hash(key), key, value, false, true);
}
//這里調(diào)用了hashmap提供的hash方法，32為都參與了運(yùn)算所以降低了hash碰撞的幾率，這里還跟數(shù)組容量有關(guān)
//下面再討論
static final int hash(Object key) {
int h;
//這里就可以看到hashmap
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
通過(guò)hash函數(shù)可以看到當(dāng)key為null時(shí)，key為0，所以HashMap 是允許儲(chǔ)存空值的。而后面的公式通過(guò)hashcode的高16位異或低1位得到的hash值，主要從性能、哈希碰撞角度考慮，減少系統(tǒng)開(kāi)銷，不會(huì)因?yàn)楦呶粵](méi)有參與下標(biāo)計(jì)算而引起的碰撞
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//請(qǐng)注意這里的hash是已經(jīng)算過(guò)的hash(key)，然后計(jì)算數(shù)組下標(biāo)位置(n - 1) & hash
Node<K,V>[] tab; Node<K,V> p; int n, i;
//首先判斷數(shù)組哈希表是否為null或者長(zhǎng)度為0，是則進(jìn)行數(shù)組初始化操作
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//這里tab指向table數(shù)組 n是數(shù)組長(zhǎng)度
//如果該數(shù)組下標(biāo)位置沒(méi)有數(shù)據(jù)直接插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//該位置有元素
Node<K,V> e; K k;
//首先判斷此位置的值的hash和key的地址和值是否相等
//如果相等直接覆蓋
//小問(wèn)題這里為什么先判斷hash值而不是判斷key值，因?yàn)閔ash值判斷最快，如果hash值不同就不用判斷下面的
//hash不同則key一定不同，但key相同hash值是可能相同的，效率提高
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//否則就是該位置可以不存在，如果該節(jié)點(diǎn)是紅黑樹(shù)類型，
else if (p instanceof TreeNode)
//則按照紅黑樹(shù)的插入
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
//否則就為鏈表結(jié)構(gòu)，遍歷鏈表，尾插
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//如果鏈表長(zhǎng)度大于等于轉(zhuǎn)為紅黑樹(shù)閾值8，則轉(zhuǎn)為紅黑樹(shù)
//這里為什么要-1，因?yàn)閿?shù)組下標(biāo)從0開(kāi)始
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉(zhuǎn)為紅黑樹(shù)操作時(shí)，內(nèi)部還會(huì)判斷數(shù)組長(zhǎng)度是否小于MIN_TREEIFY_CAPACITY 64，如果是的話不轉(zhuǎn)換
treeifyBin(tab, hash);
break;//退出
}
//如果鏈表中已經(jīng)存在該key，直接覆蓋
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//遍歷數(shù)組 e = p.next
p = e;
}
}
//e代表被覆蓋的值
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// 如果onlyIfAbsent為false并且oldValue為null,我們便對(duì)我們的value進(jìn)行保存
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
//如果鍵值對(duì)個(gè)數(shù)大于擴(kuò)容閾值，進(jìn)行擴(kuò)容操作
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
流程圖
![[外鏈圖片轉(zhuǎn)存失敗,源站可能有防盜鏈機(jī)制,建議將圖片保存下來(lái)直接上傳(img-HHFhKMDq-1618929232359)(C:\Users\lenovo\AppData\Roaming\Typora\typora-user-images\image-20210420203344879.png)]](http://img.jbzj.com/file_images/article/202104/2021042214044061.png)
五、get
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;
//如果桶為空，size為0，目標(biāo)位置是否為空，是直接返回null
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//如果數(shù)組該下標(biāo)位置就是要找的值，直接返回
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
//否則如果頭節(jié)點(diǎn)的next有值
if ((e = first.next) != null) {
//如果該類型為紅黑樹(shù)，從紅黑樹(shù)中找
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;
}
六、resize
數(shù)組的擴(kuò)容和初始化都要靠resize完成
final Node<K,V>[] resize() {
//擴(kuò)容前數(shù)組
Node<K,V>[] oldTab = table;
//擴(kuò)容前數(shù)組大小
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//擴(kuò)容前擴(kuò)容閾值
int oldThr = threshold;
//定義新數(shù)組和新閾值
int newCap, newThr = 0;
//如果擴(kuò)容前數(shù)組
if (oldCap > 0) {
//如果超過(guò)最大值就不用再擴(kuò)容
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//2倍擴(kuò)容不能大于最大值
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//擴(kuò)容閾值/2
newThr = oldThr << 1; // double threshold
}
//數(shù)組中沒(méi)有值，帶參初始化會(huì)進(jìn)入這里
//且擴(kuò)容因子大于0
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//不帶參默認(rèn)會(huì)到這里
else {//否則擴(kuò)充因子 <= 0
//就是沒(méi)初始化過(guò)，使用默認(rèn)的初始化容量，16 * 0.75
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新容量為0，重新計(jì)算threshold擴(kuò)容閾值
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"})
//定義新數(shù)組進(jìn)行擴(kuò)容
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
//這里采用高低映射的方式進(jìn)行對(duì)新數(shù)組的映射
if (oldTab != null) {
//遍歷舊數(shù)組復(fù)制到新數(shù)組中
//遍歷
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果當(dāng)前節(jié)點(diǎn)鏈表數(shù)據(jù)只有一個(gè)，則直接賦值
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
//否則紅黑樹(shù)操作
((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;
//判斷原索引和擴(kuò)容后索引是否相同
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);
//如果低位映射不為空，斷低位尾部后的數(shù)據(jù)，因?yàn)槲舶秃罂赡苓€會(huì)有數(shù)據(jù)，因?yàn)槭莻€(gè)鏈表，所以采用頭尾引用來(lái)記錄有效值
//付給新數(shù)組
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//高位引用 直接講原索引+oldCap放到哈希桶中
//因?yàn)槭?倍擴(kuò)容， 擴(kuò)容后位置是原位置+增長(zhǎng)的長(zhǎng)度
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
七、基于JDK1.7的優(yōu)化
7.1 底層實(shí)現(xiàn)
1.7基于數(shù)組+鏈表 而1.8基于鏈表+數(shù)組+紅黑樹(shù)
7.2 hash
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 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);
}
效率基于1.8低
7.3 put
1.7使用的是數(shù)組加鏈表，解決哈希沖突采用的是鏈表，而且1.8采用的是尾插，而1.7采用頭插
7.4 擴(kuò)容
1.7在擴(kuò)容時(shí)會(huì)重新計(jì)算h每個(gè)元素的hash值，按舊鏈表的正序遍歷鏈表，然后在新鏈表的頭部插入，所以會(huì)出現(xiàn)逆序的情況，而1.8是通過(guò)高低位映射，不會(huì)出現(xiàn)逆序。
到此這篇關(guān)于Java源碼解析之HashMap的put、resize方法詳解的文章就介紹到這了,更多相關(guān)HashMap的put、resize方法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了java實(shí)現(xiàn)計(jì)算器模板及源碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-06-06
java實(shí)現(xiàn) 微博登錄、微信登錄、qq登錄實(shí)現(xiàn)代碼
這篇文章主要介紹了java實(shí)現(xiàn) 微博登錄、微信登錄、qq登錄實(shí)現(xiàn)代碼的相關(guān)資料,需要的朋友可以參考下2016-10-10
這篇文章主要介紹了maven工程中jar包瘦身的五種方法，幫助大家更好的理解和使用maven，感興趣的朋友可以了解下2021-02-02
這篇文章主要為大家介紹了Java9新特性Module模塊化編程的示例演繹，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步早日升職加薪2022-03-03
jstack報(bào)錯(cuò)Unable to open socket file解決
這篇文章主要為大家介紹了jstack報(bào)錯(cuò)Unable to open socket file的解決方法詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2024-02-02
這篇文章主要介紹了java compareTo和compare方法比較詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-09-09
OpenCV Java實(shí)現(xiàn)人臉識(shí)別和裁剪功能
這篇文章主要為大家詳細(xì)介紹了OpenCV Java實(shí)現(xiàn)人臉識(shí)別和裁剪功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-05-05
這篇文章主要為大家詳細(xì)介紹了java編寫(xiě)簡(jiǎn)易貪吃蛇游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-05-05
這篇文章主要介紹了SpringBoot如何正確解析日期格式,文中給出了兩種解決方案,通過(guò)代碼示例講解的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作有一定的幫助,需要的朋友可以參考下2024-03-03
SpringBoot異步使用@Async的原理以及線程池配置詳解
在項(xiàng)目中當(dāng)訪問(wèn)其他人的接口較慢時(shí),不想程序一直卡在耗時(shí)任務(wù)上,想程序能夠并行執(zhí)行,我們可以使用多線程來(lái)并行的處理任務(wù),也可以使用spring提供的異步處理方式@Async,這篇文章主要給大家介紹了關(guān)于SpringBoot異步使用@Async的原理以及線程池配置的相關(guān)資料2021-09-09