HashMap的實(shí)現(xiàn)原理是什么？

HashMap是一個(gè)高頻的面試題，那么如何才能回答的比較合適呢？

一、青銅級(jí)

以下是jdk1.7與jdk1.8中hashmap的區(qū)別：

概括下可以從以下幾個(gè)方面來(lái)回答：

1、基本原理

HashMap是一個(gè)基于Hash散列技術(shù)，以鍵值對(duì)形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

2、數(shù)據(jù)存儲(chǔ)

JDK 1.8 之前的 HashMap 使用的數(shù)組+鏈表的結(jié)構(gòu)，插入時(shí)使用頭插法。

JDK 1.8 之后的 HashMap 使用的數(shù)組+鏈表/紅黑樹(shù)的結(jié)構(gòu)，插入時(shí)使用頭插法。

3、哈希沖突

JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。

JDK 1.8 引入了紅黑樹(shù)作為替代鏈表的沖突解決策略。

4、擴(kuò)容和負(fù)載因子

當(dāng)哈希表中的元素?cái)?shù)量超過(guò)一定閾值時(shí)，HashMap 會(huì)自動(dòng)進(jìn)行擴(kuò)容，以保持較低的負(fù)載因子，從而提高性能。

二、王者級(jí)

可以從以下幾個(gè)方面來(lái)回答：

1、基本原理

HashMap是一個(gè)基于Hash散列技術(shù)，以鍵值對(duì)形式存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)。

2、數(shù)據(jù)存儲(chǔ)

HashMap內(nèi)部維護(hù)一個(gè)數(shù)組，這個(gè)數(shù)組的每個(gè)位置都是一個(gè)鏈表或紅黑樹(shù)的頭節(jié)點(diǎn)。這些節(jié)點(diǎn)用于存儲(chǔ)鍵值對(duì)。

（1）JDK1.8之前

JDK1.8之前的 HashMap 由 Entry 數(shù)組組成，Entry 類(lèi)是 HashMap 中存儲(chǔ)鍵值對(duì)的類(lèi)。Entry 類(lèi)包含 key、value 和 next 三個(gè)屬性。key 是鍵，value 是值，next 是指向下一個(gè) Entry 對(duì)象的指針，出現(xiàn) hash 沖突存放到鏈表中。具體源碼是通過(guò) put() 方法實(shí)現(xiàn)的。

put() 方法的實(shí)現(xiàn)如下：

public V put(K key, V value) {
    // 如果哈希表為空，則對(duì)其進(jìn)行申請(qǐng)數(shù)組空間
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }

    // 如果 key 為 null，則將其放入 null 鍵的特殊位置
    if (key == null) {
        return putForNullKey(value);
    }

    // 計(jì)算 key 的哈希值
    int hash = hash(key);

    // 根據(jù)哈希值和哈希表的長(zhǎng)度計(jì)算索引位置
    int i = indexFor(hash, table.length);

    // 遍歷索引位置上的鏈表，尋找 key
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        // 如果 key 相同，則更新 value 并返回舊值
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    // 如果 key 不存在，則添加一個(gè)新的鏈表成員
    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

put() 方法首先計(jì)算 key 的 hash 值，然后定位到數(shù)組索引位置。如果數(shù)組索引位置上已經(jīng)存在 Entry 對(duì)象，則判斷 key 是否相同。如果相同則直接覆蓋value，否則添加到鏈表中。如果數(shù)組索引位置上不存在 Entry 對(duì)象，則直接添加到數(shù)組中。

鏈表的具體實(shí)現(xiàn)如下：

static class Entry<K, V> implements Map.Entry<K, V> {

    final int hash;
    final K key;
    V value;
    Entry<K, V> next;

    Entry(int hash, K key, V value) {
        this.hash = hash;
        this.key = key;
        this.value = value;
    }

    @Override
    public K getKey() {
        return key;
    }

    @Override
    public V getValue() {
        return value;
    }

    @Override
    public V setValue(V newValue) {
        V oldValue = value;
        value = newValue;
        return oldValue;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Entry<?, ?> entry = (Entry<?, ?>) o;
        return hash == entry.hash &&
        Objects.equals(key, entry.key) &&
        Objects.equals(value, entry.value);
    }

    @Override
    public int hashCode() {
        return Objects.hash(hash, key, value);
    }

    @Override
    public String toString() {
        return key + "=" + value;
    }
}

鏈表的每個(gè)元素是一個(gè) Entry 對(duì)象，Entry 對(duì)象包含 key、value、hash 和 next 四個(gè)屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個(gè) Entry 對(duì)象的指針。

當(dāng) HashMap 出現(xiàn) hash 沖突時(shí)，會(huì)將新的 Entry 對(duì)象添加到鏈表的尾部。鏈表的查詢性能較差，當(dāng)鏈表長(zhǎng)度過(guò)長(zhǎng)時(shí)，會(huì)影響 HashMap 的查詢性能。

源代碼中有幾處關(guān)鍵的地方：

關(guān)鍵一：

先通過(guò)indexFor下標(biāo)定位到的數(shù)組元素位置，再遍歷這個(gè)元素(鏈表)，依次和鏈表中的key比較，如果 key 相同就直接覆蓋，不同就采用頭插法插入元素。

關(guān)鍵二：

頭插法的實(shí)現(xiàn)主要涉及到兩個(gè)方法：addEntry 和 createEntry。addEntry 方法用于判斷是否需要擴(kuò)容，并調(diào)用 createEntry 方法將鍵值對(duì)存入數(shù)組中。createEntry 方法用于創(chuàng)建一個(gè)新的節(jié)點(diǎn)，并將其 next 屬性指向原來(lái)的鏈表頭節(jié)點(diǎn)，然后將新節(jié)點(diǎn)賦值給數(shù)組對(duì)應(yīng)位置，完成頭插法。

插入元素使用createEntry，新元素會(huì)的next指向table[bucketIndex]也就是鏈表的頭節(jié)點(diǎn)。

（2）JDK1.8之后(含1.8)

JDK1.8的 HashMap 由 Node 數(shù)組組成，Node 類(lèi)是 HashMap 中存儲(chǔ)鍵值對(duì)的類(lèi)。Node 類(lèi)包含 key、value、hash、next 和 prev 五個(gè)屬性。key 是鍵，value 是值，hash 是 key 的 hash 值，next 是指向下一個(gè) Node 對(duì)象的指針，prev 是指向前一個(gè) Node 對(duì)象的指針。
JDK1.8之后的 HashMap 由 Node 數(shù)組組成，出現(xiàn) hash 沖突存放到鏈表中同時(shí)滿足條件的情況下會(huì)生成紅黑樹(shù)。具體源碼是通過(guò) put() 方法實(shí)現(xiàn)的。

put() 方法的實(shí)現(xiàn)如下：

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 = table;
    // 如果哈希表為空或長(zhǎng)度為0，則進(jìn)行擴(kuò)容
    if (tab == null || tab.length == 0) {
        tab = resize();
    }
    // 計(jì)算索引位置
    int n = tab.length;
    int i = (n - 1) & hash;

    // 如果索引位置上的節(jié)點(diǎn)為空，則添加一個(gè)新的節(jié)點(diǎn)
    Node<K,V> p = tab[i];
    if (p == null) {
        tab[i] = newNode(hash, key, value, null);
    } else {
        // 如果索引位置上的節(jié)點(diǎn)存在，則遍歷鏈表，尋找 key 相同的節(jié)點(diǎn)
        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) {
            // 如果索引位置上的節(jié)點(diǎn)是紅黑樹(shù)節(jié)點(diǎn)，則調(diào)用紅黑樹(shù)的 putTreeVal() 方法添加新的節(jié)點(diǎn)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        } else {
            // 如果索引位置上的節(jié)點(diǎn)是鏈表節(jié)點(diǎn)，則遍歷鏈表，尋找 key 相同的節(jié)點(diǎn)
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    // 如果沒(méi)有找到 key 相同的節(jié)點(diǎn)，則在鏈表尾部添加一個(gè)新的節(jié)點(diǎn)
                    p.next = newNode(hash, key, value, null);
                    // 如果鏈表長(zhǎng)度超過(guò)閾值，則將鏈表轉(zhuǎn)換為紅黑樹(shù)
                    if (binCount >= TREEIFY_THRESHOLD - 1) {
                        treeifyBin(tab, hash);
                    }
                    break;
                }
                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {
                    // 如果找到 key 相同的節(jié)點(diǎn)，則停止遍歷
                    break;
                }
                p = e;
            }
        }

        if (e != null) { // 找到 key 相同的節(jié)點(diǎn)
            // 獲取舊值
            V oldValue = e.value;
            // 如果只有 key 不存在才添加新的節(jié)點(diǎn)，則僅當(dāng)舊值為 null 時(shí)才更新值
            if (!onlyIfAbsent || oldValue == null) {
                e.value = value;
            }
            // 調(diào)用 afterNodeAccess() 方法更新節(jié)點(diǎn)的訪問(wèn)時(shí)間
            afterNodeAccess(e);
            return oldValue;
        }
    }

    // 添加新的節(jié)點(diǎn)后，更新 HashMap 的大小和修改次數(shù)
    ++modCount;
    if (++size > threshold) {
        resize();
    }
    // 調(diào)用 afterNodeInsertion() 方法更新節(jié)點(diǎn)的插入狀態(tài)
    afterNodeInsertion(evict);
    return null;
}

put() 方法在添加元素時(shí)，會(huì)先判斷數(shù)組索引位置上是否已經(jīng)存在 Node 對(duì)象。如果已經(jīng)存在，則判斷 key 是否相同。如果相同則更新 value，否則添加到鏈表中。

如果鏈表長(zhǎng)度超過(guò)閾值，則將鏈表轉(zhuǎn)換為紅黑樹(shù)。閾值的默認(rèn)值是 8。

treeifyBin() 方法的實(shí)現(xiàn)如下：

final void treeifyBin(Node<K,V>[] tab, int hash) {
    // 如果哈希表為空或長(zhǎng)度小于 MIN_TREEIFY_CAPACITY，則進(jìn)行擴(kuò)容
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) {
        resize();
    } else if ((e = tab[index = (n - 1) & hash]) != null) {
        // 獲取索引位置上的節(jié)點(diǎn)
        TreeNode<K,V> hd = null, tl = null;
        // 遍歷鏈表，將每個(gè)節(jié)點(diǎn)轉(zhuǎn)換為紅黑樹(shù)節(jié)點(diǎ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);
        // 將轉(zhuǎn)換后的紅黑樹(shù)節(jié)點(diǎn)添加到哈希表中
        if ((tab[index] = hd) != null) {
            hd.treeify(tab);
        }
    }
}

treeifyBin() 方法首先判斷鏈表的長(zhǎng)度是否超過(guò)閾值。如果超過(guò)閾值，則將鏈表的第一個(gè)元素作為紅黑樹(shù)的根節(jié)點(diǎn)。

然后，將鏈表中的所有元素添加到紅黑樹(shù)中。

最后，將紅黑樹(shù)的根節(jié)點(diǎn)添加到數(shù)組中。

這樣，當(dāng) HashMap 出現(xiàn) hash 沖突存放到鏈表中同時(shí)滿足條件的情況下，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)，提高查詢性能。

源代碼中有幾處關(guān)鍵的地方：

當(dāng)鏈表的節(jié)點(diǎn)數(shù)量達(dá)到閾值(默認(rèn)為 8 )，執(zhí)行 treeifyBin 方法。

關(guān)鍵二：

進(jìn)入treeifyBin方法后還有一個(gè)邏輯就是當(dāng)數(shù)組長(zhǎng)度大于或者等于 64 的情況下，才會(huì)執(zhí)行轉(zhuǎn)換紅黑樹(shù)操作，以減少搜索時(shí)間。否則，就是只是對(duì)數(shù)組擴(kuò)容。所以鏈表長(zhǎng)度大于閾值不是轉(zhuǎn)為紅黑樹(shù)的唯一條件。

關(guān)鍵三：

區(qū)別于jdk1.7，jdk1.8已經(jīng)使用了尾插法實(shí)現(xiàn)鏈表元素的插入。

問(wèn)題：為什么jdk1.8后改為尾插法？

主要是因?yàn)轭^插法在多線程擴(kuò)容情況下會(huì)引起鏈表環(huán)。那什么是鏈表環(huán)呢？

線程1，第一節(jié)點(diǎn)為A，第二節(jié)點(diǎn)為B后面就沒(méi)有了，遍歷過(guò)程為A->B然后B沒(méi)有后面節(jié)點(diǎn)即遍歷結(jié)束。

這時(shí)線程1掛起。線程2引發(fā)擴(kuò)容，擴(kuò)容后為B->A。這時(shí)線程1遍歷就會(huì)發(fā)現(xiàn)A的下一節(jié)點(diǎn)是B，會(huì)發(fā)現(xiàn)遍歷B時(shí)B還有后續(xù)的節(jié)點(diǎn)為A，這樣就出樣鏈表環(huán)了。

（3）Node 與Entry區(qū)別

在 Java 的 HashMap 中，Node 和 Entry 都是用于表示鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，但它們?cè)诓煌姹镜?HashMap 中有一些區(qū)別：

Node：

• Node 是在 JDK 1.8 之后的版本中引入的，用于存儲(chǔ)鍵值對(duì)。
• Node 主要用于存儲(chǔ)在哈希沖突的情況下，將鍵值對(duì)以鏈表或紅黑樹(shù)的方式組織起來(lái)的數(shù)據(jù)結(jié)構(gòu)。
• Node 是 TreeNode 和 LinkedNode 的父類(lèi)，這兩個(gè)子類(lèi)分別用于表示紅黑樹(shù)節(jié)點(diǎn)和鏈表節(jié)點(diǎn)。
• Node 中包含了鍵、值、哈希碼、下一個(gè)節(jié)點(diǎn)引用等信息。

Entry：

• Entry 是在 JDK 1.7 及之前的版本中用于存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)。
• Entry 是 HashMap 內(nèi)部的靜態(tài)內(nèi)部類(lèi)，用于表示鍵值對(duì)。
• Entry 主要用于存儲(chǔ)在哈希沖突的情況下，將鍵值對(duì)以鏈表的方式組織起來(lái)的數(shù)據(jù)結(jié)構(gòu)。
• Entry 中包含了鍵、值、下一個(gè) Entry 的引用等信息。

Node 和 Entry 都用于表示鍵值對(duì)，但它們的命名和實(shí)現(xiàn)方式在不同的 Java 版本中有所不同。Node 主要用于 JDK 1.8 及之后的 HashMap，而 Entry 主要用于 JDK 1.7 及之前的 HashMap。Node 進(jìn)一步改進(jìn)了哈希沖突的處理方式，引入了紅黑樹(shù)來(lái)提高性能。

3、哈希沖突

JDK 1.8 之前的 HashMap 使用的是拉鏈法（Chaining）作為沖突解決策略。

HashMap 通過(guò) key 的 hashCode 經(jīng)過(guò)擾動(dòng)函數(shù)處理過(guò)后得到 hash 值，然后通過(guò) (n - 1) & hash 判斷當(dāng)前元素存放的位置，如果當(dāng)前位置存在元素的話，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同，如果相同的話，直接覆蓋，不相同就通過(guò)拉鏈法解決沖突。以下就是JDK1.7中的hashcode擾動(dòng)函數(shù)。

JDK 1.8 中，HashMap 使用了拉鏈法和紅黑樹(shù)兩種沖突解決策略。當(dāng)鏈表長(zhǎng)度超過(guò)一定閾值時(shí)，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)。紅黑樹(shù)是一種自平衡二叉樹(shù)，具有較高的查詢性能。以下就是JDK1.8中的hashcode擾動(dòng)函數(shù)。

JDK1.8 中的 HashMap 在查詢性能上比 JDK1.7 中的 HashMap 有一定的提升。

以下是 JDK1.7 和 JDK1.8 中 HashMap 解決哈希沖突方法的具體對(duì)比：

JDK1.8 中的 HashMap 解決哈希沖突的方法更加靈活，可以適應(yīng)不同的場(chǎng)景。

4、擴(kuò)容和負(fù)載因子

當(dāng)哈希表中的元素?cái)?shù)量超過(guò)一定閾值時(shí)，HashMap 會(huì)自動(dòng)進(jìn)行擴(kuò)容，以保持較低的負(fù)載因子，從而提高性能。

Java HashMap 使用負(fù)載因子來(lái)控制擴(kuò)容。負(fù)載因子是指 HashMap 中鍵值對(duì)數(shù)與 HashMap 容量的比值。

HashMap 的初始容量為 16，負(fù)載因子為 0.75。這意味著，當(dāng) HashMap 中鍵值對(duì)數(shù)達(dá)到 16 * 0.75 = 12 時(shí)，HashMap 就會(huì)進(jìn)行擴(kuò)容。

HashMap 的擴(kuò)容方式是將容量擴(kuò)大為原來(lái)的 2 倍。例如，當(dāng) HashMap 的容量為 16 時(shí)，擴(kuò)容后容量為 32。

HashMap 擴(kuò)容的原因是，當(dāng) HashMap 的負(fù)載因子達(dá)到一定值時(shí)，HashMap 的查詢性能會(huì)下降。這是因?yàn)椋?dāng) HashMap 的容量較小，并且鍵值對(duì)數(shù)較多時(shí)，會(huì)導(dǎo)致哈希沖突的概率增加。

因此，HashMap 會(huì)在負(fù)載因子達(dá)到一定值時(shí)進(jìn)行擴(kuò)容，以提高查詢性能。

以下是 HashMap 擴(kuò)容的具體步驟：

• 創(chuàng)建一個(gè)新的 HashMap，容量為原來(lái)的 2 倍。
• 將原 HashMap 中的所有鍵值對(duì)復(fù)制到新 HashMap 中。
• 將原 HashMap 置為空。