擾動(dòng)函數(shù)
- 默認(rèn)初始化的Map大小是16個(gè)長(zhǎng)度
DEFAULT_INITIAL_CAPACITY = 1 << 4 - 在HashMap存放元素時(shí)候有這樣一段代碼來處理哈希值留瞳，這是
java 8的散列值擾動(dòng)函數(shù)，用于優(yōu)化散列效果
static final int hash(Object key) {
int h;
// 將key的hash值和右移16位的hash進(jìn)行異或操作
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
- hashMap獲取
bucketIndex的方式是return h & (length-1);將hash值和map長(zhǎng)度減一進(jìn)行&操作(取模肾筐，只有為2的整次冪才等同于是取模)慷吊。
10100101 11000100 00100101
& 00000000 00000000 00001111 16-1=15
----------------------------------
00000000 00000000 00000101 //hash值高位全部歸零闲孤，只保留末四位
- 如果幾個(gè)hash值的后面幾為都相同豪治，就會(huì)導(dǎo)致碰撞情況洞拨，所以需要擾動(dòng)函數(shù)，hash值為int型大小為32bit负拟，右位移16位，正好是32bit的一半歹河，將自己的高半?yún)^(qū)和低半?yún)^(qū)做異或掩浙，就是為了混合原始哈希碼的高位和低位，以此來加大低位的隨機(jī)性秸歧。而且混合后的低位摻雜了高位的部分特征厨姚，這樣高位的信息也被變相保留下來。
HashMap的數(shù)組長(zhǎng)度為什么要取2的整次冪
因?yàn)?&任何都為0键菱，
return h & (length-1);操作為了減少length-1對(duì)hash值的影響谬墙，則需要保證length-1的二進(jìn)制為全是1，這樣就能保證最后的運(yùn)算結(jié)果经备，完全取決于hash的二進(jìn)制數(shù)拭抬。HashMap的大小總是2的整次冪，在HashMap初始化中
/**
* 將傳入cap-1的二進(jìn)制位全填充為0侵蒙，然后+1.
*/
static final int tableSizeFor(int cap) {
int n = cap - 1;
// 將n和右移一位的n進(jìn)行|操作造虎，1和任何進(jìn)行|操作都為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;
}
如傳入19
00000000 00000000 00010010 19-1=18的二進(jìn)制碼
00000000 00000000 00001001 18右移一位
----------------------------------
00000000 00000000 00011011 n，n>>1進(jìn)行或(|)運(yùn)算 變成28
00000000 00000000 00011011 28的二進(jìn)制碼
00000000 00000000 00000110 28右移兩位
----------------------------------
00000000 00000000 00011111 n纷闺，n>>2進(jìn)行或(|)運(yùn)算 變成32
00000000 00000000 00011111 32的二進(jìn)制碼
00000000 00000000 00000011 32右移三位
----------------------------------
00000000 00000000 00011111 n算凿，n>>3進(jìn)行或(|)運(yùn)算 變成32
后續(xù)相同，不斷用1占位犁功，最終會(huì)得到大于cap的最小2的整次冪
hashMap擴(kuò)容
- capacity 即容量氓轰，默認(rèn)16
- loadFactor 負(fù)載因子，默認(rèn)是0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;
- threshold 閾值浸卦。閾值=容量*加載因子署鸡。默認(rèn)12。當(dāng)元素?cái)?shù)量超過閾值時(shí)便會(huì)觸發(fā)擴(kuò)容
JDK1.7
- JDK7中，HashMap的內(nèi)部數(shù)據(jù)保存的都是鏈表储玫。map會(huì)遍歷數(shù)組的每個(gè)“桶”侍筛，然后遍歷桶中的每個(gè)Entity，重新計(jì)算其hash值（可能不計(jì)算）撒穷，找到新數(shù)組中的對(duì)應(yīng)位置匣椰，以頭插法插入新的鏈表。
- 因?yàn)槭穷^插法端礼，因此新舊鏈表的元素位置會(huì)發(fā)生轉(zhuǎn)置現(xiàn)象禽笑。
- 元素遷移的過程中在多線程情境下有可能會(huì)觸發(fā)死循環(huán)（無限進(jìn)行鏈表反轉(zhuǎn)）。
JDK1.8
由于數(shù)組的容量是以2的冪次方擴(kuò)容的蛤奥，那么一個(gè)Entity在擴(kuò)容時(shí)佳镜，新的位置要么在原位置，要么在原長(zhǎng)度+原位置凡桥。
如果原來hashMap大小為16蟀伸，進(jìn)行擴(kuò)容，原哈希值與擴(kuò)容新增出來的長(zhǎng)度16缅刽，進(jìn)行&運(yùn)算啊掏，如果值等于0，則下標(biāo)位置不變衰猛。如果不為0迟蜜，那么新的位置則是原來位置上加16
當(dāng)hash值的二進(jìn)制第5位為0的情況
10100101 11000100 00100101 原h(huán)ash
00000000 00000000 00001111 擴(kuò)容前 16-1=15
----------------------------------
00000000 00000000 00000101 結(jié)果為5
進(jìn)行擴(kuò)容，hashMap數(shù)組容量16*2=32啡省，最后4位顯然是相同的娜睛，唯一可能出現(xiàn)的區(qū)別就在第5位
10100101 11000100 00100101 原h(huán)ash
00000000 00000000 00011111 擴(kuò)容前 32-1=31
----------------------------------
00000000 00000000 00000101 結(jié)果為5
當(dāng)hash值的二進(jìn)制第5位為1的情況
10100101 11000100 00110101 原h(huán)ash
00000000 00000000 00001111 擴(kuò)容前 16-1=15
----------------------------------
00000000 00000000 00000101 結(jié)果為5
進(jìn)行擴(kuò)容，hashMap數(shù)組容量16*2=32卦睹，最后4位顯然是相同的畦戒，唯一可能出現(xiàn)的區(qū)別就在第5位
10100101 11000100 00110101 原h(huán)ash
00000000 00000000 00011111 擴(kuò)容前 32-1=31
----------------------------------
00000000 00000000 00010101 結(jié)果為5+16（二進(jìn)制10000）=21
結(jié)論：當(dāng)hashMap進(jìn)行擴(kuò)容時(shí)，只用原長(zhǎng)度和原h(huán)ash值進(jìn)行&計(jì)算分预，如果等于0則下標(biāo)不變兢交，否則新位置為 原位置+原h(huán)ashMap長(zhǎng)度
- JDK8在遷移元素時(shí)是正序的，不會(huì)出現(xiàn)鏈表轉(zhuǎn)置的發(fā)生笼痹。
- 如果某個(gè)桶內(nèi)的元素超過8個(gè)配喳，則會(huì)將鏈表轉(zhuǎn)化成紅黑樹，加快數(shù)據(jù)查詢效率凳干。
