Java中的HashMap源碼解析
更新時間：2023年12月19日 10:35:32 作者：會飛的豬zhu
這篇文章主要介紹了Java中的HashMap源碼解析,當HashMap中的其中一個鏈表的對象個數(shù)如果達到了8個,此時如果數(shù)組長度沒有達到64,那么HashMap會先擴容解決,如果已經(jīng)達到了64,那么這個鏈表會變成紅黑樹,需要的朋友可以參考下
HashMap
靜態(tài)常量
//序列化版本號，在序列化和反序列化的時候使用
private static final long serialVersionUID = 362498820763181265L;
//集合初始容量為16，
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容量 table數(shù)組存放元素的最大數(shù)量
static final int MAXIMUM_CAPACITY = 1 << 30;
//負載因子默認為0.75 負載因子= 表中的元素個數(shù)/散列表的長度，達到0.75擴容
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//鏈表轉成樹的閾值，鏈表中的元素個數(shù)大于8，變?yōu)榧t黑樹和MIN_TREEIFY_CAPACITY一起決定的
static final int TREEIFY_THRESHOLD = 8;
//樹轉換成鏈表的閾值 樹中的元素小于6，轉換為鏈表
static final int UNTREEIFY_THRESHOLD = 6;
//最小轉成樹的容量，當數(shù)組長度達到64轉換為紅黑樹----和TREEIFY_THRESHOLD一起決定的
static final int MIN_TREEIFY_CAPACITY = 64;成員變量
//存放元素的數(shù)組
transient Node<K,V>[] table;
//存放Entry類型的元素集合
transient Set<Map.Entry<K,V>> entrySet;
//哈希表中元素的個數(shù)
transient int size;
//每次擴容和更改map結構的計數(shù)器
transient int modCount;
//擴容的閾值，當實際大小為(16 * 0.75 = 12) 閾值時開始擴容
int threshold;
//哈希表自己的負載因子
final float loadFactor;構造函數(shù)
//指定容量大小的構造函數(shù)
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/*
指定“容量大小”和“加載因子”的構造函數(shù)
initialCapacity: 指定的容量
loadFactor:指定的加載因子
*/
public HashMap(int initialCapacity, float loadFactor) {
//判斷初始化容量initialCapacity是否小于0
if (initialCapacity < 0)
//如果小于0，則拋出非法的參數(shù)異常IllegalArgumentException
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
//判斷初始化容量initialCapacity是否大于集合的最大容量MAXIMUM_CAPACITY-》2的30次冪
if (initialCapacity > MAXIMUM_CAPACITY)
//如果超過MAXIMUM_CAPACITY，會將MAXIMUM_CAPACITY賦值給initialCapacity
initialCapacity = MAXIMUM_CAPACITY;
//判斷負載因子loadFactor是否小于等于0或者是否是一個非數(shù)值
if (loadFactor <= 0 || Float.isNaN(loadFactor))
//如果滿足上述其中之一，則拋出非法的參數(shù)異常IllegalArgumentException
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
//將指定的加載因子賦值給HashMap成員變量的負載因子loadFactor
this.loadFactor = loadFactor;
/*
tableSizeFor(initialCapacity) 判斷指定的初始化容量是否是2的n次冪，如果不是那么會變?yōu)楸戎付ǔ跏蓟萘看蟮淖钚〉?的n次冪。
但是注意，在tableSizeFor方法體內(nèi)部將計算后的數(shù)據(jù)返回給調用這里了，并且直接賦值給threshold邊界值了。有些人會覺得這里是一個bug,應該這樣書寫：
this.threshold = tableSizeFor(initialCapacity) *this.loadFactor;
這樣才符合threshold的意思（當HashMap的size到達threshold這個閾值時會擴容）。
但是，請注意，在jdk8以后的構造方法中，并沒有對table這個成員變量進行初始化，table的初始化被推遲到了put方法中，在put方法中會對threshold重新計算
*/
this.threshold = tableSizeFor(initialCapacity);
}
//無參構造
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}//返回比指定初始容量大的最小的2的n次方
static final int tableSizeFor(int cap) {
int n = cap - 1;
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;
}put()方法流程
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
//transient Node<K,V>[] table; 表示存儲Map集合中元素的數(shù)組。
Node<K,V>[] tab;
Node<K,V> p;
//n代表數(shù)組的長度
int n, i;
// ① 將table賦值給tab,并判斷是否為null，第一次賦值時肯定為null
// ② 將tab.length賦值給n，并判斷是否為0
if ((tab = table) == null || (n = tab.length) == 0)
//③ 由于數(shù)組為tab==null，對數(shù)組進行初始化，并將初始化后的數(shù)組長度賦值給n
//④ 執(zhí)行n = (tab = resize()).length，數(shù)組tab每個空間都是null
n = (tab = resize()).length;
// ① i = (n - 1) & hash 表示計算數(shù)組的索引賦值給i，即確定元素存放在哪個桶中
// ② p = tab[i = (n - 1) & hash] 將計算出的數(shù)組索引對應的數(shù)據(jù)賦值給節(jié)點p
// ③ 判斷p是否為null，即當前桶沒有哈希沖突，則直接把鍵值對插入空間位置
if ((p = tab[i = (n - 1) & hash]) == null)
// ④ 根據(jù)鍵值對創(chuàng)建新的節(jié)點放入該位置的桶中
// p表示tab[i]，即 newNode(hash, key, value, null)方法返回的Node對象。
tab[i] = newNode(hash, key, value, null);
else {
// ① 執(zhí)行else說明p=tab[i]不等于null，表示這個位置已經(jīng)有值了，
Node<K,V> e; K k;
// ② p.hash == hash：比較桶中元素的hash值和新添加元素key的hash值是否相等
// ③ (k = p.key) == key：比較兩個key的地址值是否相等
// ④ (key != null && key.equals(k))：能夠執(zhí)行到這里說明兩個key的地址值不相等，
//那么先判斷后添加的key是否等于null，如果不等于null再調用equals方法判斷兩個key的內(nèi)容是否相等
if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))
// 兩個元素哈希值相等，并且key的值也相等，將舊的元素整體對象賦值給e，用e來記錄
e = p;
// hash值不相等或者key不相等；判斷p是否為紅黑樹結點
else if (p instanceof TreeNode)
// 放入樹中
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// hash值不相等或者key不相等，說明是鏈表節(jié)點
else {
// 如果hash(key)不相同，說明是計算的桶下標相同，key也不相同，說明直接插在鏈表最后
for (int binCount = 0; ; ++binCount) {
// ① e = p.next 獲取p的下一個元素賦值給e
// ② 判斷p.next是否等于null，等于null，說明p沒有下一個元素
// ③ 到達了鏈表的尾部，還沒有找到重復的key,說明HashMap沒有包含該鍵，將該鍵值對插入鏈表中
if ((e = p.next) == null) {
//④ 創(chuàng)建一個新的節(jié)點插入到尾部
p.next = newNode(hash, key, value, null);
//① 節(jié)點添加完成之后判斷此時節(jié)點個數(shù)是否大于臨界值8，如果大于則將鏈表轉換為紅黑樹
//② binCount從0開始計數(shù)，TREEIFY_THRESHOLD - 1=7
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//轉換為紅黑樹
treeifyBin(tab, hash);
break;
}
// ① e = p.next 不是null，不是最后一個元素。
// ②繼續(xù)判斷鏈表中結點的key值與插入的元素的key值是否相等
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
// 相等，跳出循環(huán)
//要添加的元素和鏈表中的存在的元素的key相等了，則跳出for循環(huán)。
//不用再繼續(xù)比較了，直接執(zhí)行下面的if語句去替換去 if (e != null)
break;
//說明新添加的元素和當前節(jié)點不相等，繼續(xù)查找下一個節(jié)點。
// 用于遍歷桶中的鏈表，與前面的e = p.next組合，可以遍歷鏈表
p = e;
}
}
/*
表示在桶中找到key值、hash值與插入元素相等的結點
也就是說通過上面的操作找到了重復的鍵，所以這里就是把該鍵的值變?yōu)樾碌闹?，并返回舊值
這里完成了put方法的修改功能
*/
if (e != null) {
// 記錄e的value
V oldValue = e.value;
// onlyIfAbsent為false或者舊值為null
if (!onlyIfAbsent || oldValue == null)
//用新值替換舊值:e.value 表示舊值 value表示新值
e.value = value;
// 訪問后回調
afterNodeAccess(e);
// 返回舊值
return oldValue;
}
}
//修改記錄次數(shù)
++modCount;
// 判斷實際大小是否大于threshold閾值，如果超過則擴容
if (++size > threshold)
resize();
// 插入后回調
afterNodeInsertion(evict);
return null;
} hash()方法實現(xiàn)
① 計算hash(key)
對于key的hashCode做hash操作，無符號右移16位后做異或運算。 還有偽隨機數(shù)法和取余數(shù)法。這2種效率都比較低。而無符號右移16位和異或運算效率是最高的。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}② 計算數(shù)組桶下標： hash(key) & (table.length-1)
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {
// n表示數(shù)組初始化的長度是16
// 數(shù)組的長度必須為2的n次方，這樣能夠讓hash(key)更加均勻的分布在桶下標中，減少hash沖突
// 使用 & 運算是為了提高效率
if ((p = tab[i = (n - 1) & hash]) == null)
}具體流程：
resize方法的實現(xiàn)
當HashMap中的元素個數(shù)超過數(shù)組大小 *loadFactor時，就會進行數(shù)組擴容，loadFactor的默認值是0.75,這是一個折中的取值。也就是說，默認情況下，數(shù)組大小為16，那么當HashMap中的元素個數(shù)超過16×0.75=12(這個值就是閾值或者邊界值threshold值)的時候，就把數(shù)組的大小擴展為2×16=32，即擴大一倍，然后重新計算每個元素在數(shù)組中的位置，而這是一個非常耗性能的操作，所以如果我們已經(jīng)預知HashMap中元素的個數(shù)，那么預知元素的個數(shù)能夠有效的提高HashMap的性能。
當HashMap中的其中一個鏈表的對象個數(shù)如果達到了8個，此時如果數(shù)組長度沒有達到64，那么HashMap會先擴容解決，如果已經(jīng)達到了64，那么這個鏈表會變成紅黑樹，節(jié)點類型由Node變成TreeNode類型。當然，如果映射關系被移除后，下次執(zhí)行resize方法時判斷樹的節(jié)點個數(shù)低于6，也會再把樹轉換為鏈表。
進行擴容，會伴隨著一次重新hash分配，并且會遍歷hash表中所有的元素，是非常耗時的。在編寫程序中，要盡量避免resize。
HashMap在進行擴容時，使用的rehash方式非常巧妙，因為每次擴容都是翻倍，與原來計算的 (n-1)&hash的結果相比，只是多了一個bit位，所以節(jié)點要么就在原來的位置，要么就被分配到"原位置+舊容量"這個位置。
怎么理解呢？例如我們從16擴展為32時，具體的變化如下所示：
元素在重新計算hash之后，因為n變?yōu)?倍，那么n-1的標記范圍在高位多1bit(紅色)，因此新的index就會發(fā)生這樣的變化：
說明：5是假設計算出來的原來的索引。這樣就驗證了上述所描述的：擴容之后所以節(jié)點要么就在原來的位置，要么就被分配到"原位置+舊容量"這個位置。如果新的索引高位為0那么存儲在原來索引位置，如果高位是1那么存在原來索引+舊的數(shù)組長度位置。
因此，我們在擴充HashMap的時候，不需要重新計算hash，只需要看看原來的hash值新增的那個bit是1還是0就可以了，是0的話索引沒變，是1的話索引變成“原索引+oldCap(原位置+舊容量)”?？梢钥纯聪聢D為16擴充為32的resize示意圖：
正是因為這樣巧妙的rehash方式，既省去了重新計算hash值的時間，而且同時，由于新增的1bit是0還是1可以認為是隨機的，在resize的過程中保證了rehash之后每個桶上的節(jié)點數(shù)一定小于等于原來桶上的節(jié)點數(shù)，保證了rehash之后不會出現(xiàn)更嚴重的hash沖突，均勻的把之前的沖突的節(jié)點分散到新的桶中了。
final Node<K,V>[] resize() {
//得到當前數(shù)組
Node<K,V>[] oldTab = table;
//如果當前數(shù)組等于null長度返回0，否則返回當前數(shù)組的長度
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//舊閾值點 默認是12(16*0.75)
int oldThr = threshold;
int newCap, newThr = 0;
//第一次的數(shù)組容量都是0肯定
// ① 數(shù)組容量>0
if (oldCap > 0) {
// ① 超過最大值就不再擴充了，就只好隨你碰撞去吧
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// ② 沒超過最大值，數(shù)組容量就擴充為原來的2倍，newCap = 16*2=32
else if((newCap = oldCap << 1)< MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY)
//閾值擴大一倍， 默認原來是12 乘以2之后變?yōu)?4
newThr = oldThr << 1;
}
//② 舊閾值點大于0 直接賦值
else if (oldThr > 0)
newCap = oldThr;
//③ 直接使用默認值
else {
newCap = DEFAULT_INITIAL_CAPACITY;//16
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 = 24
threshold = newThr;
// ③ 創(chuàng)建新的哈希表，數(shù)組大小為newCap=32
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// ④ 判斷舊數(shù)組不等于空，遍歷舊的哈希表 ,重新計算桶里元素的新位置,把每個bucket都移動到新的buckets中
if (oldTab != null) {
// 把每個bucket都移動到新的buckets中
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//取出桶中的元素賦值給e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//① 如果沒有下一個節(jié)點，說明不是鏈表，當前桶上只有一個鍵值對，直接插入
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//② 判斷是否是紅黑樹節(jié)點
else if (e instanceof TreeNode)
//說明是紅黑樹來處理沖突的，則調用相關方法把樹分開
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//③ 說明是鏈表節(jié)點
else {
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
//遍歷鏈表計算節(jié)點要插入新數(shù)組的位置
do {
//原索引
next = e.next;
//① e這個節(jié)點在resize之后不需要移動位置
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//② 否則e這個節(jié)點要插入的位置為：原索引+oldCap
else {
if (hiTail == null)
hiHead = e;
else
hiTail.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;
}總結：
1.如果當前數(shù)組的容量大于0并且小于數(shù)組容量的最大值，那么就會將數(shù)組容量擴容為原來的2倍
2. 如果數(shù)組容量為0，但是閾值大于0，那么table會初始化為閾值大小
3. 如果數(shù)組容量為0，且閾值為0，那么table會初始化為默認值16
4. 創(chuàng)建一個新的數(shù)組，數(shù)組的容量為擴容后的數(shù)組大小，然后遍歷原來數(shù)組中的元素：
5.如果數(shù)組桶下標處只有一個鍵值對，將當前位置的元素直接插入到新數(shù)組對應桶下標處
6.如果紅黑樹節(jié)點，拆分紅黑樹解決哈希沖突
7.如果是鏈表節(jié)點，遍歷鏈表，并計算鏈表中每個節(jié)點應該插入到新數(shù)組中的位置
8.如果當前節(jié)點的hash值和原來數(shù)組的容量進行與運算等于0，那么當前元素插入新數(shù)組的該索引處
9.如果當前節(jié)點的hash值和原來數(shù)組的容量進行與運算等于1，那么當前元素插入到新數(shù)組的位置為：當前元素在舊數(shù)組中的索引+舊數(shù)組的長度
treeifyBin()方法實現(xiàn)
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
//① 如果數(shù)組為空，或者數(shù)組的長度小于64，就先擴容，而不是將節(jié)點轉為紅黑樹
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
//② 執(zhí)行到這里說明哈希表中的數(shù)組長度大于閾值64，開始進行樹形化
// 將數(shù)組中的元素取出賦值給e,e是哈希表中指定位置桶里的鏈表節(jié)點，從第一個開始
else if ((e = tab[index = (n - 1) & hash]) != null) {
///hd：紅黑樹的頭結點 tl :紅黑樹的尾結點
TreeNode<K,V> hd = null, tl = null;
do {
//新創(chuàng)建一個樹的節(jié)點，內(nèi)容和當前鏈表節(jié)點e一致
TreeNode<K,V> p = replacementTreeNode(e, null);
//將新創(chuàng)鍵的p節(jié)點賦值給紅黑樹的頭結點
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
//讓桶中的第一個元素即數(shù)組中的元素指向新建的紅黑樹的節(jié)點，以后這個桶里的元素就是紅黑樹,而不是鏈表數(shù)據(jù)結構了
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}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;
if((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {
//判斷數(shù)組中的第一個節(jié)點的hash、key的地址、key的內(nèi)容是否和要查找的key相同，如果相同返回即可
if (first.hash == hash && ((k = first.key) == key || (key != null && key.equals(k))))
return first;
//如果數(shù)組中節(jié)點還指向了下一個節(jié)點
if ((e = first.next) != null) {
//如果是紅黑樹，調用紅黑樹的getTreeNode()方法
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//如果是鏈表，遍歷鏈表，查找與key相同的鍵對應的節(jié)點，找到只有返回當前節(jié)點
do {
if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}到此這篇關于Java中的HashMap源碼解析的文章就介紹到這了,更多相關HashMap源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
java實現(xiàn)日歷(某年的日歷,某月的日歷)用戶完全自定義
本篇文章介紹了，java實現(xiàn)日歷(某年的日歷,某月的日歷)用戶完全自定義。需要的朋友參考下2013-05-05
大家在開發(fā)中經(jīng)常會用到Spring MVC Controller來接收請求參數(shù)，主要常用的接收方式就是通過實體對象以及形參等方式、有些用于GET請求，有些用于POST請求，有些用于兩者，下面介紹幾種常見的Spring MVC傳遞接收參數(shù)的方式2021-11-11
spring boot實戰(zhàn)之本地jar包引用示例
本篇文章主要介紹了spring boot實戰(zhàn)之本地jar包引用示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
IDEA剛接觸不久，各種常用工具窗口找不到，不小心關掉不知道從哪里打開，今天小編給大家分享這個問題的解決方法，感興趣的朋友一起看看吧2021-09-09
基于Java Callable接口實現(xiàn)線程代碼實例
這篇文章主要介紹了基于Java Callable接口實現(xiàn)線程代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-08-08
springboot?實現(xiàn)不同context-path下的會話共享
這篇文章主要介紹了springboot?實現(xiàn)不同context-path下的會話共享，基于很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-01-01
這篇文章主要介紹了Lambda表達式的使用及注意事項，主要圍繞?Lambda表達式的省略模式?Lambda表達式和匿名內(nèi)部類的區(qū)別的相關內(nèi)容展開詳情，感興趣的小伙伴可以參考一下2022-06-06
這篇文章主要介紹了Java線程休眠之sleep方法詳解,Thread?類中有一個靜態(tài)方法的sleep方法,當該線程調用sleep方法后,就會暫時讓CPU的調度權,但是監(jiān)視器資源比如鎖并不會釋放出去,需要的朋友可以參考下2024-01-01
這篇文章主要介紹了Java多線程中Callable和Future的解讀,Callable接口類似于Runnable,從名字就可以看出來了,但是Runnable不會返回結果,并且無法拋出返回結果的異常,而Callable功能更強大一些,被線程執(zhí)行后,可以返回值,這個返回值可以被Future拿到,需要的朋友可以參考下2023-09-09
java多線程編程之InheritableThreadLocal
這篇文章主要為大家詳細介紹了java多線程編程之InheritableThreadLocal，具有一定的參考價值，感興趣的小伙伴們可以參考一下2017-10-10