解析HashMap中的put方法執(zhí)行流程

更新時(shí)間：2021年12月14日 09:44:05 作者：~wangweijun

在Java集合中，HashMap的重要性不言而喻，作為一種存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，它在日常開發(fā)中有著非常多的應(yīng)用場(chǎng)景，也是面試中的高頻考點(diǎn)，本篇文章就來分析一下HashMap集合中的put方法

引言

在Java集合中，HashMap的重要性不言而喻，作為一種存儲(chǔ)鍵值對(duì)的數(shù)據(jù)結(jié)構(gòu)，它在日常開發(fā)中有著非常多的應(yīng)用場(chǎng)景，也是面試中的高頻考點(diǎn)，本篇文章就來分析一下HashMap集合中的put方法。

HashMap底層數(shù)據(jù)結(jié)構(gòu)

先來了解一下HashMap底層的數(shù)據(jù)結(jié)構(gòu)，它實(shí)質(zhì)上是一個(gè)散列表，在數(shù)據(jù)結(jié)構(gòu)課程中，我們應(yīng)該都學(xué)習(xí)過散列表，它是通過關(guān)鍵碼值而直接進(jìn)行訪問的一種數(shù)據(jù)結(jié)構(gòu)，比如存儲(chǔ)這樣的一個(gè)序列：5,12,7,6,1,3。我們首先需要設(shè)定一個(gè)hash函數(shù)，通過該函數(shù)就能夠定位每個(gè)元素存儲(chǔ)的位置，比如hash函數(shù)為 H(k) = k % 6，那么每個(gè)元素的存儲(chǔ)位置即為：1,0,1,0,1,3，此時(shí)問題就出現(xiàn)了，有幾個(gè)元素的存儲(chǔ)位置計(jì)算后發(fā)現(xiàn)是一樣的，而一個(gè)位置不可能存放兩個(gè)值，這就是hash沖突。
解決哈希沖突的方式有很多：

線性探測(cè)法
偽隨機(jī)數(shù)法
鏈地址法

若是采用較為簡(jiǎn)單的線性探測(cè)法，則將產(chǎn)生沖突的元素向后移動(dòng)一個(gè)位置，若是仍然有沖突，則繼續(xù)后移一位，由此可得每個(gè)元素的存儲(chǔ)位置：

在這里插入圖片描述

在HashMap中，它的設(shè)計(jì)當(dāng)然是要精妙很多的，查閱其源碼：

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

    Node(int hash, K key, V value, Node<K,V> next) {
        this.hash = hash;
        this.key = key;
        this.value = value;
        this.next = next;
    }

    public final K getKey()        { return key; }
    public final V getValue()      { return value; }
    public final String toString() { return key + "=" + value; }

    public final int hashCode() {
        return Objects.hashCode(key) ^ Objects.hashCode(value);
    }

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

    public final boolean equals(Object o) {
        if (o == this)
            return true;
        if (o instanceof Map.Entry) {
            Map.Entry<?,?> e = (Map.Entry<?,?>)o;
            if (Objects.equals(key, e.getKey()) &&
                Objects.equals(value, e.getValue()))
                return true;
        }
        return false;
    }
}

我們發(fā)現(xiàn)了這樣的一個(gè)內(nèi)容類，它是一個(gè)Node節(jié)點(diǎn)，由此，我們可以猜測(cè)，HashMap對(duì)于沖突的解決辦法采用的是鏈地址法，那么HashMap數(shù)據(jù)的真正存放位置是在哪呢？

transient Node<K,V>[] table;

就是這樣的一個(gè)Node數(shù)組。

put方法的執(zhí)行流程

我們直接通過一個(gè)程序來理解HashMap中put方法的執(zhí)行流程，在put方法中，HashMap需要經(jīng)歷初始化、存值、擴(kuò)容、解決沖突等等操作：

public static void main(String[] args) {
    Map<String, String> map = new HashMap<>();
    map.put("name", "zs");
    map.put("age", "20");
    map.put("name", "lisi");
    map.forEach((k, v) -> {
        System.out.println(k + "--" + v);
    });
}

這段程序的運(yùn)行結(jié)果我們都知道是name--lisi age -- 20，那為什么是這個(gè)結(jié)果呢？源碼能夠告訴我們答案。

首先執(zhí)行第一行代碼，調(diào)用HashMap的無參構(gòu)造方法：

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

在構(gòu)造方法中，只是設(shè)置了一個(gè)loadFactor的成員變量，它表示的是hash表的負(fù)載因子，默認(rèn)值為0.75，至于這個(gè)負(fù)載因子是什么，我們后面再說。
接下來程序會(huì)執(zhí)行put方法：

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

put方法又調(diào)用了putVal方法，并傳入了key的hash，key，value等等參數(shù)，所以先來計(jì)算key的hash：

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

這個(gè)hash是用來計(jì)算插入位置的，我們放到后面說，計(jì)算完key的hash后，它將調(diào)用putVal方法：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    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;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

該方法的前三行先定義了一個(gè)Node類型的數(shù)組和一個(gè)變量，并判斷類成員中的table是否為空，前面我們已經(jīng)說到，這個(gè)table就是真正來存儲(chǔ)數(shù)據(jù)的數(shù)組，它的初始值肯定為空，所以會(huì)觸發(fā)resize方法：

final Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    if (oldCap > 0) {
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                 oldCap >= DEFAULT_INITIAL_CAPACITY)
            newThr = oldThr << 1; // double threshold
    }
    else if (oldThr > 0) // initial capacity was placed in threshold
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }
    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;
    if (oldTab != null) {
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;
                else if (e instanceof TreeNode)
                    ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    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;
}

這個(gè)resize方法其實(shí)是相當(dāng)復(fù)雜的，但我們撿出重要的代碼來看，因?yàn)閠able的初始值為null，所以一定會(huì)進(jìn)入下面的分支：

else {               // zero initial threshold signifies using defaults
    newCap = DEFAULT_INITIAL_CAPACITY;
    newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}

它設(shè)置了兩個(gè)變量的值，newCap = 16，newThr = 0.75 * 16 = 12，其中newCap就是本次需要?jiǎng)?chuàng)建的table數(shù)組的容量，而newThr就是實(shí)際只能存儲(chǔ)的容量大小。

對(duì)于一個(gè)散列表，如果讓其每個(gè)位置都占滿元素，那么一定是已經(jīng)產(chǎn)生大量的沖突了，但若是只讓小部分位置存儲(chǔ)元素，又會(huì)浪費(fèi)散列表的空間，由此，前輩們經(jīng)過大量的計(jì)算，得出散列表的總?cè)萘?* 0.75之后的值是散列表最合適的存儲(chǔ)容量，這個(gè)0.75就被稱為散列表中的負(fù)載因子。所以，HashMap在第一次調(diào)用put方法時(shí)會(huì)創(chuàng)建一個(gè)總?cè)萘繛?6的Node類型數(shù)組（前提是調(diào)用無參構(gòu)造方法），但實(shí)際上只有12的容量可以被使用，當(dāng)?shù)?3個(gè)元素插入時(shí)，就需要考慮擴(kuò)容。

接下來就是初始化table數(shù)組：

threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;

通過調(diào)用resize方法，我們就獲得了一個(gè)容量為16的Node數(shù)組，緊接著就執(zhí)行：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

還記得這個(gè)hash變量嗎？它就是前面求得的key的hash值，通過n（table數(shù)組的長度，即：16）減1并與hash值做一個(gè)與運(yùn)算，即可得到該數(shù)據(jù)的存儲(chǔ)位置，它類似于文章開篇提到的hash函數(shù) H(k) = k % 6，它做的也是這個(gè)操作，hash % n。需要注意，若是求模操作中，除數(shù)是2的冪次，則求模操作可以等價(jià)于與其除數(shù)減1的與操作，即：hash & (n - 1)，因?yàn)?amp;操作的效率是要高于求模運(yùn)算的，所以HashMap會(huì)將n設(shè)計(jì)為2的冪次。

求得數(shù)據(jù)需要插入的位置后，就需要判斷當(dāng)前位置是否有元素，現(xiàn)在table數(shù)組中沒有任何數(shù)據(jù)，所以第一次判斷一定是null，符合條件，執(zhí)行代碼：tab[i] = newNode(hash, key, value, null);，創(chuàng)建了一個(gè)節(jié)點(diǎn)，并存入hash值，key、value及其指針域：

Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
    return new Node<>(hash, key, value, next);
}

最后執(zhí)行：

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);

判斷當(dāng)前容量size是否超過了閾值threshold，若是超過了，還需要調(diào)用resize方法進(jìn)行擴(kuò)容。
到這里，第一個(gè)數(shù)據(jù)name:zs就插入成功了。

第二個(gè)數(shù)據(jù)age:20在這里就不作分析了，它和name的插入流程是一樣的，我們分析一下第三個(gè)數(shù)據(jù)name:lisi的插入，這里涉及到了一個(gè)key重復(fù)的問題，來看看HashMap是如何處理的。

首先仍然是調(diào)用putVal方法，并計(jì)算key的hash值，然后判斷當(dāng)前table是否為空，這次table肯定不為空，所以直接走到：

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

仍然通過(n - 1) & hash計(jì)算數(shù)據(jù)的插入位置，結(jié)果發(fā)現(xiàn)要插入的位置已經(jīng)有元素了，就是name:zs，此時(shí)就產(chǎn)生了沖突，執(zhí)行：

Node<K,V> e; K k;
if (p.hash == hash &&
    ((k = p.key) == key || (key != null && key.equals(k))))
    e = p;

現(xiàn)在的p就是name:zs，通過p的hash與當(dāng)前數(shù)據(jù)key的hash比較，發(fā)現(xiàn)hash值相同，繼續(xù)比較p的key，即：name與當(dāng)前數(shù)據(jù)的key是否相同，發(fā)現(xiàn)仍然相同，此時(shí)就將p交給e管理，最后執(zhí)行：

if (e != null) { // existing mapping for key
    V oldValue = e.value;
    if (!onlyIfAbsent || oldValue == null)
        e.value = value;
    afterNodeAccess(e);
    return oldValue;
}

此時(shí)e不為null，所以將e中的value值設(shè)置為當(dāng)前數(shù)據(jù)的value值，由此，HashMap便成功將key為name的值修改為了lisi，并返回了原值z(mì)s。

總結(jié)

綜上所述，我們能夠得到以下結(jié)論：

HashMap的總?cè)萘恳欢ㄊ?的冪次方，即使通過構(gòu)造函數(shù)傳入一個(gè)不是2的冪次方的容量，HashMap也會(huì)將其擴(kuò)充至與其最接近的2的冪次方的值；比如傳入總?cè)萘繛?0，則HashMap會(huì)自動(dòng)將容量擴(kuò)充至16
若是調(diào)用HashMap的無參構(gòu)造方法，則將在第一次執(zhí)行put方法時(shí)初始化一個(gè)總?cè)萘繛?6，實(shí)際可用容量為12的Node數(shù)組
當(dāng)實(shí)際容量超過閾值時(shí)，HashMap會(huì)進(jìn)行擴(kuò)容，擴(kuò)容至原容量的2倍
HashMap的put方法執(zhí)行流程：首先判斷當(dāng)前table是否為空，若為空，則初始化，若不為空，則根據(jù)key的hash計(jì)算得到插入位置，再判斷該位置是否有元素，若無元素，則直接插入，若有元素，則判斷原位置數(shù)據(jù)的hash值與待插入數(shù)據(jù)的hash值是否相同，若相同，則繼續(xù)比較值，若值不同，則創(chuàng)建一個(gè)新的Node節(jié)點(diǎn)，并使用尾插法將其插入到原數(shù)據(jù)的節(jié)點(diǎn)后面形成鏈表，若值相同，則采用待插入數(shù)據(jù)的值覆蓋原數(shù)據(jù)的值，并返回原數(shù)據(jù)的值
HashMap采用鏈地址法解決hash沖突，所以當(dāng)某個(gè)鏈表的長度大于8，并且table數(shù)組的長度大于64，則當(dāng)前鏈表會(huì)被轉(zhuǎn)換為紅黑樹，若table數(shù)組的長度尚未達(dá)到64，則進(jìn)行擴(kuò)容；當(dāng)鏈表長度小于6，則會(huì)將紅黑樹轉(zhuǎn)回鏈表
因?yàn)镠ashMap會(huì)根據(jù)key的hash值計(jì)算插入位置，所以key的數(shù)據(jù)類型一定要重寫hashCode方法，否則會(huì)出現(xiàn)兩個(gè)相同的key結(jié)果hash值不相同的情況，也需要重寫equals方法，否則equals方法將比較的是地址值

到此這篇關(guān)于解析HashMap中的put方法的文章就介紹到這了,更多相關(guān)HashMap?put方法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: