上次寫(xiě)到了HashMap的put函數(shù)原理,這次我們來(lái)看一看HashMap在調(diào)用get函數(shù)的時(shí)候是什么原理.
上文已經(jīng)提到了HashMap的數(shù)據(jù)結(jié)構(gòu)是數(shù)組 + 鏈表/樹(shù) 的結(jié)構(gòu) 臀稚，那么我們要怎么樣才能根據(jù)key命中對(duì)應(yīng)的目標(biāo)呢售躁，且聽(tīng)分解.
強(qiáng)調(diào)一下 jdk版本為 1.8.0_121
以下為get(key)源碼
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
get(Object key) 中，首先對(duì)key進(jìn)行hash處理,然后將hash值以及key傳入getNode(int hash, Object key),那么實(shí)際上就是由getNode函數(shù)去查詢對(duì)應(yīng)的Node/Entry。
接下來(lái)我們來(lái)分析getNode源碼:
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
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) {
//將table賦值到tab并判斷是否有值并且通過(guò)(n-1) & hash 計(jì)算出key所對(duì)應(yīng)的下標(biāo),找到該下標(biāo)的元素判斷其是否為null
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//這里first元素便是所屬鏈表的入口元素 若first的hash以及k值與key的完全相同那么返回first
return first;
if ((e = first.next) != null) {
//這里獲取到first下一個(gè)元素 并判斷元素類型,若是TreeNode則使用平衡樹(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))))
//判斷他們的hash以及key值 返回滿足條件的元素
return e;
} while ((e = e.next) != null);
}
}
return null;
}
到這里，結(jié)合上一篇文章 HashMap PUT 詳解 首先要理解HashMap的數(shù)據(jù)結(jié)構(gòu),
結(jié)合數(shù)據(jù)結(jié)構(gòu)再去看源碼就十分容易理解了.
那么通過(guò)源碼的分析我們還能得出一些HashMap需要注意的點(diǎn):
1.盡量使用String和一些不可變類型作為key值.由源碼我們可以看出,會(huì)大量使用hash來(lái)進(jìn)行運(yùn)算,由于String 為final，對(duì)象不可變，因此hash值也會(huì)保證不變。
2.由于HashMap線程不安全,當(dāng)多個(gè)線程put時(shí)可能會(huì)造成線程數(shù)據(jù)丟失.
3.HashMap數(shù)據(jù)擴(kuò)容, 其實(shí)在上一篇中在put函數(shù)末尾有這么一句代碼
if (++size > threshold)
resize();
當(dāng)數(shù)組大小大于閾值時(shí)會(huì)進(jìn)行擴(kuò)容,創(chuàng)建一個(gè)于當(dāng)前數(shù)據(jù)兩倍大小的數(shù)據(jù),并把舊數(shù)據(jù)放入新數(shù)組中碱茁。
4.在1.8之前resize的代碼跟1.8的區(qū)別比較大,建議大家對(duì)比一下。這里涉及到的是一個(gè)環(huán)形鏈表的問(wèn)題仿贬，在1.8之前的版本纽竣，當(dāng)兩個(gè)線程同時(shí)擴(kuò)容，會(huì)打亂鏈表順序有一定幾率形成環(huán)形鏈表導(dǎo)致無(wú)限循環(huán)茧泪。那么我們看看現(xiàn)在的resize代碼如下:
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
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) {//這里針對(duì)hash值對(duì)應(yīng)下標(biāo)沒(méi)有變化的元素
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) {
//著重看這里 會(huì)將loTail的next設(shè)置為null
//loTail 表示尾部元素
//這里每次循環(huán)鏈表完成組裝后便會(huì)設(shè)置尾部元素的next為null 避免了環(huán)形鏈表的產(chǎn)生
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;//這里同上理
newTab[j + oldCap] = hiHead;
}
}
}
}
resize代碼比較長(zhǎng) 這里我只貼了比較重要的部分.
所以在1.8開(kāi)始 hashMap不會(huì)造成環(huán)形鏈表了哈蜓氨，大家注意了
本篇get 以及 resize就說(shuō)到這里了。
接下來(lái)的文章我準(zhǔn)備說(shuō)說(shuō)ConcurrentMap,給自己加油队伟！
