Map大家族的那點(diǎn)事兒(4) ：HashMap
2018-09-11 來(lái)源：importnew
HashMap
光從名字上應(yīng)該也能猜到，HashMap肯定是基于hash算法實(shí)現(xiàn)的，這種基于hash實(shí)現(xiàn)的map叫做散列表（hash table）。
散列表中維護(hù)了一個(gè)數(shù)組，數(shù)組的每一個(gè)元素被稱為一個(gè)桶（bucket），當(dāng)你傳入一個(gè)key = "a"進(jìn)行查詢時(shí)，散列表會(huì)先把key傳入散列（hash）函數(shù)中進(jìn)行尋址，得到的結(jié)果就是數(shù)組的下標(biāo)，然后再通過(guò)這個(gè)下標(biāo)訪問數(shù)組即可得到相關(guān)聯(lián)的值。
我們都知道數(shù)組中數(shù)據(jù)的組織方式是線性的，它會(huì)直接分配一串連續(xù)的內(nèi)存地址序列，要找到一個(gè)元素只需要根據(jù)下標(biāo)來(lái)計(jì)算地址的偏移量即可（查找一個(gè)元素的起始地址為：數(shù)組的起始地址加上下標(biāo)乘以該元素類型占用的地址大�。�。因此散列表在理想的情況下，各種操作的時(shí)間復(fù)雜度只有O(1)，這甚至超過(guò)了二叉查找樹，雖然理想的情況并不總是滿足的，關(guān)于這點(diǎn)之后我們還會(huì)提及。
為什么是hash？
hash算法是一種可以從任何數(shù)據(jù)中提取出其“指紋”的數(shù)據(jù)摘要算法，它將任意大小的數(shù)據(jù)（輸入）映射到一個(gè)固定大小的序列（輸出）上，這個(gè)序列被稱為hash code、數(shù)據(jù)摘要或者指紋。比較出名的hash算法有MD5、SHA。
hash是具有唯一性且不可逆的，唯一性指的是相同的輸入產(chǎn)生的hash code永遠(yuǎn)是一樣的，而不可逆也比較容易理解，數(shù)據(jù)摘要算法并不是壓縮算法，它只是生成了一個(gè)該數(shù)據(jù)的摘要，沒有將數(shù)據(jù)進(jìn)行壓縮。壓縮算法一般都是使用一種更節(jié)省空間的編碼規(guī)則將數(shù)據(jù)重新編碼，解壓縮只需要按著編碼規(guī)則解碼就是了，試想一下，一個(gè)幾百M(fèi)B甚至幾GB的數(shù)據(jù)生成的hash code都只是一個(gè)擁有固定長(zhǎng)度的序列，如果再能逆向解壓縮，那么其他壓縮算法該情何以堪？
我們上述討論的僅僅是在密碼學(xué)中的hash算法，而在散列表中所需要的散列函數(shù)是要能夠?qū)ey尋址到buckets中的一個(gè)位置，散列函數(shù)的實(shí)現(xiàn)影響到整個(gè)散列表的性能。
一個(gè)完美的散列函數(shù)要能夠做到均勻地將key分布到buckets中，每一個(gè)key分配到一個(gè)bucket，但這是不可能的。雖然hash算法具有唯一性，但同時(shí)它還具有重復(fù)性，唯一性保證了相同輸入的輸出是一致的，卻沒有保證不同輸入的輸出是不一致的，也就是說(shuō)，完全有可能兩個(gè)不同的key被分配到了同一個(gè)bucket（因?yàn)樗鼈兊膆ash code可能是相同的），這叫做碰撞沖突。總之，理想很豐滿，現(xiàn)實(shí)很骨感，散列函數(shù)只能盡可能地減少?zèng)_突，沒有辦法完全消除沖突。
散列函數(shù)的實(shí)現(xiàn)方法非常多，一個(gè)優(yōu)秀的散列函數(shù)要看它能不能將key分布均勻。首先介紹一種最簡(jiǎn)單的方法：除留余數(shù)法，先對(duì)key進(jìn)行hash得到它的hash code，然后再用該hash code對(duì)buckets數(shù)組的元素?cái)?shù)量取余，得到的結(jié)果就是bucket的下標(biāo)，這種方法簡(jiǎn)單高效，也可以當(dāng)做對(duì)集群進(jìn)行負(fù)載均衡的路由算法。
private int hash(Key key) {
// & 0x7fffffff 是為了屏蔽符號(hào)位，M為bucket數(shù)組的長(zhǎng)度
return (key.hashCode() & 0x7fffffff) % M;
}
要注意一點(diǎn)，只有整數(shù)才能進(jìn)行取余運(yùn)算，如果hash code是一個(gè)字符串或別的類型，那么你需要將它轉(zhuǎn)換為整數(shù)才能使用除留余數(shù)法，不過(guò)Java在Object對(duì)象中提供了hashCode()函數(shù)，該函數(shù)返回了一個(gè)int值，所以任何你想要放入HashMap的自定義的抽象數(shù)據(jù)類型，都必須實(shí)現(xiàn)該函數(shù)和equals()函數(shù)，這兩個(gè)函數(shù)之間也遵守著一種約定：如果a.equals(b) == true，那么a與b的hashCode()也必須是相同的。
下面為String類的hashCode()函數(shù)，它先遍歷了內(nèi)部的字符數(shù)組，然后在每一次循環(huán)中計(jì)算hash code（將hash code乘以一個(gè)素?cái)?shù)并加上當(dāng)前循環(huán)項(xiàng)的字符）：
/** The value is used for character storage. */
private final char value[];
/** Cache the hash code for the string */
private int hash; // Default to 0
public int hashCode() {
int h = hash;
if (h == 0 && value.length > 0) {
char val[] = value;
for (int i = 0; i < value.length; i++) {
h = 31 * h + val[i];
}
hash = h;
}
return h;
}
HashMap沒有采用這么簡(jiǎn)單的方法，有一個(gè)原因是HashMap中的buckets數(shù)組的長(zhǎng)度永遠(yuǎn)為一個(gè)2的冪，而不是一個(gè)素?cái)?shù)，如果長(zhǎng)度為素?cái)?shù)，那么可能會(huì)更適合簡(jiǎn)單暴力的除留余數(shù)法（當(dāng)然除留余數(shù)法雖然簡(jiǎn)單卻并不是那么高效的），順便一提，時(shí)代的眼淚Hashtable就使用了除留余數(shù)法，它沒有強(qiáng)制約束buckets數(shù)組的長(zhǎng)度。
HashMap在內(nèi)部實(shí)現(xiàn)了一個(gè)hash()函數(shù)，首先要對(duì)hashCode()的返回值進(jìn)行處理：
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
該函數(shù)將key.hashCode()的低16位和高16位做了個(gè)異或運(yùn)算，其目的是為了擾亂低位的信息以實(shí)現(xiàn)減少碰撞沖突。之后還需要把hash()的返回值與table.length - 1做與運(yùn)算（table為buckets數(shù)組），得到的結(jié)果即是數(shù)組的下標(biāo)。
table.length - 1就像是一個(gè)低位掩碼（這個(gè)設(shè)計(jì)也優(yōu)化了擴(kuò)容操作的性能），它和hash()做與操作時(shí)必然會(huì)將高位屏蔽（因?yàn)橐粋�(gè)HashMap不可能有特別大的buckets數(shù)組，至少在不斷自動(dòng)擴(kuò)容之前是不可能的，所以table.length - 1的大部分高位都為0），只保留低位，看似沒什么毛病，但這其實(shí)暗藏玄機(jī)，它會(huì)導(dǎo)致總是只有最低的幾位是有效的，這樣就算你的hashCode()實(shí)現(xiàn)得再好也難以避免發(fā)生碰撞。這時(shí)，hash()函數(shù)的價(jià)值就體現(xiàn)出來(lái)了，它對(duì)hash code的低位添加了隨機(jī)性并且混合了高位的部分特征，顯著減少了碰撞沖突的發(fā)生（關(guān)于hash()函數(shù)的效果如何，可以參考這篇文章An introduction to optimising a hashing strategy）。
HashMap的散列函數(shù)具體流程如下圖：
解決沖突
在上文中我們已經(jīng)多次提到碰撞沖突，但是散列函數(shù)不可能是完美的，key分布完全均勻的情況是不存在的，所以碰撞沖突總是難以避免。
那么發(fā)生碰撞沖突時(shí)怎么辦？總不能丟棄數(shù)據(jù)吧？必須要有一種合理的方法來(lái)解決這個(gè)問題，HashMap使用了叫做分離鏈接（Separate chaining，也有人翻譯成拉鏈法）的策略來(lái)解決沖突。它的主要思想是每個(gè)bucket都應(yīng)當(dāng)是一個(gè)互相獨(dú)立的數(shù)據(jù)結(jié)構(gòu)，當(dāng)發(fā)生沖突時(shí)，只需要把數(shù)據(jù)放入bucket中（因?yàn)閎ucket本身也是一個(gè)可以存放數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)），這樣查詢一個(gè)key所消耗的時(shí)間為訪問bucket所消耗的時(shí)間加上在bucket中查找的時(shí)間。
HashMap的buckets數(shù)組其實(shí)就是一個(gè)鏈表數(shù)組，在發(fā)生沖突時(shí)只需要把Entry（還記得Entry嗎？HashMap的Entry實(shí)現(xiàn)就是一個(gè)簡(jiǎn)單的鏈表節(jié)點(diǎn)，它包含了key和value以及hash code）放到鏈表的尾部，如果未發(fā)生沖突（位于該下標(biāo)的bucket為null），那么就把該Entry做為鏈表的頭部。而且HashMap還使用了Lazy策略，buckets數(shù)組只會(huì)在第一次調(diào)用put()函數(shù)時(shí)進(jìn)行初始化，這是一種防止內(nèi)存浪費(fèi)的做法，像ArrayList也是Lazy的，它在第一次調(diào)用add()時(shí)才會(huì)初始化內(nèi)部的數(shù)組。
不過(guò)鏈表雖然實(shí)現(xiàn)簡(jiǎn)單，但是在查找的效率上只有O(n)，而且我們大部分的操作都是在進(jìn)行查找，在hashCode()設(shè)計(jì)的不是非常良好的情況下，碰撞沖突可能會(huì)頻繁發(fā)生，鏈表也會(huì)變得越來(lái)越長(zhǎng)，這個(gè)效率是非常差的。Java 8對(duì)其實(shí)現(xiàn)了優(yōu)化，鏈表的節(jié)點(diǎn)數(shù)量在到達(dá)閾值時(shí)會(huì)轉(zhuǎn)化為紅黑樹，這樣查找所需的時(shí)間就只有O(log n)了，閾值的定義如下：
/** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8;
如果在插入Entry時(shí)發(fā)現(xiàn)一條鏈表超過(guò)閾值，就會(huì)執(zhí)行以下的操作，對(duì)該鏈表進(jìn)行樹化；相對(duì)的，如果在刪除Entry（或進(jìn)行擴(kuò)容）時(shí)發(fā)現(xiàn)紅黑樹的節(jié)點(diǎn)太少（根據(jù)閾值UNTREEIFY_THRESHOLD），也會(huì)把紅黑樹退化成鏈表。
/**
* 替換指定hash所處位置的鏈表中的所有節(jié)點(diǎn)為TreeNode，
* 如果buckets數(shù)組太小，就進(jìn)行擴(kuò)容。
*/
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY = 64，小于該值代表數(shù)組中的節(jié)點(diǎn)并不是很多
// 所以選擇進(jìn)行擴(kuò)容，只有數(shù)組長(zhǎng)度大于該值時(shí)才會(huì)進(jìn)行樹化。
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
else if ((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 轉(zhuǎn)換鏈表節(jié)點(diǎn)為樹節(jié)點(diǎn)，注意要處理好連接關(guān)系
do {
TreeNode<K,V> p = replacementTreeNode(e, null);
if (tl == null)
hd = p;
else {
p.prev = tl;
tl.next = p;
}
tl = p;
} while ((e = e.next) != null);
if ((tab[index] = hd) != null)
hd.treeify(tab); // 從頭部開始構(gòu)造樹
}
}
// 該函數(shù)定義在TreeNode中
final void treeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for (TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if (root == null) { // 初始化root節(jié)點(diǎn)
x.parent = null;
x.red = false;
root = x;
}
else {
K k = x.key;
int h = x.hash;
Class<?> kc = null;
for (TreeNode<K,V> p = root;;) {
int dir, ph;
K pk = p.key;
// 確定節(jié)點(diǎn)的方向
if ((ph = p.hash) > h)
dir = -1;
else if (ph < h)
dir = 1;
// 如果kc == null
// 并且k沒有實(shí)現(xiàn)Comparable接口
// 或者k與pk是沒有可比較性的（類型不同）
// 或者k與pk是相等的（返回0也有可能是相等）
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 確定方向后插入節(jié)點(diǎn)，修正紅黑樹的平衡
TreeNode<K,V> xp = p;
if ((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if (dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
// 確保給定的root是該bucket中的第一個(gè)節(jié)點(diǎn)
moveRootToFront(tab, root);
}
static int tieBreakOrder(Object a, Object b) {
int d;
if (a == null || b == null ||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
// System.identityHashCode()將調(diào)用并返回傳入對(duì)象的默認(rèn)hashCode()
// 也就是說(shuō)，無(wú)論是否重寫了hashCode()，都將調(diào)用Object.hashCode()。
// 如果傳入的對(duì)象是null，那么就返回0
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1 : 1);
return d;
}
解決碰撞沖突的另一種策略叫做開放尋址法（Open addressing），它與分離鏈接法的思想截然不同。在開放尋址法中，所有Entry都會(huì)存儲(chǔ)在buckets數(shù)組，一個(gè)明顯的區(qū)別是，分離鏈接法中的每個(gè)bucket都是一個(gè)鏈表或其他的數(shù)據(jù)結(jié)構(gòu)，而開放尋址法中的每個(gè)bucket就僅僅只是Entry本身。
開放尋址法是基于數(shù)組中的空位來(lái)解決沖突的，它的想法很簡(jiǎn)單，與其使用鏈表等數(shù)據(jù)結(jié)構(gòu)，不如直接在數(shù)組中留出空位來(lái)當(dāng)做一個(gè)標(biāo)記，反正都要占用額外的內(nèi)存。
當(dāng)你查找一個(gè)key的時(shí)候，首先會(huì)從起始位置（通過(guò)散列函數(shù)計(jì)算出的數(shù)組索引）開始，不斷檢查當(dāng)前bucket是否為目標(biāo)Entry（通過(guò)比較key來(lái)判斷），如果當(dāng)前bucket不是目標(biāo)Entry，那么就向后查找（查找的間隔取決于實(shí)現(xiàn)），直到碰見一個(gè)空位（null），這代表你想要找的key不存在。
如果你想要put一個(gè)全新的Entry（Map中沒有這個(gè)key存在），依然會(huì)從起始位置開始進(jìn)行查找，如果起始位置不是空的，則代表發(fā)生了碰撞沖突，只好不斷向后查找，直到發(fā)現(xiàn)一個(gè)空位。
開放尋址法的名字也是來(lái)源于此，一個(gè)Entry的位置并不是完全由hash值決定的，所以也叫做Closed hashing，相對(duì)的，分離鏈接法也被稱為Open hashing或Closed addressing。
根據(jù)向后探測(cè)（查找）的算法不同，開放尋址法有多種不同的實(shí)現(xiàn)，我們介紹一種最簡(jiǎn)單的算法：線性探測(cè)法（Linear probing），在發(fā)生碰撞時(shí)，簡(jiǎn)單地將索引加一，如果到達(dá)了數(shù)組的尾部就折回到數(shù)組的頭部，直到找到目標(biāo)或一個(gè)空位。
基于線性探測(cè)法的查找操作如下：
private K[] keys; // 存儲(chǔ)key的數(shù)組
private V[] vals; // 存儲(chǔ)值的數(shù)組
public V get(K key) {
// m是buckets數(shù)組的長(zhǎng)度，即keys和vals的長(zhǎng)度。
// 當(dāng)i等于m時(shí)，取模運(yùn)算會(huì)得0（折回?cái)?shù)組頭部）
for (int i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key))
return vals[i];
}
return null;
}
插入操作稍微麻煩一些，需要在插入之前判斷當(dāng)前數(shù)組的剩余容量，然后決定是否擴(kuò)容。數(shù)組的剩余容量越多，代表Entry之間的間隔越大以及越早碰見空位（向后探測(cè)的次數(shù)就越少），效率自然就會(huì)變高。代價(jià)就是額外消耗的內(nèi)存較多，這也是在用空間換取時(shí)間。
public void put(K key, V value) {
// n是Entry的數(shù)量，如果n超過(guò)了數(shù)組長(zhǎng)度的一半，就擴(kuò)容一倍
if (n >= m / 2) resize(2 * m);
int i;
for (i = hash(key); keys[i] != null; i = (i + 1) % m) {
if (keys[i].equals(key)) {
vals[i] = value;
return;
}
}
// 沒有找到目標(biāo)，那么就插入一對(duì)新的Entry
keys[i] = key;
vals[i] = value;
n++;
}
接下來(lái)是刪除操作，需要注意一點(diǎn)，我們不能簡(jiǎn)單地把目標(biāo)key所在的位置（keys和vals數(shù)組）設(shè)置為null，這樣會(huì)導(dǎo)致此位置之后的Entry無(wú)法被探測(cè)到，所以需要將目標(biāo)右側(cè)的所有Entry重新插入到散列表中：
public V delete(K key) {
int i = hash(key);
// 先找到目標(biāo)的索引
while (!key.equals(keys[i])) {
i = (i + 1) % m;
}
V oldValue = vals[i];
// 刪除目標(biāo)key和value
keys[i] = null;
vals[i] = null;
// 指針移動(dòng)到下一個(gè)索引
i = (i + 1) % m;
while (keys[i] != null) {
// 先刪除然后重新插入
K keyToRehash = keys[i];
V valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
n--;
// 當(dāng)前Entry小于等于數(shù)組長(zhǎng)度的八分之一時(shí)，進(jìn)行縮容
if (n > 0 && n <= m / 8) resize(m / 2);
return oldValue;
}
動(dòng)態(tài)擴(kuò)容
散列表以數(shù)組的形式組織bucket，問題在于數(shù)組是靜態(tài)分配的，為了保證查找的性能，需要在Entry數(shù)量大于一個(gè)臨界值時(shí)進(jìn)行擴(kuò)容，否則就算散列函數(shù)的效果再好，也難免產(chǎn)生碰撞。
所謂擴(kuò)容，其實(shí)就是用一個(gè)容量更大（在原容量上乘以二）的數(shù)組來(lái)替換掉當(dāng)前的數(shù)組，這個(gè)過(guò)程需要把舊數(shù)組中的數(shù)據(jù)重新hash到新數(shù)組，所以擴(kuò)容也能在一定程度上減緩碰撞。
HashMap通過(guò)負(fù)載因子（Load Factor）乘以buckets數(shù)組的長(zhǎng)度來(lái)計(jì)算出臨界值，算法：threshold = load_factor * capacity。比如，HashMap的默認(rèn)初始容量為16（capacity = 16），默認(rèn)負(fù)載因子為0.75（load_factor = 0.75），那么臨界值就為threshold = 0.75 * 16 = 12，只要Entry的數(shù)量大于12，就會(huì)觸發(fā)擴(kuò)容操作。
還可以通過(guò)下列的構(gòu)造函數(shù)來(lái)自定義負(fù)載因子，負(fù)載因子越小查找的性能就會(huì)越高，但同時(shí)額外占用的內(nèi)存就會(huì)越多，如果沒有特殊需要不建議修改默認(rèn)值。
/**
* 可以發(fā)現(xiàn)構(gòu)造函數(shù)中根本就沒初始化buckets數(shù)組。
* （之前說(shuō)過(guò)buckets數(shù)組會(huì)推遲到第一次調(diào)用put()時(shí)進(jìn)行初始化）
*/
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor()確保initialCapacity必須為一個(gè)2的N次方
this.threshold = tableSizeFor(initialCapacity);
}
buckets數(shù)組的大小約束對(duì)于整個(gè)HashMap都至關(guān)重要，為了防止傳入一個(gè)不是2次冪的整數(shù)，必須要有所防范。tableSizeFor()函數(shù)會(huì)嘗試修正一個(gè)整數(shù)，并轉(zhuǎn)換為離該整數(shù)最近的2次冪。
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) {
int n = cap - 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;
}
還記得數(shù)組索引的計(jì)算方法嗎？index = (table.length - 1) & hash，這其實(shí)是一種優(yōu)化手段，由于數(shù)組的大小永遠(yuǎn)是一個(gè)2次冪，在擴(kuò)容之后，一個(gè)元素的新索引要么是在原位置，要么就是在原位置加上擴(kuò)容前的容量。這個(gè)方法的巧妙之處全在于&運(yùn)算，之前提到過(guò)&運(yùn)算只會(huì)關(guān)注n – 1（n = 數(shù)組長(zhǎng)度）的有效位，當(dāng)擴(kuò)容之后，n的有效位相比之前會(huì)多增加一位（n會(huì)變成之前的二倍，所以確保數(shù)組長(zhǎng)度永遠(yuǎn)是2次冪很重要），然后只需要判斷hash在新增的有效位的位置是0還是1就可以算出新的索引位置，如果是0，那么索引沒有發(fā)生變化，如果是1，索引就為原索引加上擴(kuò)容前的容量。
這樣在每次擴(kuò)容時(shí)都不用重新計(jì)算hash，省去了不少時(shí)間，而且新增有效位是0還是1是帶有隨機(jī)性的，之前兩個(gè)碰撞的Entry又有可能在擴(kuò)容時(shí)再次均勻地散布開。下面是resize()的源碼：
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table就是buckets數(shù)組
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// oldCap大于0，進(jìn)行擴(kuò)容，設(shè)置閾值與新的容量
if (oldCap > 0) {
// 超過(guò)最大值不會(huì)進(jìn)行擴(kuò)容，并且把閾值設(shè)置成Interger.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 沒超過(guò)最大值，擴(kuò)容為原來(lái)的2倍
// 向左移1位等價(jià)于乘2
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// oldCap = 0，oldThr大于0，那么就把閾值做為新容量以進(jìn)行初始化
// 這種情況發(fā)生在用戶調(diào)用了帶有參數(shù)的構(gòu)造函數(shù)（會(huì)對(duì)threshold進(jìn)行初始化）
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap與oldThr都為0，這種情況發(fā)生在用戶調(diào)用了無(wú)參構(gòu)造函數(shù)
// 采用默認(rèn)值進(jìn)行初始化
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr還沒有被賦值，那么就根據(jù)newCap計(jì)算出閾值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 如果oldTab != null，代表這是擴(kuò)容操作
// 需要將擴(kuò)容前的數(shù)組數(shù)據(jù)遷移到新數(shù)組
if (oldTab != null) {
// 遍歷oldTab的每一個(gè)bucket，然后移動(dòng)到newTab
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
// 索引j的bucket只有一個(gè)Entry（未發(fā)生過(guò)碰撞）
// 直接移動(dòng)到newTab
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是一個(gè)樹節(jié)點(diǎn)（代表已經(jīng)轉(zhuǎn)換成紅黑樹了）
// 那么就將這個(gè)節(jié)點(diǎn)拆分為lower和upper兩棵樹
// 首先會(huì)對(duì)這個(gè)節(jié)點(diǎn)進(jìn)行遍歷
// 只要當(dāng)前節(jié)點(diǎn)的hash & oldCap == 0就鏈接到lower樹
// 注意這里是與oldCap進(jìn)行與運(yùn)算，而不是oldCap - 1(n - 1)
// oldCap就是擴(kuò)容后新增有效位的掩碼
// 比如oldCap=16，二進(jìn)制10000，n-1 = 1111，擴(kuò)容后的n-1 = 11111
// 只要hash & oldCap == 0，就代表hash的新增有效位為0
// 否則就鏈接到upper樹（新增有效位為1）
// lower會(huì)被放入newTab[原索引j]，upper樹會(huì)被放到newTab[原索引j + oldCap]
// 如果lower或者upper樹的節(jié)點(diǎn)少于閾值，會(huì)被退化成鏈表
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 下面操作的邏輯與分裂樹節(jié)點(diǎn)基本一致
// 只不過(guò)split()操作的是TreeNode
// 而且會(huì)將兩條TreeNode鏈表組織成紅黑樹
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
使用HashMap時(shí)還需要注意一點(diǎn)，它不會(huì)動(dòng)態(tài)地進(jìn)行縮容，也就是說(shuō)，你不應(yīng)該保留一個(gè)已經(jīng)刪除過(guò)大量Entry的HashMap（如果不打算繼續(xù)添加元素的話），此時(shí)它的buckets數(shù)組經(jīng)過(guò)多次擴(kuò)容已經(jīng)變得非常大了，這會(huì)占用非常多的無(wú)用內(nèi)存，這樣做的好處是不用多次對(duì)數(shù)組進(jìn)行擴(kuò)容或縮容操作。不過(guò)一般也不會(huì)出現(xiàn)這種情況，如果遇見了，請(qǐng)毫不猶豫地丟掉它，或者把數(shù)據(jù)轉(zhuǎn)移到一個(gè)新的HashMap。
添加元素
我們已經(jīng)了解了HashMap的內(nèi)部實(shí)現(xiàn)與工作原理，它在內(nèi)部維護(hù)了一個(gè)數(shù)組，每一個(gè)key都會(huì)經(jīng)過(guò)散列函數(shù)得出在數(shù)組的索引，如果兩個(gè)key的索引相同，那么就使用分離鏈接法解決碰撞沖突，當(dāng)Entry的數(shù)量大于臨界值時(shí)，對(duì)數(shù)組進(jìn)行擴(kuò)容。
接下來(lái)以一個(gè)添加元素（put()）的過(guò)程為例來(lái)梳理一下知識(shí)，下圖是put()函數(shù)的流程圖：
然后是源碼：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
// table == null or table.length == 0
// 第一次調(diào)用put()，初始化table
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
// 沒有發(fā)生碰撞，直接放入到數(shù)組
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
// 發(fā)生碰撞（頭節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn)）
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 節(jié)點(diǎn)為紅黑樹
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 節(jié)點(diǎn)為鏈表
else {
for (int binCount = 0; ; ++binCount) {
// 未找到目標(biāo)節(jié)點(diǎn)，在鏈表尾部鏈接新節(jié)點(diǎn)
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 鏈表過(guò)長(zhǎng)，轉(zhuǎn)換為紅黑樹
treeifyBin(tab, hash);
break;
}
// 找到目標(biāo)節(jié)點(diǎn)，退出循環(huán)
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 節(jié)點(diǎn)已存在，替換value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeXXXXX是提供給LinkedHashMap重寫的函數(shù)
// 在HashMap中沒有意義
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
// 超過(guò)臨界值，進(jìn)行擴(kuò)容
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
標(biāo)簽：
版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。
