- capacity <<= 1：
int i = 1;
//類似于 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類型的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è)單鏈表中，稱為同義詞鏈表。有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í)體是嵌套類 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] 為空則直接插入，不然則添加到鏈表末尾
