前言

本文從三個(gè)部分去探究HashMap的鏈表轉(zhuǎn)紅黑樹的具體時(shí)機(jī)：

創(chuàng)新互聯(lián)公司專注為客戶提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè)、外貿(mào)網(wǎng)站建設(shè)、克州網(wǎng)絡(luò)推廣、小程序開發(fā)、克州網(wǎng)絡(luò)營銷、克州企業(yè)策劃、克州品牌公關(guān)、搜索引擎seo、人物專訪、企業(yè)宣傳片、企業(yè)代運(yùn)營等，從售前售中售后，我們都將竭誠為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)公司為所有大學(xué)生創(chuàng)業(yè)者提供克州建站搭建服務(wù)，24小時(shí)服務(wù)熱線：13518219792，官方網(wǎng)址：aaarwkj.com

1、從HashMap中有關(guān)“鏈表轉(zhuǎn)紅黑樹”閾值的聲明；
2、【重點(diǎn)】解析HashMap.put(K key, V value)的源碼；
3、測試；

一、從HashMap中有關(guān)“鏈表轉(zhuǎn)紅黑樹”閾值的聲明，簡單了解HashMap的鏈表轉(zhuǎn)紅黑樹的時(shí)機(jī)

HashMap中有關(guān)“鏈表轉(zhuǎn)紅黑樹”閾值的聲明：

/**
    *  使用紅黑樹(而不是鏈表)來存放元素。當(dāng)向至少具有這么多節(jié)點(diǎn)的鏈表再添加元素時(shí)，鏈表就將轉(zhuǎn)換為紅黑樹。
    * 該值必須大于2，并且應(yīng)該至少為8，以便于刪除紅黑樹時(shí)轉(zhuǎn)回鏈表。
    */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     *  當(dāng)桶數(shù)組容量小于該值時(shí)，優(yōu)先進(jìn)行擴(kuò)容，而不是樹化：
     */
    static final int MIN_TREEIFY_CAPACITY = 64;

二、【重點(diǎn)】解析HashMap.put(K key, V value)的源碼，去弄清楚鏈表轉(zhuǎn)紅黑樹的具體時(shí)機(jī)

通過查看HashMap的源碼可以發(fā)現(xiàn)，它的put(K key, V value)方法調(diào)用了putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)來實(shí)現(xiàn)元素的新增。所以我們實(shí)際要看的是putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)的源碼。

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); //直接放在散列表上的節(jié)點(diǎn)，并沒有特意標(biāo)識(shí)其為頭節(jié)點(diǎn)，其實(shí)它就是"鏈表/紅黑樹.index(0)"
        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 { //下面的代碼是探究“鏈表轉(zhuǎn)紅黑樹”的重點(diǎn)：
                for (int binCount = 0;; ++binCount) {
                    if ((e = p.next) == null) { //沿著p節(jié)點(diǎn)，找到該桶上的最后一個(gè)節(jié)點(diǎn)：
                        p.next = newNode(hash, key, value, null); //直接生成新節(jié)點(diǎn)，鏈在最后一個(gè)節(jié)點(diǎn)的后面；

                        //“binCount >= 7”：p從鏈表.index(0)開始，當(dāng)binCount == 7時(shí)，p.index == 7,newNode.index == 8； 
                        //也就是說，當(dāng)鏈表已經(jīng)有8個(gè)節(jié)點(diǎn)了，此時(shí)再新鏈上第9個(gè)節(jié)點(diǎn)，在成功添加了這個(gè)新節(jié)點(diǎn)之后，立馬做鏈表轉(zhuǎn)紅黑樹。
                        if (binCount >= TREEIFY_THRESHOLD - 1)
　　　　　　　　　　　　　　　　treeifyBin(tab, hash); //鏈表轉(zhuǎn)紅黑樹 break; 
　　　　　　　　　　　　}
　　　　　　　　　　　　…… 
　　　　　　　　　　　　p = e; 
　　　　　　　　　　} 
　　　　　　 } 
　　　　　　　…… 
　　　　} 
　　　　…… 
}

通過源碼解析，我們已經(jīng)很清楚HashMap是在“當(dāng)鏈表已經(jīng)有8個(gè)節(jié)點(diǎn)了，此時(shí)再新鏈上第9個(gè)節(jié)點(diǎn)，在成功添加了這個(gè)新節(jié)點(diǎn)之后，立馬做鏈表轉(zhuǎn)紅黑樹”。

三、通過debug，進(jìn)一步理解鏈表轉(zhuǎn)紅黑樹的具體時(shí)機(jī)

1. 自定義一個(gè)類：該類中去重寫hashCode()，讓一組數(shù)據(jù)能得到同樣的哈希值，從而實(shí)現(xiàn)哈希碰撞。同時(shí)也重寫equals()方法。

public class A03Bean {
    protected int number;

    public A03Bean(int number) {
        this.number = number;
    }

    /**
     * 重寫hashCode()方法，只要是4的倍數(shù)，最后算出的哈希值都會(huì)是0.
     */
    @Override
    public int hashCode() {
        return number % 4;
    }

    /**
     * 也必須重寫equals()方法。當(dāng)發(fā)生哈希沖突的時(shí)候，需要調(diào)用equals()方法比較兩個(gè)對(duì)象的實(shí)際內(nèi)容是否相同。
     */
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        A03Bean other = (A03Bean) obj;
        if (number != other.number)
            return false;
        return true;
    }
}

2. 將自定義類A03Bean的實(shí)例放到HashMap中：

public class A03Method_TreeifyBin2 {
    public static void main(String[] args) {
        HashMap<A03Bean, Integer> hashMap = new HashMap<>();
        hashMap.put(new A03Bean(4), 0);
        hashMap.put(new A03Bean(8), 1);
        hashMap.put(new A03Bean(12), 2);
        hashMap.put(new A03Bean(16), 3);
        hashMap.put(new A03Bean(20), 4);
        hashMap.put(new A03Bean(24), 5);
        hashMap.put(new A03Bean(28), 6);
        hashMap.put(new A03Bean(32), 7);
        hashMap.put(new A03Bean(36), 8);
        hashMap.put(new A03Bean(40), 9);
        hashMap.put(new A03Bean(44), 10);

        System.out.println("hashMap.size = " + hashMap.size());

        //查看是否所有對(duì)象都放到HashMap中了：
        for(A03Bean key : hashMap.keySet()) {
            System.out.println(key.number);
        }
    }
}

3.debug，斷點(diǎn)查看當(dāng)同一個(gè)桶上的鏈表的長度達(dá)到多長時(shí)會(huì)做“鏈表轉(zhuǎn)紅黑樹”的操作。

斷點(diǎn)打在HashMap.putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法的“treeifyBin(tab, hash);”這里。

4.測試結(jié)果：

當(dāng)put進(jìn)第9個(gè)元素（hashMap.put(new A03Bean(36), 8);）時(shí)，HashMap做了鏈表轉(zhuǎn)紅黑樹的操作。

也就是說：當(dāng)鏈表已經(jīng)有8個(gè)元素了，此時(shí)put進(jìn)第9個(gè)元素，先完成第9個(gè)元素的put，然后立刻做鏈表轉(zhuǎn)紅黑樹。這個(gè)結(jié)論和第2點(diǎn)中得到的結(jié)論一致。

最后的輸出結(jié)果也證明了所有的元素都成功put進(jìn)了集合中，hashMap.size等于11。

到這里，有關(guān)“HashMap的鏈表轉(zhuǎn)紅黑樹的具體時(shí)機(jī)”算是解釋清楚了，有時(shí)間再探究“HashMap的紅黑樹轉(zhuǎn)回鏈表的具體時(shí)機(jī)”。

新聞名稱：HashMap底層數(shù)據(jù)結(jié)構(gòu)之鏈表轉(zhuǎn)紅黑樹的具體時(shí)機(jī)
URL地址：http://aaarwkj.com/article2/peeooc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)站建設(shè)、網(wǎng)站排名、外貿(mào)建站、企業(yè)網(wǎng)站制作、企業(yè)建站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)