- capacity <<= 1：
int i = 1;
//類(lèi)似于 i++就是 i = i+1;的這結(jié)構(gòu)
//i = i<<1 i等于i乘以2的1次方
//i <<= 1;
//i = i<<2 i等于i乘以2的2次方,>>就是相除了
i <<= 2;
System.out.println("結(jié)果是：" + i);
- java中有三種移位運(yùn)算符：
// <<：左移運(yùn)算符，num << 1,相當(dāng)于num乘以2
// >>：右移運(yùn)算符未巫，num >> 1,相當(dāng)于num除以2
// >>>：無(wú)符號(hào)右移荣瑟，忽略符號(hào)位，空位都以0補(bǔ)齊
無(wú)符號(hào)右移的規(guī)則只記住一點(diǎn)：忽略了符號(hào)位擴(kuò)展，0補(bǔ)最高位 無(wú)符號(hào)右移運(yùn)算符>>> 只是對(duì)32位和64位的值有意義
//保證hashCode 不同的算法
//int 是4位byte的 4*8=32bit 间聊，注意-->12+20=32
//h>>>20是無(wú)符號(hào)右移運(yùn)算，就是將int類(lèi)型的h的二進(jìn)制數(shù)字位往右移動(dòng)抵拘，左邊移出來(lái)的空位補(bǔ)上0哎榴。
//即為h = h ^ ((h >>> 20) ^ (h >>> 12));按位異或運(yùn)算，僅當(dāng)兩個(gè)對(duì)應(yīng)的二進(jìn)制位不相同時(shí)僵蛛，結(jié)果為1尚蝌；否則結(jié)果為0。
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
- 什么是哈希沖突：
- 哈希計(jì)算就是努力的把比較大的數(shù)據(jù)存放到相對(duì)較小的空間中充尉。最常見(jiàn)的哈希算法是取模法飘言。
- 取模法：數(shù)組的長(zhǎng)度是5。這時(shí)有一個(gè)數(shù)據(jù)是6驼侠。那么如何把這個(gè)6存放到長(zhǎng)度只有5的數(shù)組中呢姿鸿。按照取模法谆吴，計(jì)算6％5，結(jié)果是1般妙，那么就把6放到數(shù)組下標(biāo)是1的位置纪铺。那么，7就應(yīng)該放到2這個(gè)位置碟渺。到此位置鲜锚，沖突還沒(méi)有出現(xiàn)。這時(shí)苫拍，有個(gè)數(shù)據(jù)是11芜繁，按照取模法，11％5＝1绒极，也等于1骏令。那么原來(lái)數(shù)組下標(biāo)是1的地方已經(jīng)有數(shù)了，是6垄提。這時(shí)又計(jì)算出1這個(gè)位置榔袋，那么數(shù)組1這個(gè)位置，就必須儲(chǔ)存兩個(gè)數(shù)了铡俐。這時(shí)凰兑，就叫哈希沖突。沖突之后就要按照順序來(lái)存放了审丘。
- 如果數(shù)據(jù)的分布比較廣泛吏够，而且儲(chǔ)存數(shù)據(jù)的數(shù)組長(zhǎng)度比較大。那么哈希沖突就比較少滩报。否則沖突是很高的锅知。
HashMap就是一個(gè)散列表，它是通過(guò)“拉鏈法”解決哈希沖突的
- 什么是拉鏈法：
- 拉鏈法又叫鏈地址法脓钾，拉鏈法就是把具有相同散列地址的關(guān)鍵字(同義詞)值放在同一個(gè)單鏈表中售睹，稱(chēng)為同義詞鏈表。有m個(gè)散列地址就有m個(gè)鏈表惭笑，同時(shí)用指針數(shù)組T[0..m-1]存放各個(gè)鏈表的頭指針侣姆，凡是散列地址為i的記錄都以結(jié)點(diǎn)方式插入到以T[i]為指針的單鏈表中。T中各分量的初值應(yīng)為空指針.
- 簡(jiǎn)單來(lái)說(shuō)拉鏈法就是數(shù)組加鏈表沉噩。
- 大方向上，HashMap 里面是一個(gè)數(shù)組柱蟀，然后數(shù)組中每個(gè)元素是一個(gè)單向鏈表川蒙。
下圖中，每個(gè)綠色的實(shí)體是嵌套類(lèi) Entry 的實(shí)例长已，Entry 包含四個(gè)屬性：key, value, hash 值和用于單向鏈表的 next畜眨。
這個(gè)僅僅是示意圖昼牛，因?yàn)闆](méi)有考慮到數(shù)組要擴(kuò)容的情況
從HashMap的實(shí)現(xiàn)來(lái)看，我們總結(jié)拉鏈法的實(shí)現(xiàn)步驟如下：
1. 計(jì)算 key 的 hashValue
2. 根據(jù) hashValue 值定位到 table[hashIndex] 康聂。( table[hashIndex] 是一條鏈表Node)
3. 若 table[hashValue] 為空則直接插入贰健，不然則添加到鏈表末尾
