技術(shù)博客已遷移至個(gè)人頁(yè)侣背，歡迎查看 yloopdaed.icu
您也可以關(guān)注 JPP - 這是一個(gè)Java養(yǎng)成計(jì)劃白华，需要您的加入。
IHAVEAQUESTION
為什么JDK1.7中HashMap鏈表插入時(shí)要在 遍歷完一遍鏈表 后贩耐，再采用頭插法弧腥？
數(shù)組
HashMap在JDK1.7中采用 數(shù)組+鏈表 的存儲(chǔ)結(jié)構(gòu)。
數(shù)組的角標(biāo)是在key值hashCode()的基礎(chǔ)上進(jìn)行多次高位移動(dòng)的擾動(dòng)后盡量保持散列潮太，代碼片段如下：
1 hash
final int hash(Object k) {
int h = hashSeed;
if (0 != h && k instanceof String) {
return sun.misc.Hashing.stringHash32((String) k);
}
h ^= k.hashCode();
// 多次讓高位參與運(yùn)算管搪，擾動(dòng)函數(shù)
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
2 % -> &
采用更搞笑的 &運(yùn)算虾攻。這里length為數(shù)組的長(zhǎng)度，源碼中巧妙的設(shè)計(jì)數(shù)組的長(zhǎng)度必須保持2的整數(shù)冪更鲁。這樣設(shè)計(jì)才能保證length-1計(jì)算后得到 全1 的的二進(jìn)制序列霎箍。
static int indexFor(int h, int length) {
return h & (length-1);
}
鏈表
數(shù)組的index確認(rèn)后澡为，就可以將鍵值對(duì)插入相應(yīng)位置的鏈表了漂坏。
public V put(K key, V value) {
...
int hash = hash(key); // hash
int i = indexFor(hash, table.length); // %
// 判斷hashmap中有沒(méi)有存在相同的key，如果有的話將這個(gè)key原來(lái)的value覆蓋媒至，并返回
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
...
// 擴(kuò)容，頭插
addEntry(hash, key, value, i);
return null;
}
上面的源碼部分只保留了關(guān)鍵部分
我們都知道JDK1.7中鏈表的插入方式是頭插筋夏。頭插與尾插相比是節(jié)省了一次鏈表全遍歷的時(shí)間。直接采用下面代碼即可完成：
// 鏈表頭插
table[bucketIndex] = new Entry<>(hash, key, value, table[bucketIndex]);
這部分代碼在put方法的addEntry()中，addEntry()方法在鏈表頭插之前做了擴(kuò)容操作指蚜。
但是奇怪的是涨椒，在上面put方法中有一段循環(huán)遍歷鏈表的代碼摊鸡，這段代碼的目的只是檢查要插入的Key值是否已經(jīng)存在在HashMap中，如果存在就修改蚕冬，同時(shí)將原來(lái)的值返回免猾。
這我就很疑惑了，為什么這里明明已經(jīng)遍歷過(guò)一遍鏈表了囤热，為什么不多寫一個(gè)else猎提，如果沒(méi)有找到存在的Key值，直接將目標(biāo)鍵值對(duì)插入在鏈表尾部呢旁蔼？都已經(jīng)遍歷完了锨苏，插個(gè)值咋了？
可能的原因只能是擴(kuò)容時(shí)機(jī)不好把握棺聊？
HashMap的擴(kuò)容機(jī)制是鍵值對(duì)size超過(guò)閾值后伞租，數(shù)組長(zhǎng)度擴(kuò)充至之前的兩倍，然后將原本下標(biāo)的全部鏈表遷移（這個(gè)遷移的過(guò)程會(huì)倒序鏈表限佩，也可能分散鏈表中的數(shù)據(jù)葵诈，以縮短鏈表的長(zhǎng)度）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
...
// 同一個(gè)元素轉(zhuǎn)移后的下標(biāo)有兩種情況。
// 1 與原來(lái)相同 2 在原來(lái)下標(biāo)基礎(chǔ)上加原數(shù)組長(zhǎng)度
int i = indexFor(e.hash, newCapacity);
// 這樣遍歷頭插后，鏈表的順序與之前相反
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
了解HashMap源碼的朋友可能都知道驯击，這個(gè)擴(kuò)容和遷移的代碼在高并發(fā)時(shí)并不是線程安全的烁兰。可能出現(xiàn)循環(huán)鏈表徊都，以至于get時(shí)陷入死循環(huán)沪斟。
也許正因如此，需要將鏈表插入和擴(kuò)容的代碼從之前的循環(huán)中獨(dú)立出來(lái)暇矫。并采用頭插的方式主之，盡量再循環(huán)一次鏈表。
最后
以上都是我在閱讀HashMap源碼后產(chǎn)生疑問(wèn)李根，獨(dú)立思考槽奕，自我解答的過(guò)程。
可能是很少有人產(chǎn)生跟我相似的疑問(wèn)房轿，所以我在網(wǎng)上也沒(méi)能查找到準(zhǔn)確的資料和答案粤攒。
所以以上全是自己的推斷和猜測(cè)。畢竟HashMap源碼不論是在數(shù)據(jù)結(jié)構(gòu)還是算法思想層面都是非常優(yōu)雅的囱持。別人這么設(shè)計(jì)肯定是有原因的夯接。哈哈
