快捷導(dǎo)航

java?中的HashMap的底層實現(xiàn)和元素添加流程

更新時間：2022年05月09日 09:47:01 作者：??Java中文社群????

這篇文章主要介紹了java?中的HashMap的底層實現(xiàn)和元素添加流程，HashMap?是使用頻率最高的數(shù)據(jù)類型之一，同時也是面試必問的問題之一，尤其是它的底層實現(xiàn)原理，下文更多詳細(xì)內(nèi)容，需要的小伙伴可以參考一下

HashMap 底層實現(xiàn)

HashMap 在 JDK 1.7 和 JDK 1.8 的底層實現(xiàn)是不一樣的，在 JDK 1.7 中，HashMap 使用的是數(shù)組 + 鏈表實現(xiàn)的，而 JDK 1.8 中使用的是數(shù)組 + 鏈表或紅黑樹實現(xiàn)的。

HashMap 在 JDK 1.7 中的實現(xiàn)如下圖所示：

HashMap 在 JDK 1.8 中的實現(xiàn)如下圖所示：

我們本文重點(diǎn)來學(xué)習(xí)主流版本 JDK 1.8 中的 HashMap。HashMap 中每個元素稱之為一個哈希桶（bucket），

哈希桶包含的內(nèi)容有 4 個：

hash 值
key
value
next（下一個節(jié)點(diǎn)）

HashMap 插入流程

HashMap 元素新增的實現(xiàn)源碼如下（下文源碼都是基于主流版本 JDK 1.8）：

public V put(K key, V value) {
    // 對 key 進(jìn)行哈希操作
    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;
    // 哈希表為空則創(chuàng)建表
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    // 根據(jù) key 的哈希值計算出要插入的數(shù)組索引 i
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 如果 table[i] 等于 null，則直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        Node<K,V> e; K k;
        // 如果 key 已經(jīng)存在了，直接覆蓋 value
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p;
        // 如果 key 不存在，判斷是否為紅黑樹
        else if (p instanceof TreeNode)
            // 紅黑樹直接插入鍵值對
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            // 為鏈表結(jié)構(gòu)，循環(huán)準(zhǔn)備插入
            for (int binCount = 0; ; ++binCount) {
                // 下一個元素為空時
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    // 轉(zhuǎn)換為紅黑樹進(jìn)行處理
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                //  key 已經(jīng)存在直接覆蓋 value
                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;
        }
    }
    ++modCount;
    // 超過最大容量，擴(kuò)容
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

上述的源碼都添加了相應(yīng)的代碼注釋，簡單來說 HashMap 的元素添加流程是，先將 key 值進(jìn)行 hash 得到哈希值，根據(jù)哈希值得到元素位置，判斷元素位置是否為空，如果為空直接插入，不為空判斷是否為紅黑樹，如果是紅黑樹則直接插入，否則判斷鏈表是否大于 8，且數(shù)組長度大于 64，如果滿足這兩個條件則把鏈表轉(zhuǎn)成紅黑樹，然后插入元素，如果不滿足這兩個條件中的任意一個，則遍歷鏈表進(jìn)行插入，

它的執(zhí)行流程如下圖所示：

為什么要將鏈表轉(zhuǎn)紅黑樹？

JDK 1.8 中引入了新的數(shù)據(jù)結(jié)構(gòu)紅黑樹來實現(xiàn) HashMap，主要是出于性能的考量。因為鏈表超過一定長度之后查詢效率就會很低，它的時間復(fù)雜度是 O(n)，而紅黑樹的時間復(fù)雜度是 O(logn)，因此引入紅黑樹可以加快 HashMap 在數(shù)據(jù)量比較大的情況下的查詢效率。

哈希算法實現(xiàn)

HashMap 的哈希算法實現(xiàn)源碼如下：

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

其中，key.hashCode() 是 Java 中自帶的 hashCode() 方法，返回一個 int 類型的散列值，后面 hashCode 再右移 16 位，正好是 32bit 的一半，與自己本身做異或操作（相同為 0，不同為 1），主要是為了混合哈希值的高位和低位，增加低位的隨機(jī)性，這樣就實現(xiàn)了 HashMap 的哈希算法。

總結(jié)

HashMap 在 JDK 1.7 時，使用的是數(shù)組 + 鏈表實現(xiàn)的，而在 JDK 1.8 時，使用的是數(shù)組 + 鏈表或紅黑樹的方式來實現(xiàn)的，JDK 1.8 之所以引入紅黑樹主要是出于性能方面的考慮。HashMap 在插入時，會判斷當(dāng)前鏈表的長度是否大于 8 且數(shù)組的長度大于 64，如果滿足這兩個條件就會把鏈表轉(zhuǎn)成紅黑樹再進(jìn)行插入，否則就是遍歷鏈表插入。

到此這篇關(guān)于java 中的HashMap的底層實現(xiàn)和元素添加流程的文章就介紹到這了,更多相關(guān)Java中的HashMap內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: