Java HashMap源碼深入分析講解
1.HashMap是數(shù)組+鏈表（紅黑樹）的數(shù)據(jù)結(jié)構(gòu)。
數(shù)組用來存放HashMap的Key，鏈表、紅黑樹用來存放HashMap的value。
2.HashMap大小的確定：
1） HashMap的初始大小是16，在下面的源碼分析中會看到。
2）如果創(chuàng)建時給定大小，HashMap會通過計(jì)算得到1、2、4、8、16、32、64....這樣的二進(jìn)制位作為HashMap數(shù)組的大小。
//如何做到的呢？通過右移和或運(yùn)算，最終n = xxx11111。n+1 = xx100000，2的n次方，即為數(shù)組大小
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 + 1;
}3.如何將key映射成數(shù)組角標(biāo)：
我們都知道數(shù)組的下標(biāo)是0,1,2,3,4,5,6.....這樣的連續(xù)整數(shù)，那么、HashMap是怎么將Key轉(zhuǎn)換成對應(yīng)的數(shù)組角標(biāo)的呢？
//1. int h = key.hashCode 得到key的hashCode.
//2. int j = h>>>16 右移16位
//3. int hash = h^j 異或，將hashCode變?yōu)閔ash值。
//通過hash算法將hashCode轉(zhuǎn)換為hash值，注意hash值和hashCode不是一回事。
//4.int index = (n - 1) & hash，n是數(shù)組的長度，計(jì)算得到的index即為數(shù)組的角標(biāo)。
//有興趣的朋友，可以寫幾行代碼進(jìn)行驗(yàn)證。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
static final int index(int hash,int n){
return (n - 1) & hash;
}4.Value值如何存儲？
HashMap將key的hashCode轉(zhuǎn)換為數(shù)組角標(biāo)，必然會存在多個元素的key轉(zhuǎn)換成同一個角標(biāo)的情況。針對這樣的情況，HashMap采用鏈表和紅黑數(shù)的方式存儲Value值。java8以后默認(rèn)先以單鏈表的方式存儲。當(dāng)單鏈表中的元素超過8個后，單鏈表會轉(zhuǎn)換成紅黑樹數(shù)據(jù)結(jié)構(gòu)。當(dāng)紅黑樹上的節(jié)點(diǎn)數(shù)量少于6個會重新變?yōu)閱捂湵斫Y(jié)構(gòu)。
5.put實(shí)現(xiàn)原理：
1）通過算法，計(jì)算出key對應(yīng)的數(shù)組角標(biāo)。
2）取出數(shù)組角標(biāo)存儲的節(jié)點(diǎn)，如果為null直接存儲，如果不為null，則對鏈表進(jìn)行遍歷，先比較兩個元素的hash值，再判斷key的equale，如果一樣，說明key已經(jīng)存在，則不存儲，這也就是hashmapKey不能重復(fù)的原因。如果不一樣，則以鏈表或紅黑樹的方式存儲。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果數(shù)組是null 或者長度為0，則創(chuàng)建數(shù)組 resize()
if ((tab = table) == null || (n = tab.length) == 0)
//resize既是創(chuàng)建，也是擴(kuò)容
n = (tab = resize()).length;
//取出索引為i的Node賦值給p，如果為null，說明這個位置沒有節(jié)點(diǎn)
if ((p = tab[i = (n - 1) & hash]) == null)
//創(chuàng)建Node，并放在角標(biāo)為i的位置。這個node是一個單鏈表結(jié)構(gòu)
tab[i] = newNode(hash, key, value, null);
else {//如果i的位置有節(jié)點(diǎn)，則添加到鏈表中
Node<K,V> e; K k;
//先判斷hash是否一致，再判斷key，如果一樣，則說明是同一個Key，
//直接將p賦值給e，這也就是hashMap和HashSet的key不能重復(fù)的原因
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 {
//創(chuàng)建新的node添加的鏈表的末尾
for (int binCount = 0; ; ++binCount) {
//將下一個節(jié)點(diǎn)賦值給e。如果e==null，說明遍歷到最后一個節(jié)點(diǎn)，
if ((e = p.next) == null) {
//創(chuàng)建新的節(jié)點(diǎn)，添加到鏈表末尾
p.next = newNode(hash, key, value, null);
//static final int TREEIFY_THRESHOLD = 8;
//當(dāng)鏈表長度大于等于8時，
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);//轉(zhuǎn)換成紅黑樹
break;
}
//去重
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
//將當(dāng)前的e賦值給p
p = e;
}
}
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) //添加元素個數(shù)大于數(shù)組長度時，進(jìn)行擴(kuò)容
resize();
afterNodeInsertion(evict);
return null;
}6.get方法，HashMap如何取出元素。
取數(shù)據(jù)時，如何判斷傳入的key和map中的key是同一個key呢？
e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))
通過源碼可以看到，必須滿足兩個條件，hash值必須相等，然后再判斷，key的引用是否一致，或者key的equals是否是true。這也就是為啥要同時復(fù)寫對象的hashCode和equals方法的原因。
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;
// 數(shù)組不為空且長度大于0，對應(yīng)角標(biāo)的第一個node，first
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
if (first.hash == hash && //如果和第一個是同一個直接返回
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {//和鏈表第一個節(jié)點(diǎn)不一致，則進(jìn)行遍歷
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);//遍歷鏈表取出和key一致的node
}
}
return null;
}7.HashMap的擴(kuò)容
擴(kuò)容因子： static final float DEFAULT_LOAD_FACTOR = 0.75f;
默認(rèn)大?。?code>static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
擴(kuò)容閾值：int threshold;
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) {//數(shù)組長度大于0
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY){
newThr = oldThr << 1; // 數(shù)組大于默認(rèn)大小時， 擴(kuò)容閾值是原來的2倍
}
} else if (oldThr > 0) //初始化時，threshold已被設(shè)置（調(diào)用有參構(gòu)造函數(shù)時）
newCap = oldThr; //將數(shù)組長度設(shè)置為threshold值。
else { //如果數(shù)組和閾值都為0 (調(diào)用無參構(gòu)造函數(shù))
newCap = DEFAULT_INITIAL_CAPACITY; //默認(rèn)數(shù)組大小，
//擴(kuò)容閾值為默認(rèn)數(shù)組大小的0.75倍
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {//遍歷數(shù)組
Node<K,V> e;
if ((e = oldTab[j]) != null) {//取出數(shù)組元素，也就是鏈表的第一個節(jié)點(diǎn)
oldTab[j] = null;
if (e.next == null)//鏈表只有首個節(jié)點(diǎn)
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);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
}到此這篇關(guān)于Java HashMap源碼深入分析講解的文章就介紹到這了,更多相關(guān)Java HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要為大家介紹了java OpenTelemetry日志體系及缺陷解決方案詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-01-01
spring-boot實(shí)現(xiàn)增加自定義filter（新）
本篇文章主要介紹了spring-boot實(shí)現(xiàn)增加自定義filter（新），小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
Java Comparable及Comparator接口區(qū)別詳解
這篇文章主要介紹了Java Comparable及Comparator接口區(qū)別詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了Spring Bean 依賴注入常見錯誤問題，文中提到value的工作大體分為三個核心步驟，具體內(nèi)容詳情跟隨小編一起看看吧2021-09-09
下面小編就為大家?guī)硪黄胬斫釰ava類和對象。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2021-09-09
這篇文章主要介紹了springBoot 與neo4j的簡單整合示例，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-01-01
Spring事務(wù)管理只對出現(xiàn)運(yùn)行期異常進(jìn)行回滾
Spring的事務(wù)管理默認(rèn)只對出現(xiàn)運(yùn)行期異常(java.lang.RuntimeException及其子類)進(jìn)行回滾,需要了解更多Spring事務(wù)方面的知識，可詳看本文2012-11-11
這篇文章主要介紹了Spring中@Configuration注解的使用場景,@Configuration注解是從Spring?3.0版本開始加入的一個使Spring能夠支持注解驅(qū)動開發(fā)的標(biāo)注型注解,主要用于標(biāo)注在類上,需要的朋友可以參考下2023-11-11
這篇文章主要介紹了Mybatis-plus4條件構(gòu)造器使用方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-02-02
Java結(jié)構(gòu)型設(shè)計(jì)模式中的適配器模式與橋接模式解析
這篇文章主要介紹了Java結(jié)構(gòu)型設(shè)計(jì)模式中的適配器模式與橋接模式,結(jié)構(gòu)型設(shè)計(jì)模式是從程序的結(jié)構(gòu)上解決模塊之間的耦合問題,需要的朋友可以參考下2016-02-02