對于hashmap 其實(shí)我之前已有一些了解，一種鍵值對結(jié)構(gòu)的存儲方案，不過在使用時(shí)并沒有對其進(jìn)行深入的了解，那么今天我就和大家一起進(jìn)入HashMap的世界.
首先我們來說一下HashMap的數(shù)據(jù)結(jié)構(gòu):
HashMap 使用數(shù)組 + 鏈表的結(jié)構(gòu)來進(jìn)行數(shù)據(jù)存儲.
如上圖所示,數(shù)組中每個(gè)元素都是自身鏈表的入口元素,每個(gè)node都包含next字段用于保存下個(gè)元素。
接下來我們看看HashMap如何將數(shù)據(jù)寫入，先看put源碼如下：
HashMap hashMap = new HashMap();
System.out.println(hashMap.put("1", "123"));
如以上兩行代碼所示, 我定義了hashmap 并調(diào)用其put方法，那么要了解其運(yùn)行邏輯咱們就得進(jìn)入put函數(shù)看源碼了 如下：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
這里其實(shí)可以看到,put 函數(shù)調(diào)用了hashmap對象的putVal函數(shù)，putVal有五個(gè)參數(shù)，每個(gè)參數(shù)的解釋如下：
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
我們繼續(xù)往下來看putVal的詳細(xì)代碼：
final V putVal(int hash,
K key,
V value,
boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab;
Node<K,V> p;
int n, i;
if ((tab = table) == null || (n = tab.length) == 0) //將table賦值給tab并判斷是否為空
n = (tab = resize()).length; //若為空,初始化tab數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null) //根據(jù)數(shù)組長度與hash值進(jìn)行&運(yùn)算決定當(dāng)前數(shù)據(jù)存儲下標(biāo),并判斷當(dāng)前下標(biāo)是否有元素存在
tab[i] = newNode(hash, key, value, null); //若沒有元素則新建node并保存
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k)))) //若下標(biāo)沖突，判斷其hash以及key是否一致
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else { //若不一致,需要遍歷p鏈表，找出相應(yīng)的位置存放
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) { //這里e對象已經(jīng)被賦值了哦 這對于后面的理解很重要
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash); //若循環(huán)次數(shù)達(dá)到8次 則這里會轉(zhuǎn)換數(shù)據(jù)結(jié)構(gòu)為平衡樹結(jié)構(gòu)
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) //若hash值與key相同則退出循環(huán)
break;
p = e; //若都不滿足 則將p賦值為e(e = p.next)
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null) //這里根據(jù)入?yún)⒁约皁ldValue來決定是否覆蓋老數(shù)據(jù)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize(); //這里是對map的擴(kuò)容，當(dāng)tab元素的數(shù)量大于閾值
afterNodeInsertion(evict);
return null;
}
流程如下：
1，首先，判斷當(dāng)前hashmap對象是否有值，如果沒有值那么初始化tab 并指定容量
2，通過 & hash運(yùn)算獲取對應(yīng)下標(biāo)元素并賦值到p，如果p為null 則新建node并賦值到tab當(dāng)前index
3，若前兩個(gè)條件都不滿足，那么表示該hashmap數(shù)據(jù)有值且出現(xiàn)了下標(biāo)沖突，
那么這個(gè)時(shí)候首先判斷出現(xiàn)沖突的兩個(gè)node對象的hash值以及key是否一致，若為true,那么更新key對應(yīng)的value(這里是否要更新取決于參數(shù)onlyIfAbsent 默認(rèn)為false)
4.若hash值或者key不一致，那么判斷p元素是否是TreeNode實(shí)例，
若是則put到平衡樹結(jié)構(gòu)。
5，若p不是TreeNode實(shí)例，那么這里又要去遍歷p 這個(gè)鏈表, 若有相同的key以及hash則停止遍歷,若沒有那么將生成新的node放入鏈表最后
閾值threshold的計(jì)算默認(rèn)是map長度 * 0.75.
可以通過new HashMap(int capacity, double flator)的構(gòu)造函數(shù)設(shè)置
這里是對于put的一些分析，后面會繼續(xù)寫get函數(shù)的分析。
有不足之處請及時(shí)指出.
