說明：此文章是轉(zhuǎn)載文章，僅添加個人些許內(nèi)容。轉(zhuǎn)載地址：https://blog.csdn.net/zxt0601/article/details/77413921
本文介紹
1、HashMap相關(guān)面試題。
2框咙、HashMap基本信息。
3痢甘、HashMap屬性和方法喇嘱。
4、HashMap的總結(jié)塞栅。
5者铜、HashMap最佳實(shí)踐。
相關(guān)面試題
Hashtable與HashMap的區(qū)別放椰？
平時在使用HashMap時一般使用什么類型的元素作為Key作烟？
如何衡量一個hash算法的好壞，你知道的常用hash算法有哪些砾医？
為什么HashMap中bucket的大小為什么是2的冪拿撩？
接下我們就帶著問題去看HashMap源碼，主要順序是HashMap的簡介如蚜、屬性以及方法的介紹压恒。
概述
本文將從幾個常用方法下手，來閱讀HashMap的源碼怖亭。
按照從構(gòu)造方法->常用API（增涎显、刪、改兴猩、查）的順序來閱讀源碼期吓，并會講解閱讀方法中涉及的一些變量的意義。了解HashMap的特點(diǎn)倾芝、適用場景讨勤。
概要
概括的說，HashMap 是一個關(guān)聯(lián)數(shù)組晨另、哈希表潭千，它是線程不安全的，允許key為null,value為null借尿，遍歷時無序刨晴。
其底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組稱之為哈希桶屉来，每個桶里面放的是鏈表，鏈表中的每個節(jié)點(diǎn)狈癞，就是哈希表中的每個元素茄靠。
在JDK8中，當(dāng)鏈表長度達(dá)到8蝶桶，會轉(zhuǎn)化成紅黑樹慨绳，以提升它的查詢、插入效率真竖，它實(shí)現(xiàn)了Map<K,V>, Cloneable, Serializable接口脐雪。
因其底層哈希桶的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，所以也會涉及到擴(kuò)容的問題恢共。
當(dāng)HashMap的容量達(dá)到 threshold 域值時战秋，就會觸發(fā)擴(kuò)容。擴(kuò)容前后讨韭，哈希桶的長度一定會是2的次方获询。
這樣在根據(jù)key的hash值尋找對應(yīng)的哈希桶時，可以用位運(yùn)算替代取余操作拐袜，更加高效。
而key的hash值，并不僅僅只是key對象的 hashCode() 方法的返回值，還會經(jīng)過擾動函數(shù)的擾動仿贬，以使hash值更加均衡锌云。
因?yàn)閔ashCode()是int類型，取值范圍是40多億饼记，只要哈希函數(shù)映射的比較均勻松散，碰撞幾率是很小的。
但就算原本的hashCode()取得很好规阀，每個key的hashCode()不同，但是由于HashMap的哈希桶的長度遠(yuǎn)比hash取值范圍小瘦麸，默認(rèn)是16谁撼，所以當(dāng)對hash值以桶的長度取余，以找到存放該key的桶的下標(biāo)時滋饲，由于取余是通過與操作完成的厉碟，會忽略hash值的高位。因此只有hashCode()的低位參加運(yùn)算屠缭，發(fā)生不同的hash值箍鼓，但是得到的index相同的情況的幾率會大大增加，這種情況稱之為hash碰撞呵曹。 即款咖，碰撞率會增大何暮。
擾動函數(shù)就是為了解決hash碰撞的。它會綜合hash值高位和低位的特征铐殃，并存放在低位海洼，因此在與運(yùn)算時，相當(dāng)于高低位一起參與了運(yùn)算背稼，以減少hash碰撞的概率贰军。（在JDK8之前，擾動函數(shù)會擾動四次蟹肘，JDK8簡化了這個操作）
擴(kuò)容操作時词疼，會new一個新的Node數(shù)組作為哈希桶，然后將原哈希表中的所有數(shù)據(jù)(Node節(jié)點(diǎn))移動到新的哈希桶中帘腹，相當(dāng)于對原哈希表中所有的數(shù)據(jù)重新做了一個put操作贰盗。所以性能消耗很大，可想而知阳欲，在哈希表的容量越大時舵盈，性能消耗越明顯。
擴(kuò)容時球化，如果發(fā)生過哈希碰撞秽晚，節(jié)點(diǎn)數(shù)小于8個。則要根據(jù)鏈表上每個節(jié)點(diǎn)的哈希值筒愚，依次放入新哈希桶對應(yīng)下標(biāo)位置赴蝇。
因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個節(jié)點(diǎn)巢掺，現(xiàn)在可能存放在原來的下標(biāo)句伶，即low位， 或者擴(kuò)容后的下標(biāo)陆淀，即high位考余。 high位= low位+原哈希桶容量
如果追加節(jié)點(diǎn)后，鏈表數(shù)量>=8轧苫，則轉(zhuǎn)化為紅黑樹
由迭代器的實(shí)現(xiàn)可以看出楚堤，遍歷HashMap時，順序是按照哈希桶從低到高含懊，鏈表從前往后钾军，依次遍歷的。屬于無序集合绢要。
整個HashMap示意圖：圖片來源于網(wǎng)絡(luò)吏恭，侵刪：
HashMap的源碼中，充斥個各種位運(yùn)算代替常規(guī)運(yùn)算的地方重罪，以提升效率：
- 與運(yùn)算替代模運(yùn)算樱哼。用 hash & (table.length-1) 替代 hash % (table.length)
- 用if ((e.hash & oldCap) == 0)判斷擴(kuò)容后哀九，節(jié)點(diǎn)e處于低區(qū)還是高區(qū)。
鏈表節(jié)點(diǎn)Node
在開始之前搅幅，我們先看一下掛載在哈希表上的元素阅束，鏈表的結(jié)構(gòu)：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;//哈希值
final K key;//key
V value;//value
Node<K,V> next;//鏈表后置節(jié)點(diǎn)
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; }
//每一個節(jié)點(diǎn)的hash值，是將key的hashCode 和 value的hashCode 亦或得到的茄唐。
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//設(shè)置新的value 同時返回舊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;
}
}
由此可知息裸，這是一個單鏈表。
每一個節(jié)點(diǎn)的hash值沪编，是將key的hashCode 和 value的hashCode 異或得到的呼盆。**
構(gòu)造函數(shù)
//最大容量 2的30次方
static final int MAXIMUM_CAPACITY = 1 << 30;
//默認(rèn)的加載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;
//哈希桶，存放鏈表蚁廓。 長度是2的N次方访圃，或者初始化時為0.
transient Node<K,V>[] table;
//加載因子，用于計(jì)算哈希表元素?cái)?shù)量的閾值相嵌。 threshold = 哈希桶.length * loadFactor;
final float loadFactor;
//哈希表內(nèi)元素?cái)?shù)量的閾值腿时，當(dāng)哈希表內(nèi)元素?cái)?shù)量超過閾值時，會發(fā)生擴(kuò)容resize()饭宾。
int threshold;
public HashMap() {
//默認(rèn)構(gòu)造函數(shù)批糟，賦值加載因子為默認(rèn)的0.75f
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
public HashMap(int initialCapacity) {
//指定初始化容量的構(gòu)造函數(shù)
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
//同時指定初始化容量 以及 加載因子， 用的很少看铆，一般不會修改loadFactor
public HashMap(int initialCapacity, float loadFactor) {
//邊界處理
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
//初始容量最大不能超過2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
//顯然加載因子不能為負(fù)數(shù)
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
//設(shè)置閾值為 >=初始化容量的 2的n次方的值
this.threshold = tableSizeFor(initialCapacity);
}
//新建一個哈希表跃赚，同時將另一個map m 里的所有元素加入表中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//根據(jù)期望容量cap，返回2的n次方形式的 哈希桶的實(shí)際容量 length性湿。 返回值一般會>=cap
static final int tableSizeFor(int cap) {
//經(jīng)過下面的 或 和位移 運(yùn)算， n最終各位都是1满败。
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判斷n是否越界肤频，返回 2的n次方作為 table（哈希桶）的閾值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
//將另一個Map的所有元素加入表中，參數(shù)evict初始化時為false算墨，其他情況為true
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//拿到m的元素?cái)?shù)量
int s = m.size();
//如果數(shù)量大于0
if (s > 0) {
//如果當(dāng)前表是空的
if (table == null) { // pre-size
//根據(jù)m的元素?cái)?shù)量和當(dāng)前表的加載因子宵荒，計(jì)算出閾值
float ft = ((float)s / loadFactor) + 1.0F;
//修正閾值的邊界 不能超過MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果新的閾值大于當(dāng)前閾值
if (t > threshold)
//返回一個 》=新的閾值的 滿足2的n次方的閾值
threshold = tableSizeFor(t);
}
//如果當(dāng)前元素表不是空的，但是 m的元素?cái)?shù)量大于閾值净嘀，說明一定要擴(kuò)容报咳。
else if (s > threshold)
resize();
//遍歷 m 依次將元素加入當(dāng)前表中。
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
putVal(hash(key), key, value, false, evict);
}
}
}
先看一下擴(kuò)容函數(shù)： 這是一個重點(diǎn)挖藏！重點(diǎn)暑刃！重點(diǎn)！
初始化或加倍哈希桶大小膜眠。如果是當(dāng)前哈希桶是null,分配符合當(dāng)前閾值（默認(rèn)閾值是12） 的初始容量（默認(rèn)初始容量是16）岩臣。
否則溜嗜，因?yàn)槲覀償U(kuò)容成以前的兩倍。
在擴(kuò)容時架谎，要注意區(qū)分以前在哈希桶相同index的節(jié)點(diǎn)炸宵，現(xiàn)在是在以前的index里，還是index+oldlength 里
final Node<K,V>[] resize() {
//oldTab 為當(dāng)前表的哈希桶
Node<K,V>[] oldTab = table;
//當(dāng)前哈希桶的容量 length
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//當(dāng)前的閾值
int oldThr = threshold;
//初始化新的容量和閾值為0
int newCap, newThr = 0;
//如果當(dāng)前容量大于0
if (oldCap > 0) {
//如果當(dāng)前容量已經(jīng)到達(dá)上限
if (oldCap >= MAXIMUM_CAPACITY) {
//則設(shè)置閾值是2的31次方-1
threshold = Integer.MAX_VALUE;
//同時返回當(dāng)前的哈希桶谷扣，不再擴(kuò)容
return oldTab;
}//否則新的容量為舊的容量的兩倍土全。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)//如果舊的容量大于等于默認(rèn)初始容量16
//那么新的閾值也等于舊的閾值的兩倍
newThr = oldThr << 1; // double threshold
}//如果當(dāng)前表是空的，但是有閾值会涎。代表是初始化時指定了容量裹匙、閾值的情況
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;//那么新表的容量就等于舊的閾值
else {}//如果當(dāng)前表是空的，而且也沒有閾值在塔。代表是初始化時沒有任何容量/閾值參數(shù)的情況 // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;//此時新表的容量為默認(rèn)的容量 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);//新的閾值為默認(rèn)容量16 * 默認(rèn)加載因子0.75f = 12
}
if (newThr == 0) {//如果新的閾值是0幻件，對應(yīng)的是 當(dāng)前表是空的，但是有閾值的情況
float ft = (float)newCap * loadFactor;//根據(jù)新表容量 和 加載因子 求出新的閾值
//進(jìn)行越界修復(fù)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新閾值
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
//根據(jù)新的容量 構(gòu)建新的哈希桶
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//更新哈希桶引用
table = newTab;
//如果以前的哈希桶中有元素
//下面開始將當(dāng)前哈希桶中的所有節(jié)點(diǎn)轉(zhuǎn)移到新的哈希桶中
if (oldTab != null) {
//遍歷老的哈希桶
for (int j = 0; j < oldCap; ++j) {
//取出當(dāng)前的節(jié)點(diǎn) e
Node<K,V> e;
//如果當(dāng)前桶中有元素,則將鏈表賦值給e
if ((e = oldTab[j]) != null) {
//將原哈希桶置空以便GC
oldTab[j] = null;
//如果當(dāng)前鏈表中就一個元素蛔溃，（沒有發(fā)生哈希碰撞）
if (e.next == null)
//直接將這個元素放置在新的哈希桶里绰沥。
//注意這里取下標(biāo) 是用 哈希值 與 桶的長度-1 。 由于桶的長度是2的n次方贺待，這么做其實(shí)是等于 一個模運(yùn)算徽曲。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果發(fā)生過哈希碰撞 ,而且是節(jié)點(diǎn)數(shù)超過8個，轉(zhuǎn)化成了紅黑樹（暫且不談 避免過于復(fù)雜麸塞， 后續(xù)專門研究一下紅黑樹）
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果發(fā)生過哈希碰撞秃臣，節(jié)點(diǎn)數(shù)小于8個。則要根據(jù)鏈表上每個節(jié)點(diǎn)的哈希值哪工，依次放入新哈希桶對應(yīng)下標(biāo)位置奥此。
else { // preserve order
//因?yàn)閿U(kuò)容是容量翻倍，所以原鏈表上的每個節(jié)點(diǎn)雁比，現(xiàn)在可能存放在原來的下標(biāo)稚虎，即low位， 或者擴(kuò)容后的下標(biāo)偎捎，即high位蠢终。 high位= low位+原哈希桶容量
//低位鏈表的頭結(jié)點(diǎn)、尾節(jié)點(diǎn)
Node<K,V> loHead = null, loTail = null;
//高位鏈表的頭節(jié)點(diǎn)茴她、尾節(jié)點(diǎn)
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;//臨時節(jié)點(diǎn) 存放e的下一個節(jié)點(diǎn)
do {
next = e.next;
//這里又是一個利用位運(yùn)算 代替常規(guī)運(yùn)算的高效點(diǎn)： 利用哈希值 與 舊的容量寻拂，可以得到哈希值去模后，是大于等于oldCap還是小于oldCap丈牢，等于0代表小于oldCap祭钉，應(yīng)該存放在低位，否則存放在高位
if ((e.hash & oldCap) == 0) {
//給頭尾節(jié)點(diǎn)指針賦值
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}//高位也是相同的邏輯
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}//循環(huán)直到鏈表結(jié)束
} while ((e = next) != null);
//將低位鏈表存放在原index處己沛，
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
//將高位鏈表存放在新index處
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
再看一下 往哈希表里插入一個節(jié)點(diǎn)的 putVal 函數(shù),如果參數(shù) onlyIfAbsent 是true朴皆，那么不會覆蓋相同key的值value帕识。如果evict是false。那么表示是在初始化時調(diào)用的
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab存放 當(dāng)前的哈希桶遂铡， p用作臨時鏈表節(jié)點(diǎn)
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果當(dāng)前哈希表是空的肮疗，代表是初始化
if ((tab = table) == null || (n = tab.length) == 0)
//那么直接去擴(kuò)容哈希表，并且將擴(kuò)容后的哈希桶長度賦值給n
n = (tab = resize()).length;
//如果當(dāng)前index的節(jié)點(diǎn)是空的扒接，表示沒有發(fā)生哈希碰撞伪货。 直接構(gòu)建一個新節(jié)點(diǎn)Node，掛載在index處即可钾怔。
//這里再啰嗦一下碱呼，index 是利用 哈希值 & 哈希桶的長度-1，替代模運(yùn)算
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {//否則 發(fā)生了哈希沖突宗侦。
//e
Node<K,V> e; K k;
//如果哈希值相等愚臀，key也相等，則是覆蓋value操作
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;//將當(dāng)前節(jié)點(diǎn)引用賦值給e
else if (p instanceof TreeNode)//紅黑樹暫且不談
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {//不是覆蓋操作矾利，則插入一個普通鏈表節(jié)點(diǎn)
//遍歷鏈表
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {//遍歷到尾部姑裂，追加新節(jié)點(diǎn)到尾部
p.next = newNode(hash, key, value, null);
//如果追加節(jié)點(diǎn)后，鏈表數(shù)量》=8男旗，則轉(zhuǎn)化為紅黑樹
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//如果找到了要覆蓋的節(jié)點(diǎn)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果e不是null舶斧，說明有需要覆蓋的節(jié)點(diǎn)，
if (e != null) { // existing mapping for key
//則覆蓋節(jié)點(diǎn)值察皇，并返回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//這是一個空實(shí)現(xiàn)的函數(shù)茴厉，用作LinkedHashMap重寫使用。
afterNodeAccess(e);
return oldValue;
}
}
//如果執(zhí)行到了這里什荣，說明插入了一個新的節(jié)點(diǎn)矾缓，所以會修改modCount，以及返回null稻爬。
//修改modCount
++modCount;
//更新size嗜闻，并判斷是否需要擴(kuò)容。
if (++size > threshold)
resize();
//這是一個空實(shí)現(xiàn)的函數(shù)因篇，用作LinkedHashMap重寫使用。
afterNodeInsertion(evict);
return null;
}
newNode如下：構(gòu)建一個鏈表節(jié)點(diǎn)
// Create a regular (non-tree) node
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
小結(jié)：
- 運(yùn)算盡量都用位運(yùn)算代替笔横，更高效竞滓。
- 對于擴(kuò)容導(dǎo)致需要新建數(shù)組存放更多元素時，除了要將老數(shù)組中的元素遷移過來吹缔，也記得將老數(shù)組中的引用置null商佑，以便GC
- 取下標(biāo) 是用 哈希值 與運(yùn)算 （桶的長度-1） i = (n - 1) & hash。 由于桶的長度是2的n次方厢塘，這么做其實(shí)是等于 一個模運(yùn)算茶没。但是效率更高
- 擴(kuò)容時肌幽，如果發(fā)生過哈希碰撞，節(jié)點(diǎn)數(shù)小于8個抓半。則要根據(jù)鏈表上每個節(jié)點(diǎn)的哈希值喂急，依次放入新哈希桶對應(yīng)下標(biāo)位置。
- 因?yàn)閿U(kuò)容是容量翻倍笛求，所以原鏈表上的每個節(jié)點(diǎn)廊移，現(xiàn)在可能存放在原來的下標(biāo)，即low位探入， 或者擴(kuò)容后的下標(biāo)狡孔，即high位。 high位= low位+原哈希桶容量
- 利用哈希值 與運(yùn)算 舊的容量 蜂嗽，if ((e.hash & oldCap) == 0),可以得到哈希值去模后苗膝，是大于等于oldCap還是小于oldCap，等于0代表小于oldCap植旧，應(yīng)該存放在低位辱揭，否則存放在高位。這里又是一個利用位運(yùn)算 代替常規(guī)運(yùn)算的高效點(diǎn)
- 如果追加節(jié)點(diǎn)后隆嗅，鏈表數(shù)量>=8界阁，則轉(zhuǎn)化為紅黑樹
- 插入節(jié)點(diǎn)操作時，有一些空實(shí)現(xiàn)的函數(shù)胖喳，用作LinkedHashMap重寫使用泡躯。
增、改
1 往表中插入或覆蓋一個key-value
public V put(K key, V value) {
//先根據(jù)key丽焊，取得hash值较剃。 再調(diào)用上一節(jié)的方法插入節(jié)點(diǎn)
return putVal(hash(key), key, value, false, true);
}
這個根據(jù)key取hash值的函數(shù)也要關(guān)注一下，它稱之為“擾動函數(shù)”技健，關(guān)于這個函數(shù)的用處 開頭已經(jīng)總結(jié)過了：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
而key的hash值写穴，并不僅僅只是key對象的 hashCode() 方法的返回值，還會經(jīng)過擾動函數(shù)的擾動雌贱，以使hash值更加均衡啊送。
因?yàn)閔ashCode()是int類型，取值范圍是40多億欣孤，只要哈希函數(shù)映射的比較均勻松散馋没，碰撞幾率是很小的。
但就算原本的hashCode()取得很好降传，每個key的hashCode()不同篷朵，但是由于HashMap的哈希桶的長度遠(yuǎn)比hash取值范圍小，默認(rèn)是16，所以當(dāng)對hash值以桶的長度取余声旺，以找到存放該key的桶的下標(biāo)時笔链，由于取余是通過與操作完成的，會忽略hash值的高位腮猖。因此只有hashCode()的低位參加運(yùn)算鉴扫，發(fā)生不同的hash值，但是得到的index相同的情況的幾率會大大增加缚够，這種情況稱之為hash碰撞幔妨。 即，碰撞率會增大谍椅。
2 往表中批量增加數(shù)據(jù)
public void putAll(Map<? extends K, ? extends V> m) {
//這個函數(shù)上一節(jié)也已經(jīng)分析過误堡。//將另一個Map的所有元素加入表中，參數(shù)evict初始化時為false雏吭，其他情況為true
putMapEntries(m, true);
}
3 只會往表中插入 key-value, 若key對應(yīng)的value之前存在锁施，不會覆蓋。（jdk8增加的方法）
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}
刪
以key為條件刪除
如果key對應(yīng)的value存在杖们，則刪除這個鍵值對悉抵。 并返回value。如果不存在 返回null摘完。
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
//從哈希表中刪除某個節(jié)點(diǎn)姥饰， 如果參數(shù)matchValue是true，則必須key 孝治、value都相等才刪除列粪。
//如果movable參數(shù)是false，在刪除節(jié)點(diǎn)時谈飒，不移動其他節(jié)點(diǎn)
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// p 是待刪除節(jié)點(diǎn)的前置節(jié)點(diǎn)
Node<K,V>[] tab; Node<K,V> p; int n, index;
//如果哈希表不為空岂座，則根據(jù)hash值算出的index下 有節(jié)點(diǎn)的話。
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node是待刪除節(jié)點(diǎn)
Node<K,V> node = null, e; K k; V v;
//如果鏈表頭的就是需要刪除的節(jié)點(diǎn)
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;//將待刪除節(jié)點(diǎn)引用賦給node
else if ((e = p.next) != null) {//否則循環(huán)遍歷 找到待刪除節(jié)點(diǎn)杭措，賦值給node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
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);
}
}
//如果有待刪除節(jié)點(diǎn)node费什， 且 matchValue為false，或者值也相等
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)//如果node == p手素，說明是鏈表頭是待刪除節(jié)點(diǎn)
tab[index] = node.next;
else//否則待刪除節(jié)點(diǎn)在表中間
p.next = node.next;
++modCount;//修改modCount
--size;//修改size
afterNodeRemoval(node);//LinkedHashMap回調(diào)函數(shù)
return node;
}
}
return null;
}
void afterNodeRemoval(Node<K,V> p) { }
以key value 為條件刪除
@Override
public boolean remove(Object key, Object value) {
//這里傳入了value 同時matchValue為true
return removeNode(hash(key), key, value, true, true) != null;
}
查
以key為條件鸳址，找到返回value。沒找到返回null
public V get(Object key) {
Node<K,V> e;
//傳入擾動后的哈希值 和 key 找到目標(biāo)節(jié)點(diǎn)Node
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//傳入擾動后的哈希值 和 key 找到目標(biāo)節(jié)點(diǎn)Node
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//查找過程和刪除基本差不多泉懦， 找到返回節(jié)點(diǎn)稿黍，否則返回null
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) {
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;
}
判斷是否包含該key
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
判斷是否包含value
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
//遍歷哈希桶上的每一個鏈表
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//如果找到value一致的返回true
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
java8新增，帶默認(rèn)值的get方法
以key為條件祠斧，找到了返回value闻察。否則返回defaultValue
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}
遍歷
//緩存 entrySet
transient Set<Map.Entry<K,V>> entrySet;
*/
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
//一般我們用到EntrySet拱礁，都是為了獲取iterator
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
//最終還是調(diào)用getNode方法
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
//最終還是調(diào)用removeNode方法
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
//琢锋。辕漂。。
}
//EntryIterator的實(shí)現(xiàn)：
final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}
abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
//因?yàn)閔ashmap也是線程不安全的吴超，所以要保存modCount钉嘹。用于fail-fast策略
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
//next 初始時，指向 哈希桶上第一個不為null的鏈表頭
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
//由這個方法可以看出鲸阻，遍歷HashMap時跋涣，順序是按照哈希桶從低到高，鏈表從前往后鸟悴，依次遍歷的陈辱。屬于無序集合。
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
//fail-fast策略
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//依次取鏈表下一個節(jié)點(diǎn)细诸，
if ((next = (current = e).next) == null && (t = table) != null) {
//如果當(dāng)前鏈表節(jié)點(diǎn)遍歷完了沛贪，則取哈希桶下一個不為null的鏈表頭
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
////fail-fast策略
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
//最終還是利用removeNode 刪除節(jié)點(diǎn)
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}
HashMap與HashTable的區(qū)別
- 與之相比HashTable是線程安全的，且不允許key震贵、value是null利赋。
- HashTable默認(rèn)容量是11。
- HashTable是直接使用key的hashCode(key.hashCode())作為hash值猩系，不像HashMap內(nèi)部使用static final int * hash(Object key)擾動函數(shù)對key的hashCode進(jìn)行擾動后作為hash值媚送。
- HashTable取哈希桶下標(biāo)是直接用模運(yùn)算%.（因?yàn)槠淠J(rèn)容量也不是2的n次方。所以也無法用位運(yùn)算替代模運(yùn)算）
- 擴(kuò)容時寇甸，新容量是原來的2倍+1塘偎。int newCapacity = (oldCapacity << 1) + 1;
- Hashtable是Dictionary的子類同時也實(shí)現(xiàn)了Map接口，HashMap是Map接口的一個實(shí)現(xiàn)類幽纷；
最佳實(shí)踐
- 由于非線程安全式塌，不要在多線程場景下使用
- 初始化時指定其容量， 減少resize()方法的執(zhí)行
- key使用不可變的對象友浸，如String
總結(jié)
第一次看HashMap源碼我的內(nèi)心是崩潰的峰尝，大段大段的代碼直接向你撲來，好可怕笆栈帧武学！想必大部分小伙伴都有類似感覺，相信我你并不孤單伦意。這跟之前ArrayList和LinkedList根本不是同一個級別好嘛火窒，但是如果我們直接就逃避困難直接不看了，這是非常低效率的一種學(xué)習(xí)方法驮肉。相信我這是每位學(xué)習(xí)Java的小伙伴必須要邁過的坎熏矿。
說說我是怎么把HashMap啃下來的。先看幾篇blog，這時那大段大段代碼是看不懂的票编，接下來寫個小例子debug褪储，然后跟著文章一行一行代碼進(jìn)行理解，就這樣最終把HashMap啃了下來慧域。
引文
HashMap相關(guān)面試題
https://blog.csdn.net/qq_27093465/article/details/52209814
HashMap源碼分析
https://blog.csdn.net/fighterandknight/article/details/61624150
圖解HashMap原理
http://www.reibang.com/p/dde9b12343c1
