一、HashCode為什么使用31作為乘數(shù)

1、選擇數(shù)字31是因?yàn)樗且粋€(gè)奇質(zhì)數(shù)，如果選擇一個(gè)偶數(shù)會(huì)在乘法運(yùn)算中產(chǎn)生溢出，導(dǎo)致數(shù)值信息丟失，因?yàn)槌硕喈?dāng)于移位運(yùn)算。選擇質(zhì)數(shù)的優(yōu)勢(shì)并不是特別的明顯，但這是一個(gè)傳統(tǒng)。

2、數(shù)字31有一個(gè)很好的特性，即乘法運(yùn)算可以被移位和減法運(yùn)算取代，來獲取更好的性能：31 * i == (i << 5) - i，現(xiàn)代的 Java 虛擬機(jī)可以自動(dòng)地完成這個(gè)優(yōu)化。

二、數(shù)組與鏈表的特點(diǎn)

數(shù)組的特點(diǎn)是：尋址容易，插入和刪除困難。

鏈表的特點(diǎn)是：尋址困難，插入和刪除容易。

三、HashMap原理

• 允許null健及null值，null健，值為0。
• HashMap 不保證鍵值對(duì)的順序，操作時(shí)，鍵值對(duì)的順序會(huì)發(fā)生變化。
• HashMap是非線程安全類，在多線程環(huán)境下會(huì)發(fā)生問題。
• HashMap是JDK 1.2時(shí)推出的，底層基于散列算法實(shí)現(xiàn)。
• 在JDK 1.8中涉及比較多：1、散列表實(shí)現(xiàn)、2、擾動(dòng)函數(shù)、3、初始化容量、4、負(fù)載因子、5、擴(kuò)容元素拆分、6、鏈表樹化、7、紅黑樹、8、插入、9、查找、10、刪除、11、遍歷、12、分段鎖等。

(1) 擾動(dòng)函數(shù)

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

擾動(dòng)函數(shù)就是為了增加隨機(jī)性，讓數(shù)據(jù)元素更加均衡地散列，減少碰撞。

(2) 負(fù)載因子

static final float DEFAULT_LOAD_FACTOR = 0.75f;

負(fù)載因子，可以理解成一輛車可承重重量超過某個(gè)閥值時(shí)，把貨放到新的車上。在 HashMap 中，負(fù)載因子決定了數(shù)據(jù)量多少了以后進(jìn)行擴(kuò)容。

0.75 是一個(gè)默認(rèn)構(gòu)造值，在創(chuàng)建 HashMap 也可以調(diào)整，如何希望用更多的空間換取時(shí)間，可以把負(fù)載因子調(diào)得更小一些，減少碰撞。

(3) 擴(kuò)容元素拆分

擴(kuò)容最直接的問題，就是需要把元素拆分到新的數(shù)組中，在JDK1.7中，會(huì)重新計(jì)算哈希值，但在JDK1.8后，進(jìn)行了優(yōu)化。

1. 擴(kuò)容時(shí)計(jì)算出新的newCap、newThr，這是兩個(gè)單詞的縮寫，一個(gè)是Capacity ，另一個(gè)是閥Threshold。
2. newCap用于創(chuàng)新的數(shù)組桶 new Node[newCap]。
3. 隨著擴(kuò)容后，原來那些因?yàn)楣Ｅ鲎?，存放成鏈表和紅黑樹的元素，都需要進(jìn)行拆分存放到新的位置中。

(4) 數(shù)據(jù)遷移

(5) 數(shù)據(jù)插入

1. 首先進(jìn)行哈希值的擾動(dòng)，獲取一個(gè)新的哈希值。(key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)。
2. 判斷tab是否為空或者長度為0，如果是則進(jìn)行擴(kuò)容操作。
3. if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length。
4. 根據(jù)哈希值計(jì)算下標(biāo)，如果對(duì)應(yīng)小標(biāo)正好沒有存放數(shù)據(jù)，則直接插入即可否則需要覆蓋。tab[i = (n - 1) & hash])。
5. 判斷tab[i]是否為樹節(jié)點(diǎn)，否則向鏈表中插入數(shù)據(jù)，否則向樹中插入節(jié)點(diǎn)。
6. 如果鏈表中插入節(jié)點(diǎn)的時(shí)候，鏈表長度大于等于8，則需要把鏈表轉(zhuǎn)換為紅黑樹。treeifyBin(tab, hash)。
7. 最后所有元素處理完成后，判斷是否超過閾值;threshold，超過則擴(kuò)容。
8. treeifyBin,是一個(gè)鏈表轉(zhuǎn)樹的方法，但不是所有的鏈表長度為8后都會(huì)轉(zhuǎn)成樹，還需要判斷存放key值的數(shù)組桶長度是否小于64 MIN_TREEIFY_CAPACITY。如果小于則需要擴(kuò)容，擴(kuò)容后鏈表上的數(shù)據(jù)會(huì)被拆分散列的相應(yīng)的桶節(jié)點(diǎn)上，也就把鏈表長度縮短了。

(6) 鏈表樹化

1. 鏈表樹化的條件有兩點(diǎn);鏈表長度大于等于8、桶容量大于64，否則只是擴(kuò)容，不會(huì)樹化。
2. 鏈表樹化的過程中是先由鏈表轉(zhuǎn)換為樹節(jié)點(diǎn)，此時(shí)的樹可能不是一顆平衡樹。同時(shí)在樹轉(zhuǎn)換過程中會(huì)記錄鏈表的順序，tl.next = p，這主要方便后續(xù)樹轉(zhuǎn)鏈表和拆分更方便。
3. 鏈表轉(zhuǎn)換成樹完成后，再進(jìn)行紅黑樹的轉(zhuǎn)換。先簡單介紹下，紅黑樹的轉(zhuǎn)換需要染色和旋轉(zhuǎn)，以及比對(duì)大小。在比較元素的大小中，有一個(gè)比較有意思的方法，tieBreakOrder加時(shí)賽，這主要是因?yàn)镠ashMap沒有像TreeMap那樣本身就有Comparator的實(shí)現(xiàn)。

(7) 紅黑樹轉(zhuǎn)鏈

在轉(zhuǎn)換樹的過程中，記錄了原有鏈表的順序，紅黑樹轉(zhuǎn)鏈表時(shí)候，直接把TreeNode轉(zhuǎn)換為Node，因?yàn)橛涗浟随湵黻P(guān)系，所以替換過程很容易。

(8) 查找

1. 擾動(dòng)函數(shù)的使用，獲取新的哈希值。
2. 下標(biāo)的計(jì)算， tab[(n - 1) & hash])。
3. 確定了桶數(shù)組下標(biāo)位置，接下來就是對(duì)紅黑樹和鏈表進(jìn)行查找和遍歷操作了。

(9) 刪除

1. 刪除的操作也比較簡單，沒有太多的復(fù)雜的邏輯。
2. 另外紅黑樹的操作因?yàn)楸话b了，只看使用上也是很容易。

(10) 遍歷

1. 這里我們要設(shè)定一個(gè)既有紅黑樹又有鏈表結(jié)構(gòu)的數(shù)據(jù)場景
2. 為了可以有這樣的數(shù)據(jù)結(jié)構(gòu)，我們最好把 HashMap 初始長度設(shè)定為 64，避免在

鏈表超過 8 位后擴(kuò)容，而是直接讓其轉(zhuǎn)換為紅黑樹。

1. 找到 18 個(gè)元素，分別放在不同節(jié)點(diǎn)(這些數(shù)據(jù)通過程序計(jì)算得來)。
2. 桶數(shù)組 02 節(jié)點(diǎn)：24、46、68。
3. 桶數(shù)組 07 節(jié)點(diǎn)：29。
4. 桶數(shù)組 12 節(jié)點(diǎn)：150、172、194、271、293、370、392、491、590。

測(cè)試代碼

public void test_Iterator() {
    Map<String, String> map = new HashMap<String, String>(64);
    map.put("24", "Idx：2");
    map.put("46", "Idx：2");
    map.put("68", "Idx：2");
    map.put("29", "Idx：7");
    map.put("150", "Idx：12");
    map.put("172", "Idx：12");
    map.put("194", "Idx：12");
    map.put("271", "Idx：12");
    System.out.println("排序01：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }
    map.put("293", "Idx：12");
    map.put("370", "Idx：12");
    map.put("392", "Idx：12");
    map.put("491", "Idx：12");
    map.put("590", "Idx：12");
    System.out.println("\n\n排序02：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }    
    map.remove("293");
    map.remove("370");
    map.remove("392");
    map.remove("491");
    map.remove("590");
    System.out.println("\n\n排序03：");
    for (String key : map.keySet()) {
        System.out.print(key + " ");
    }
}

1. 添加元素，在 HashMap 還是只鏈表結(jié)構(gòu)時(shí)，輸出測(cè)試結(jié)果 01。
2. 添加元素，在 HashMap 轉(zhuǎn)換為紅黑樹的時(shí)候，輸出測(cè)試結(jié)果 02。
3. 刪除元素，在 HashMap 轉(zhuǎn)換為鏈表結(jié)構(gòu)時(shí)，輸出測(cè)試結(jié)果 03。

結(jié)果如下：

排序01：
24 46 68 29 150 172 194 271 
排序02：
24 46 68 29 271 150 172 194 293 370 392 491 590 
排序03：
24 46 68 29 172 271 150 194 
Process finished with exit code 0

這一篇 API 源碼以及邏輯與上一篇數(shù)據(jù)結(jié)構(gòu)中擾動(dòng)函數(shù)、負(fù)載因子、散列表實(shí)現(xiàn)等，內(nèi)容的結(jié)合，算是把 HashMap 基本常用技術(shù)點(diǎn)，梳理完成了。但知識(shí)絕不止于此，這里還有紅黑樹的相關(guān)技術(shù)內(nèi)容，后續(xù)會(huì)進(jìn)行詳細(xì)。

除了 HashMap 以外還有 TreeMap、ConcurrentHashMap 等，每一個(gè)核心類都有一與之相關(guān)的核心知識(shí)點(diǎn)，每一個(gè)都非常值得深入研究。這個(gè)燒腦的過程，是學(xué)習(xí)獲得的知識(shí)的最佳方式。