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