適合閱讀的人群
文筆不是很好矿咕，如果對于HashMap沒有一個大致的了解共虑，最好不要看
目錄
HashMap的幾個基本概念
HashMap的成員變量
HashMap的構(gòu)造方法
HashMap的幾個基礎(chǔ)方法
HashMap的get()方法
HashMap的put()方法
HashMap的resize()方法
HashMap的remove()方法
HashMap的幾個基本概念
桶(bucked)：存放同一個hash地址的
table[]：即存放桶的數(shù)組
容量(capacity)：即table.length
loadfactor：負(fù)載因子,權(quán)衡hash沖突情況
HashMap的成員變量
首先看HashMap定義的幾個常量
//默認(rèn)容器大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
//最大容器大小
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//需要轉(zhuǎn)換為紅黑樹的鏈表長度閾值
static final int TREEIFY_THRESHOLD = 8;
//轉(zhuǎn)換為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;
//需要轉(zhuǎn)換為紅黑樹的容器容量閾值
static final int MIN_TREEIFY_CAPACITY = 64;
這里需要注意到的幾個細(xì)節(jié):
- TREEIFY_THRESHOLD:jdk1.8以后，如果長度超過這個閾值憎乙，則一個桶內(nèi)的node由鏈表轉(zhuǎn)為紅黑樹
- UNTREEIFY_THRESHOLD:當(dāng)紅黑樹長度小于這個閾值拟杉，就會再退化成鏈表
- 只有capacity>=MIN_TREEIFY_CAPACITY時笑旺，才需要將鏈表轉(zhuǎn)換為紅黑樹，否則只需要resize()
這里第三點(diǎn)補(bǔ)充一下：現(xiàn)在HashMap源碼解讀好唯，關(guān)于鏈表轉(zhuǎn)換為紅黑樹這一塊普遍都有誤導(dǎo)性竭沫，大部分資料都是說當(dāng)鏈表長度到達(dá)8時，桶結(jié)構(gòu)從鏈表轉(zhuǎn)換為紅黑樹骑篙，其實(shí)這是不嚴(yán)謹(jǐn)?shù)耐商幔€需要當(dāng)前容量capacity>=MIN_TREEIFY_CAPACITY(即桶數(shù)量>=64)這個條件,否則進(jìn)行擴(kuò)容而不是轉(zhuǎn)換紅黑樹,關(guān)鍵源碼在下面
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
這是有道理的，讀者也不妨思考一下靶端，如果當(dāng)capacity的容量只有16的時候谎势，hash嚴(yán)重沖突鏈表長度到達(dá)8，除了hash不均勻之外杨名，也有可能是容量太小脏榆，導(dǎo)致沖突嚴(yán)重，這時候?qū)able進(jìn)行擴(kuò)容,再對元素均勻散列才是最有效的辦法台谍。
再提一點(diǎn)须喂，鏈表轉(zhuǎn)為紅黑樹這個事件發(fā)生的概率有多大呢，我們捋一下幾個條件:
- capacity>=MIN_TREEIFY_CAPACITY
- 鏈表長度>=TREEIFY_THRESHOLD
但HashMap還有一個loadfactor參數(shù)趁蕊，就拿默認(rèn)值0.75舉例坞生，假設(shè)桶已經(jīng)有64個了，那么當(dāng)節(jié)點(diǎn)到達(dá)48個的時候就會擴(kuò)容掷伙，平均分的話是己，一個桶還不夠分一個節(jié)點(diǎn)，一旦擴(kuò)容任柜，又重新對半進(jìn)行散列卒废，因此需要滿足全部以上條件的話寒波，那是非常小的小概率事件。
那么這個算法還有意義嗎?
有意義的升熊，除了應(yīng)對這個隨機(jī)發(fā)生的小概率事件俄烁，還需要應(yīng)對人為刻意的制造hash沖突,如果在服務(wù)器環(huán)境中，如果得到你的hash計(jì)算方法级野，那么有可能針對hash方法進(jìn)行hashdos攻擊页屠，web服務(wù)器會有一個HashMap保存提交的參數(shù)，如果不對參數(shù)數(shù)量進(jìn)行限制的話蓖柔，那么一次性提交大量hash沖突的參數(shù)辰企，那么光一次get()方法就能拖垮服務(wù)器的吞吐量,使用紅黑樹，至少能保證了get方法的效率况鸣，但是要解決hashdos還是要以預(yù)防為主牢贸。
繼續(xù)看HashMap的實(shí)例變量
//hash表，每個Node就是一個桶的頭節(jié)點(diǎn)
transient java.util.HashMap.Node<K,V>[] table;
//用來返回迭代器
transient Set<Map.Entry<K,V>> entrySet;
//數(shù)量
transient int size;
//記錄修改次數(shù)
transient int modCount;
//擴(kuò)容的閾值镐捧，等于loadFactor*capacity
int threshold;
//負(fù)載因子
final float loadFactor;
這里需要注意到的細(xì)節(jié):
- modCount有什么作用:是為了HashMap的迭代器能夠記錄map有沒有被修改過潜索，在多線程情況，如果迭代器迭代時發(fā)現(xiàn)modCount變化了懂酱，則說明當(dāng)前這份數(shù)據(jù)已經(jīng)無效了竹习，就會拋出一個ConcurrentModificationException異常
- threshold就是size的一個閾值，當(dāng)size到達(dá)threshold時列牺，就需要擴(kuò)容,threshold等于loadFactor*capacity
- 為什么table都要加上transient不允許序列化?是因?yàn)镠ashCode()的方法是基于平臺的整陌，不同平臺的同一個對象可能會得到不同的HashCode,因此不允許table進(jìn)行序列化
- 沒有capacity變量，capacity=table.length
HashMap的構(gòu)造方法
查看HashMap的源碼瞎领，可以看到HashMap有四種構(gòu)造器
//1.設(shè)定容器大小和負(fù)載因子
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//最大不能超過MAXIMUM_CAPACITY
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
//2.設(shè)定容器大小
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//3.默認(rèn)方法泌辫，使用默認(rèn)參數(shù)
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
}
//4.使用默認(rèn)構(gòu)造器，同時將m填充到這個hashMap
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
這里關(guān)注一下第一個構(gòu)造方法的細(xì)節(jié):
this.threshold = tableSizeFor(initialCapacity);
當(dāng)給定了初始容量參數(shù)之后九默，就會調(diào)用tableSizeFor()方法震放，返回一個大于initialCapacity的最小2的冪次方,以符合HashMap的Capacity必須為2的冪次方的要求(為什么這么要求，后面會提到),這里tableSizeFor()的返回值荤西，即表示最后容器的初始化值澜搅，而這里的threshold就不等于負(fù)載因子*容器，而表示的是初始容量
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;
}
這個是tableSizeFor()方法邪锌，用了一次很巧妙的方法得到cap最小2的冪次方,有興趣的可以看一下這個博客
同時threshold在初始化時等于0或者等于初始化的容量,在第一次resize()的時候才會變成負(fù)載因子*容器
HashMap的幾個基礎(chǔ)方法
hash()方法
是==HashMap==中用來計(jì)算Key的hash值的唯一方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
這里為什么不直接用對象的hashCode,而需要右移十六位進(jìn)行異或勉躺，簡單來說，是讓hashCode高16位和第16位進(jìn)行異或觅丰，增加hashCode的隨機(jī)性饵溅，這里具體不提了，有興趣的可以看HashMap 的 hash 方法原理是什么
同時我們需要注意到妇萄，這里的key是允許為null,當(dāng)key為null時蜕企，默認(rèn)hash值為0咬荷，后面可以看到，即key為null的對象轻掩，都保存到table[0]桶下面
treeifyBin()方法
當(dāng)一個桶中的鏈表長度>TREEIFY_THRESHOLD時要執(zhí)行的方法幸乒，執(zhí)行結(jié)果有兩種
- 將鏈表轉(zhuǎn)換為紅黑樹
- 執(zhí)行一次rezise()
取決于capacity是否>=MIN_TREEIFY_CAPACITY
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab);
}
}
HashMap的get()方法
接下來是HashMap的第一個重點(diǎn)方法，get()方法
在看源碼之前唇牧，我們可以先設(shè)想罕扎，如果我們是編寫代碼的人，我們會怎么寫get()方法:
- 首先獲取到Key的Hash值
- 根據(jù)Hash定位到table的桶位置
- 對桶內(nèi)元素進(jìn)行遍歷丐重，比較對象是否存在
- 如果存在則返回對象
之后我來看get()方法的源碼,可以看到可以訪問的公有的方法.是先對key進(jìn)行hash之后調(diào)用一個getNode()方法,這個方法是包訪問權(quán)限
public V get(Object key) {
java.util.HashMap.Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
繼續(xù)看getNode()方法
final java.util.HashMap.Node<K,V> getNode(int hash, Object key) {
//tab為hash表,first為hash桶的頭指針,n為表的長度,k為用來遍歷鏈表的指針
java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> first, e; int n; K k;
// 第一步：獲取表的長度n,獲取到hash桶的頭指針first
if ((tab = table) != null && (n = tab.length) > 0 &&
//這里用n-1和hash值進(jìn)行hash,之后講解為什么要這樣
(first = tab[(n - 1) & hash]) != null) {
// 第二步：檢查hash桶的頭指針是否和要找的對象key相等
if (first.hash == hash &&
((k = first.key) == key || (key != null && key.equals(k))))
return first;
// 第三步：遍歷桶進(jìn)行查找
if ((e = first.next) != null) {
// 判斷如果是紅黑樹的結(jié)構(gòu)腔召，則用TreeNode的靜態(tài)方法遞歸查找
if (first instanceof java.util.HashMap.TreeNode)
return ((java.util.HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
// 否則使用鏈表進(jìn)行遍歷查找
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
// 如果都沒有找到，則返回null
return null;
}
這里已經(jīng)把各個步驟都詳細(xì)的寫了注釋扮惦，這里有一個細(xì)節(jié)就是桶的下標(biāo)tab[(n - 1) & hash]為什么是通過(n - 1) & hash進(jìn)行定位?
hashmap要求容量是2的冪次方
/**
* The default initial capacity - MUST be a power of two.
*/
而n是hashmap的容量
假設(shè)這里有一個key:使用hash()方法得到的hash值為16位:
1111111111110101
換為十進(jìn)制就是65535
hashmap的n為:
2<<4
換為十進(jìn)制就是16
意味著最大的能定位到的下標(biāo)也只是16-1=15
如果直接用hash值就數(shù)組越界了
因此我們需要對hash對n進(jìn)行取余
n-1 = 15
換位二進(jìn)制就是1111
hash & (n - 1)即:
1111111111110101
& 0000000000001111
= 0000000000000101
最后取到(n-1)位0101
用hash & (n - 1)進(jìn)行取余效率更快臀蛛，同時也解釋了為什么hashmap要求容量是2的冪次方
HashMap的put()方法
在HashMap的put()方法之前，我們也可以先思考put需要考慮什么問題
我們直到hashMap是基于數(shù)組實(shí)現(xiàn)
- 如果hash到同一個位置崖蜜，hash沖突了怎么辦
- 如果hash沖突嚴(yán)重浊仆，在一個桶內(nèi)有上萬個節(jié)點(diǎn)怎么辦
接下來看put方法的源碼
//onlyIfAbsent代表key相同時，是否要替換值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里同樣調(diào)用到一個包訪問方法puVal()
//onlyIfAbsent表示當(dāng)key重復(fù)需不需要用新值替換舊值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab為table,p為臨時指針,n為table的長度,i為hash到的桶
java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, i;
// 如果table沒有初始化纳猪，則用resize()方法初始化,resize()在后面提到
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
//如果hash到的桶不存在氧卧，則作為頭指針插入
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
java.util.HashMap.Node<K,V> e; K k;
//hash到的值相等
if (p.hash == hash &&
//判斷是否是同一個對象桃笙，或者相等(例如String)
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
//如果是樹節(jié)點(diǎn)
else if (p instanceof java.util.HashMap.TreeNode)
//則用樹節(jié)點(diǎn)的putTreeVal方法
e = ((java.util.HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//如果為鏈表結(jié)構(gòu)
else {
//使用尾插法
for (int binCount = 0; ; ++binCount) {
//遍歷到尾部
if ((e = p.next) == null) {
//直接鏈入新節(jié)點(diǎn)
p.next = newNode(hash, key, value, null);
//如果到達(dá)長度限制
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//則轉(zhuǎn)換為紅黑樹或進(jìn)行一次resize();
treeifyBin(tab, hash);
break;
}
//如果查找到相同的值則返回
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果key已經(jīng)存在,則直接返回
if (e != null) { // existing mapping for key
V oldValue = e.value;
//根據(jù)onlyIfAbsent決定是否要替換
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
//返回舊值
return oldValue;
}
}
//如果新插入的Node,就會執(zhí)行一下方法
//更新操作數(shù)
++modCount;
//如果大于闕值threshold氏堤，則需要resize
if (++size > threshold)
resize();
//這時一個回調(diào)方法，當(dāng)插入節(jié)點(diǎn)的時候執(zhí)行這個方法搏明，但是在HashMap里方法是空的鼠锈，留給子類覆寫
afterNodeInsertion(evict);
return null;
}
關(guān)于put()方法，上面也已經(jīng)說的足夠詳細(xì)了,設(shè)計(jì)到一個比較重要的方法resize(),這個在下一節(jié)會繼續(xù)講到
總結(jié)
- 在jdk1.7以前星著，鏈表的插入是使用頭插法购笆，jdk1.8之后是使用的尾插法，這一點(diǎn)不要混淆了
- 允許插入的Key為null,hash的桶下標(biāo)為0
- 允許插入的Value為null
- onlyIfAbsent參數(shù)默認(rèn)為false虚循，因此當(dāng)key重復(fù)時同欠，新value會替換掉舊的value
- 當(dāng)一個桶內(nèi)的元素?cái)?shù)量超過TREEIFY_THRESHOLD,則會將當(dāng)前桶由鏈表轉(zhuǎn)換為紅黑樹
- 當(dāng)當(dāng)前容器中的節(jié)點(diǎn)數(shù)量size到達(dá)threashold(即負(fù)載因子*容量)時，就會進(jìn)行擴(kuò)容
- 每次插入節(jié)點(diǎn)都會更新modCount
HashMap的resize()方法
HashMap的resize()方法主要有兩個作用:
- 初始化容器時横缔，為容器創(chuàng)建一個默認(rèn)的map
- 當(dāng)插入的數(shù)據(jù)到達(dá)閾值時铺遂，進(jìn)行擴(kuò)容
final java.util.HashMap.Node<K,V>[] resize() {
java.util.HashMap.Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//舊的閾值，如果size到達(dá)threshold茎刚，則需要擴(kuò)容
int oldThr = threshold;
int newCap, newThr = 0;
//如果oldCap>0襟锐，則意味著table已經(jīng)初始化過了
if (oldCap > 0) {
//最大不能超過MAXIMUM_CAPACITY,如果到達(dá)MAXIMUM_CAPACITY,threshold不作限制
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//進(jìn)行兩倍擴(kuò)容
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
//如果oldCap==0,oldThr>0意味著table還未初始化，同時是調(diào)用的有初始化容量的構(gòu)造器膛锭，有給定的初始容量
else if (oldThr > 0)
//則新容量=oldThr
newCap = oldThr;
//如果oldCap==0,oldThr==0意味著table還未初始化粮坞，同時調(diào)用的是默認(rèn)的構(gòu)造器
else {
//則新容量為默認(rèn)值
newCap = DEFAULT_INITIAL_CAPACITY;
//newThr等于負(fù)載因子*容量大小
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//對threshold賦值
if (newThr == 0) {
//等于負(fù)載因子*容量大小
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//下面是需要把舊的table的數(shù)據(jù)全部再hash到新的table
@SuppressWarnings({"rawtypes","unchecked"})
java.util.HashMap.Node<K,V>[] newTab = (java.util.HashMap.Node<K,V>[])new java.util.HashMap.Node[newCap];
table = newTab;
if (oldTab != null) {
//對table每個桶進(jìn)行遍歷
for (int j = 0; j < oldCap; ++j) {
java.util.HashMap.Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
//如果是桶的頭指針蚊荣，則直接再hash到新的桶
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
//如果是樹節(jié)點(diǎn)，則進(jìn)行切分,切分成兩棵子樹莫杈，或者退化成兩個鏈表
else if (e instanceof java.util.HashMap.TreeNode)
((java.util.HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果是鏈表互例，則拆分成兩個新鏈表
else {
//分為高位鏈表和低位鏈表
java.util.HashMap.Node<K,V> loHead = null, loTail = null;
java.util.HashMap.Node<K,V> hiHead = null, hiTail = null;
java.util.HashMap.Node<K,V> next;
do {
next = e.next;
//和舊容器長度進(jìn)行hash如果等于0則說明 hash<oldCap,鏈接到低位鏈表
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
//如果>0則說明 hash>oldCap,鏈接到高位鏈表
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
//最后將高位低位鏈表放回到新的table
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
擴(kuò)容總結(jié)為三步驟
- 獲得新容量newCap,更新域里面的threshold
- 創(chuàng)建一個新table,長度為newCap
- 將舊的table里面的Node，拷貝到新容器(桶的Key的hash值不需要重新計(jì)算筝闹，只需要計(jì)算hash在新table的高位還是低位)
HashMap的remove()方法
remove()方法比較簡單
public V remove(Object key) {
java.util.HashMap.Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//matchValue表示只有value相等的時候刪除
final java.util.HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
java.util.HashMap.Node<K,V> node = null, e; K k; V v;
//如果是桶的頭指針
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//判斷是否是紅黑樹
if (p instanceof java.util.HashMap.TreeNode)
//獲得紅黑樹的節(jié)點(diǎn)
node = ((java.util.HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
//否則遞歸獲得鏈表節(jié)點(diǎn)
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);
}
}
//如果matchValue為true就需要判斷聂示，兩個對象時候相等，或者是否equals
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
//如果是紅黑樹節(jié)點(diǎn)
if (node instanceof java.util.HashMap.TreeNode)
((java.util.HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
//如果是鏈表且是鏈表的頭節(jié)點(diǎn)
else if (node == p)
tab[index] = node.next;
//如果是鏈表的中間節(jié)點(diǎn)
else
p.next = node.next;
//操作數(shù)+1
++modCount;
//size-1
--size;
//回調(diào)函數(shù)纵竖，目前實(shí)現(xiàn)為空
afterNodeRemoval(node);
return node;
}
}
return null;
}
最后
這里沒有涉及紅黑樹的算法部分
如果有寫的不正確的地方墓造，歡迎提出來，如果有不理解的地方解寝，也可以提出來
