說(shuō)到HashMap繁成，絕大多數(shù)Java程序員并不默認(rèn)吓笙，在沒(méi)有研究它之前，我們嚴(yán)重的HashMap多是這樣的：

Map<String, String> map = new HashMap<>()
map.put(key, value);
map.get(key);
map.putAll(List<Map>)
…… 

然而在面試官眼里巾腕，可大不一樣面睛，它可以對(duì)數(shù)組、鏈表祠墅、位運(yùn)算侮穿、線程安全等一系列Java基礎(chǔ)的集合。很多時(shí)候毁嗦，HashMap是Java面試?yán)@不過(guò)去的點(diǎn)亲茅。以上的知識(shí)點(diǎn)，我們可以在學(xué)習(xí)HashMap原理和源碼的過(guò)程中掌握和消化狗准。本文試圖詳盡的描述作者對(duì)HashMap的理解克锣，力求條理清晰。

• 哈希是誰(shuí)
• Map為啥扯上Hash
• HashMap的創(chuàng)建及put方法（結(jié)合源碼）
• HashMap的get方法（結(jié)合源碼）

哈希是誰(shuí)

哈希在這里指的是哈希函數(shù)腔长，簡(jiǎn)單來(lái)說(shuō)袭祟，哈希算法會(huì)接收任意輸入對(duì)象，將其轉(zhuǎn)換成定長(zhǎng)的整型數(shù)字輸出捞附。一個(gè)好的哈希函數(shù)會(huì)有兩個(gè)特點(diǎn)：一是同一性巾乳，也就是說(shuō)由于任意輸入經(jīng)過(guò)fun后都是定長(zhǎng)輸出您没，輸出是固定長(zhǎng)度，就意味著這個(gè)函數(shù)輸出的最大值是確定的胆绊，那么哈希函數(shù)需要力爭(zhēng)讓任何輸入都能均勻的散落到輸出區(qū)間上氨鹏，以免過(guò)多的輸入映射到同一個(gè)輸出上；第二點(diǎn)是雪崩效應(yīng)压状，它表示當(dāng)輸入變化一點(diǎn)仆抵，輸出就產(chǎn)生很大的變化，其目的也是希望減少碰撞种冬。本文不會(huì)涉及具體的哈希算法镣丑，我們也不需要糾結(jié)在這一點(diǎn)上，把握住哈希算法的含義和特點(diǎn)即可娱两。

Map為啥扯上Hash

我們知道Map是一種鍵值對(duì)形式的數(shù)據(jù)結(jié)構(gòu)莺匠，那為啥Java要把Map和Hash算法結(jié)合起來(lái)呢？
其實(shí)即便我們將Map在內(nèi)存中用數(shù)組或鏈表的形式存儲(chǔ)也是可以的谷婆，試想每一個(gè)存儲(chǔ)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)如下：

//數(shù)組node
Node<K, V> {
  K key;
  V value;
}  

//鏈表node
Node<K, V> {
  K key;
  V value;
  Node<K, V> next;
}

它當(dāng)然可以存儲(chǔ)Map要表達(dá)的數(shù)據(jù)慨蛙，但是對(duì)于數(shù)組而言，我們知道它在內(nèi)存中是連續(xù)的纪挎，這意味著期贫，數(shù)組在查詢時(shí)有天然的優(yōu)勢(shì)，因?yàn)橹莱跏嫉刂泛蚷ndex就可以很快鎖定讀取位置异袄。但正是由于連續(xù)的內(nèi)存地址通砍，導(dǎo)致在做刪除和插入操作時(shí)，數(shù)組需要不斷調(diào)整操作節(jié)點(diǎn)后續(xù)的位置烤蜕，導(dǎo)致效率低下封孙；那鏈表呢，鏈表的內(nèi)存地址是不連續(xù)的讽营，每一個(gè)節(jié)點(diǎn)都記錄著下一節(jié)點(diǎn)的內(nèi)存地址虎忌，所以如果做查詢操作，我們需要挨個(gè)訪問(wèn)興趣節(jié)點(diǎn)之前的所有節(jié)點(diǎn)橱鹏，才能找到它膜蠢，此時(shí)效率是低下的，對(duì)于刪除和新增來(lái)講會(huì)比數(shù)組靈活莉兰，因?yàn)橹恍枰膭?dòng)附近節(jié)點(diǎn)的next指針即可挑围，其它節(jié)點(diǎn)不受影響。所以一個(gè)是新增刪除效率低下（數(shù)組）糖荒，一個(gè)是讀取效率低下（鏈表）杉辙。人們就試圖將二者結(jié)合，做到優(yōu)勢(shì)互補(bǔ)捶朵，這就是下一個(gè)話題——哈希表
哈希表在內(nèi)存中的直觀表現(xiàn)如下：

哈希表

• 在插入的時(shí)候硼端，輸入對(duì)象先通過(guò)特定哈希函數(shù)計(jì)算并淋，其輸出會(huì)落在左邊數(shù)組的index里面（不會(huì)超過(guò)array.length），如果該數(shù)組元素沒(méi)有指向任何Node珍昨，則直接將插入的值生成Node掛在對(duì)應(yīng)數(shù)組元素之后，如圖array[8]所示句喷；如果該數(shù)組元素后面已經(jīng)掛有鏈表存在镣典，則我們將遍歷這個(gè)鏈表，確定鏈表中沒(méi)有相同的key后唾琼，掛在鏈表的最后兄春，也就是數(shù)組 --> 原鏈表 --> 新Node。
• 在讀取的時(shí)候锡溯，讀取的時(shí)候也是先根據(jù)key值計(jì)算哈希函數(shù)結(jié)構(gòu)赶舆，找對(duì)應(yīng)的array index，找到后根據(jù)key遍歷對(duì)應(yīng)的鏈表祭饭。
• 刪除的過(guò)程參照讀取芜茵。
  這樣一來(lái)無(wú)論是讀寫還是刪除都可以很快的縮小范圍，降低時(shí)間復(fù)雜度倡蝙。最理想的情況是所有輸入的hash值都散落在數(shù)組index范圍內(nèi)九串，這樣每個(gè)數(shù)據(jù)元素后面都只指向一個(gè)鏈表節(jié)點(diǎn)。當(dāng)然最壞的情況是所有hash值都落在某一個(gè)array節(jié)點(diǎn)上寺鸥，這就是所謂的哈希碰撞猪钮，或者叫做違反“同一性”原則，這樣的哈希函數(shù)需要改進(jìn)胆建。

HashMap的創(chuàng)建及put方法（結(jié)合源碼）

接下來(lái)我們需要閱讀源碼烤低，看一下HashMap真實(shí)的樣子，在此之前笆载，我將需要理解的專有概念梳理出來(lái)扑馁，方便查閱。
capacity：指代哈希表中數(shù)組的容量宰译；
load factor：它是一個(gè)(0,1)的float檐蚜，作為一個(gè)系數(shù)，用來(lái)計(jì)算當(dāng)前array的閾值沿侈。打個(gè)比方闯第，capacity是8，load factory是0.75缀拭，當(dāng)哈希表的數(shù)組部分落入hash值到達(dá)8*0.75=6個(gè)時(shí)咳短，哈希表會(huì)根據(jù)一定規(guī)則進(jìn)行擴(kuò)容填帽；

Threshold.png

1. 初始化：

Map<String, String> map = new HashMap<>()
HashMap對(duì)外暴露了4個(gè)構(gòu)造函數(shù)篡腌，三個(gè)帶參，一個(gè)無(wú)參勾效，我們常用是無(wú)參構(gòu)造函數(shù)：

    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
    }

很簡(jiǎn)單構(gòu)造函數(shù)僅僅初始化了loadFactor=0.75f嘹悼，在后面有一個(gè)注釋：其它成員采用默認(rèn)設(shè)置。那我們就來(lái)看看有哪些重要的成員层宫。

• table

transient Node<K,V>[] table;

哈希表的數(shù)組部分杨伙，可以看到每個(gè)元素都是一個(gè)Node節(jié)點(diǎn)，Node是HashMap的內(nèi)部類萌腿，成員包括Key限匣，Value，hash毁菱，和下一個(gè)Node的引用：

    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ……

• size

transient int size;

記錄key-value個(gè)數(shù)

• modCount

transient int modCount;

記錄HashMap的操作數(shù)米死，比如每次執(zhí)行put、get贮庞、remove等操作峦筒，modCount都會(huì)加1。

• threshold

int threshold;

如上面所說(shuō)贸伐，代表的是閾值 threshold = capacity * loadFactor勘天。

• loadFactor

final float loadFactor;

加載因子，上文已詳細(xì)說(shuō)明捉邢，不贅述脯丝。

2. 寫入

map.put(key, value);
我們看到HashMap的put方法其實(shí)是對(duì)putVal方法的直接調(diào)用，沒(méi)有其它多余的東西伏伐，那我們來(lái)好好研究一下putVal方法宠进，先看一下方法的聲明：

    /**
     * Implements Map.put and related methods
     *
     * @param hash hash for key
     * @param key the key
     * @param value the value to put
     * @param onlyIfAbsent if true, don't change existing value
     * @param evict if false, the table is in creation mode.
     * @return previous value, or null if none
     */
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) 

前三個(gè)參數(shù)很好理解，hash（根據(jù)key值計(jì)算出來(lái)的hash值）藐翎，傳入的key和value材蹬。后兩個(gè)參數(shù)在put方法調(diào)用的時(shí)候直接設(shè)置成onlyIfAbsent = false，evict=true吝镣。后者暫時(shí)不用關(guān)注堤器，onlyIfAbsent的意思是如果如果key值已經(jīng)存在是否要替換傳入的value，設(shè)置為false代表如果key存在則覆蓋其value末贾；true是指如果key存在則傳入的value不會(huì)被寫入闸溃。
所有傳參都很清晰，有一點(diǎn)！int hash是怎么來(lái)的辉川，當(dāng)然是通過(guò)hash函數(shù)計(jì)算而來(lái)表蝙，但是我們有必要看一下這個(gè)過(guò)程。put方法在調(diào)用putVal時(shí)傳參如下：

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

hash(key)是什么怪物乓旗？進(jìn)去看一下：

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

到這里我們終于看到跟哈希有實(shí)質(zhì)性關(guān)系的地方了府蛇，如果key值為null，那么返回的hash值為0屿愚，這里先得出一個(gè)結(jié)論：HashMap的key可以為null汇跨，而且對(duì)于這類數(shù)據(jù)，HashMap存放在index=0的位置妆距！要強(qiáng)調(diào)的是扰法，hash值為0并不是index為0的直接原因，后面會(huì)提到毅厚，HashMap對(duì)得到的hash值做了位與操作，這個(gè)位與的結(jié)果就是index浦箱，自然任何值與0位與結(jié)果為0吸耿。對(duì)于非空key，返回值的計(jì)算方式則是先進(jìn)行hashCode計(jì)算酷窥，其結(jié)果的高位和低位做了異或咽安。其中hashCode方法是一個(gè)native方法：

    public native int hashCode();

它的具體實(shí)現(xiàn)跟JVM有關(guān)，要注意的一點(diǎn)是蓬推，對(duì)于同一個(gè)對(duì)象進(jìn)行hashCode妆棒，在同一個(gè)Java應(yīng)用執(zhí)行階段，無(wú)論調(diào)用多少次沸伏，都會(huì)返回相同的int數(shù)糕珊。當(dāng)然如果不同版本的JVM或者再一次啟動(dòng)某Java程序，返回的int數(shù)可能不同毅糟。那么問(wèn)題來(lái)了红选，既然通過(guò)本地方法已經(jīng)得到了一個(gè)整型值，為何不直接返回呢姆另？我們先看一下jdk8的這段代碼做了些什么
(h = key.hashCode()) ^ (h >>> 16)
因?yàn)閔ashCode返回是個(gè)整型喇肋，也就是說(shuō)內(nèi)存占用4字節(jié)，我們就以一個(gè)32位的2進(jìn)制數(shù)舉例：

根據(jù)key生成index的過(guò)程

不做位移的情況下求index

//聲明變量
Node<K,V>[] tab; Node<K,V> p; int n, i;

if ((tab = table) == null || (n = tab.length) == 0)
    n = (tab = resize()).length;

這里聲明了4個(gè)變量轮纫，然后在if語(yǔ)句里面給tab和n進(jìn)行了賦值：
tab <=> 成員變量table
n <=> table的長(zhǎng)度
resize()我們之后在了解，接著看：

        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }

if中首先對(duì)p進(jìn)行了賦值：
p<=>該index上的Node對(duì)象（為了方便下文稱之為原Node）
根據(jù)key得到的hash值算出table中的index焚鲜，如果對(duì)應(yīng)這個(gè)位置為null掌唾，則實(shí)例化一個(gè)Node，并放到這個(gè)位置忿磅。如果不為空則走入else糯彬。下面對(duì)于這種碰撞的情況進(jìn)行處理：

1. 如果原Node的key和傳入的key一致，我們將傳入的value覆蓋原Node的value贝乎；
2. 如果原Node的key和傳入的key不一致情连，我們看一下這個(gè)原Node是不是TreeNode類型，如果是的览效，我們利用傳入的key却舀、value、hash生成一個(gè)TreeNode锤灿，并掛在上面挽拔；
3. 如果Key不一致且不是TreeNode我們會(huì)根據(jù)next一級(jí)級(jí)往下找，且比對(duì)每個(gè)節(jié)點(diǎn)的key和傳入的key但校，如果找到了一致的螃诅，就將該節(jié)點(diǎn)的value換成傳入的value，如果找到最后一個(gè)節(jié)點(diǎn)仍然不一致，則先根據(jù)key术裸、value倘是、hash新建一個(gè)節(jié)點(diǎn)，如果這個(gè)節(jié)點(diǎn)小于TREEIFY_THRESHOLD這個(gè)閾值袭艺，就直接接入鏈表尾部搀崭。如果大于TREEIFY_THRESHOLD則進(jìn)行樹化焊夸。

HashMap的get方法（結(jié)合源碼）

如果理解了以上的put過(guò)程橙数，那么整個(gè)get過(guò)程就是很容易的配名，get方法的核心代碼如下：

    final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

1. 如果當(dāng)前table里面沒(méi)有內(nèi)容帐我，則get時(shí)返回null；
2. 根據(jù)key得到table的index上的Node董济，如果第一個(gè)Node的key與傳入的key一致盗扒，則返回第一個(gè)Node辆它；
3. 如果第一個(gè)Node的key與傳入的key不一致瘪撇，則先會(huì)判斷获茬，這個(gè)index綁定的Nodes是不是樹型，如果是的倔既，則調(diào)用getTreeNode方法去獲取對(duì)應(yīng)的節(jié)點(diǎn)锦茁；
4. 如果不是樹型，則沿著鏈表比較key值叉存，如果能找到返回對(duì)應(yīng)Node，如果找不到則返回null度帮。
   講到這里出現(xiàn)了tree歼捏！怎么又蹦出來(lái)新的數(shù)據(jù)結(jié)構(gòu)！這個(gè)應(yīng)該是在jdk8后對(duì)傳統(tǒng)HashMap的優(yōu)化笨篷。這個(gè)我們下一節(jié)再詳細(xì)解釋瞳秽。