HashMap源碼解析

適合閱讀的人群

文筆不是很好矿咕,如果對于HashMap沒有一個大致的了解共虑,最好不要看

目錄

  1. HashMap的幾個基本概念

  2. HashMap的成員變量

  3. HashMap的構(gòu)造方法

  4. HashMap的幾個基礎(chǔ)方法

  5. HashMap的get()方法

  6. HashMap的put()方法

  7. HashMap的resize()方法

  8. HashMap的remove()方法

HashMap的幾個基本概念

桶(bucked):存放同一個hash地址的
table[]:即存放桶的數(shù)組
容量(capacity):即table.length
loadfactor:負(fù)載因子,權(quán)衡hash沖突情況

HashMap的成員變量

首先看HashMap定義的幾個常量

//默認(rèn)容器大小
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//最大容器大小
static final int MAXIMUM_CAPACITY = 1 << 30;

//默認(rèn)負(fù)載因子
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//需要轉(zhuǎn)換為紅黑樹的鏈表長度閾值
static final int TREEIFY_THRESHOLD = 8;

//轉(zhuǎn)換為鏈表的閾值
static final int UNTREEIFY_THRESHOLD = 6;

//需要轉(zhuǎn)換為紅黑樹的容器容量閾值
static final int MIN_TREEIFY_CAPACITY = 64;

這里需要注意到的幾個細(xì)節(jié):

  1. TREEIFY_THRESHOLD:jdk1.8以后,如果長度超過這個閾值憎乙,則一個桶內(nèi)的node由鏈表轉(zhuǎn)為紅黑樹
  2. UNTREEIFY_THRESHOLD:當(dāng)紅黑樹長度小于這個閾值拟杉,就會再退化成鏈表
  3. 只有capacity>=MIN_TREEIFY_CAPACITY時笑旺,才需要將鏈表轉(zhuǎn)換為紅黑樹,否則只需要resize()

這里第三點(diǎn)補(bǔ)充一下:現(xiàn)在HashMap源碼解讀好唯,關(guān)于鏈表轉(zhuǎn)換為紅黑樹這一塊普遍都有誤導(dǎo)性竭沫,大部分資料都是說當(dāng)鏈表長度到達(dá)8時,桶結(jié)構(gòu)從鏈表轉(zhuǎn)換為紅黑樹骑篙,其實(shí)這是不嚴(yán)謹(jǐn)?shù)耐商幔€需要當(dāng)前容量capacity>=MIN_TREEIFY_CAPACITY(即桶數(shù)量>=64)這個條件,否則進(jìn)行擴(kuò)容而不是轉(zhuǎn)換紅黑樹,關(guān)鍵源碼在下面

        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();

這是有道理的,讀者也不妨思考一下靶端,如果當(dāng)capacity的容量只有16的時候谎势,hash嚴(yán)重沖突鏈表長度到達(dá)8,除了hash不均勻之外杨名,也有可能是容量太小脏榆,導(dǎo)致沖突嚴(yán)重,這時候?qū)able進(jìn)行擴(kuò)容,再對元素均勻散列才是最有效的辦法台谍。
再提一點(diǎn)须喂,鏈表轉(zhuǎn)為紅黑樹這個事件發(fā)生的概率有多大呢,我們捋一下幾個條件:

  1. capacity>=MIN_TREEIFY_CAPACITY
  2. 鏈表長度>=TREEIFY_THRESHOLD

但HashMap還有一個loadfactor參數(shù)趁蕊,就拿默認(rèn)值0.75舉例坞生,假設(shè)桶已經(jīng)有64個了,那么當(dāng)節(jié)點(diǎn)到達(dá)48個的時候就會擴(kuò)容掷伙,平均分的話是己,一個桶還不夠分一個節(jié)點(diǎn),一旦擴(kuò)容任柜,又重新對半進(jìn)行散列卒废,因此需要滿足全部以上條件的話寒波,那是非常小的小概率事件。
那么這個算法還有意義嗎?

有意義的升熊,除了應(yīng)對這個隨機(jī)發(fā)生的小概率事件俄烁,還需要應(yīng)對人為刻意的制造hash沖突,如果在服務(wù)器環(huán)境中,如果得到你的hash計(jì)算方法级野,那么有可能針對hash方法進(jìn)行hashdos攻擊页屠,web服務(wù)器會有一個HashMap保存提交的參數(shù),如果不對參數(shù)數(shù)量進(jìn)行限制的話蓖柔,那么一次性提交大量hash沖突的參數(shù)辰企,那么光一次get()方法就能拖垮服務(wù)器的吞吐量,使用紅黑樹,至少能保證了get方法的效率况鸣,但是要解決hashdos還是要以預(yù)防為主牢贸。

繼續(xù)看HashMap的實(shí)例變量

//hash表,每個Node就是一個桶的頭節(jié)點(diǎn)
transient java.util.HashMap.Node<K,V>[] table;

//用來返回迭代器
transient Set<Map.Entry<K,V>> entrySet;

//數(shù)量
transient int size;

//記錄修改次數(shù)
transient int modCount;

//擴(kuò)容的閾值镐捧,等于loadFactor*capacity
int threshold;

//負(fù)載因子
final float loadFactor;

這里需要注意到的細(xì)節(jié):

  1. modCount有什么作用:是為了HashMap的迭代器能夠記錄map有沒有被修改過潜索,在多線程情況,如果迭代器迭代時發(fā)現(xiàn)modCount變化了懂酱,則說明當(dāng)前這份數(shù)據(jù)已經(jīng)無效了竹习,就會拋出一個ConcurrentModificationException異常
  2. threshold就是size的一個閾值,當(dāng)size到達(dá)threshold時列牺,就需要擴(kuò)容,threshold等于loadFactor*capacity
  3. 為什么table都要加上transient不允許序列化?是因?yàn)镠ashCode()的方法是基于平臺的整陌,不同平臺的同一個對象可能會得到不同的HashCode,因此不允許table進(jìn)行序列化
  4. 沒有capacity變量,capacity=table.length

HashMap的構(gòu)造方法

查看HashMap的源碼瞎领,可以看到HashMap有四種構(gòu)造器

//1.設(shè)定容器大小和負(fù)載因子
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                initialCapacity);
    //最大不能超過MAXIMUM_CAPACITY
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

//2.設(shè)定容器大小
public HashMap(int initialCapacity) {
    this(initialCapacity, DEFAULT_LOAD_FACTOR);
}

//3.默認(rèn)方法泌辫,使用默認(rèn)參數(shù)
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; 
}

//4.使用默認(rèn)構(gòu)造器,同時將m填充到這個hashMap
public HashMap(Map<? extends K, ? extends V> m) {
    this.loadFactor = DEFAULT_LOAD_FACTOR;
    putMapEntries(m, false);
}

這里關(guān)注一下第一個構(gòu)造方法的細(xì)節(jié):

this.threshold = tableSizeFor(initialCapacity);

當(dāng)給定了初始容量參數(shù)之后九默,就會調(diào)用tableSizeFor()方法震放,返回一個大于initialCapacity的最小2的冪次方,以符合HashMap的Capacity必須為2的冪次方的要求(為什么這么要求,后面會提到),這里tableSizeFor()的返回值荤西,即表示最后容器的初始化值澜搅,而這里的threshold就不等于負(fù)載因子*容器,而表示的是初始容量

    static final int tableSizeFor(int cap) {
        int n = cap - 1;
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

這個是tableSizeFor()方法邪锌,用了一次很巧妙的方法得到cap最小2的冪次方,有興趣的可以看一下這個博客

同時threshold在初始化時等于0或者等于初始化的容量,在第一次resize()的時候才會變成負(fù)載因子*容器

HashMap的幾個基礎(chǔ)方法

hash()方法

是==HashMap==中用來計(jì)算Key的hash值的唯一方法

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

這里為什么不直接用對象的hashCode,而需要右移十六位進(jìn)行異或勉躺,簡單來說,是讓hashCode高16位和第16位進(jìn)行異或觅丰,增加hashCode的隨機(jī)性饵溅,這里具體不提了,有興趣的可以看HashMap 的 hash 方法原理是什么

同時我們需要注意到妇萄,這里的key是允許為null,當(dāng)key為null時蜕企,默認(rèn)hash值為0咬荷,后面可以看到,即key為null的對象轻掩,都保存到table[0]桶下面

treeifyBin()方法

當(dāng)一個桶中的鏈表長度>TREEIFY_THRESHOLD時要執(zhí)行的方法幸乒,執(zhí)行結(jié)果有兩種

  1. 將鏈表轉(zhuǎn)換為紅黑樹
  2. 執(zhí)行一次rezise()
    取決于capacity是否>=MIN_TREEIFY_CAPACITY
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        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) {
            TreeNode<K,V> hd = null, tl = null;
            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);
            if ((tab[index] = hd) != null)
                hd.treeify(tab);
        }
    }

HashMap的get()方法

接下來是HashMap的第一個重點(diǎn)方法,get()方法

在看源碼之前唇牧,我們可以先設(shè)想罕扎,如果我們是編寫代碼的人,我們會怎么寫get()方法:

  1. 首先獲取到Key的Hash值
  2. 根據(jù)Hash定位到table的桶位置
  3. 對桶內(nèi)元素進(jìn)行遍歷丐重,比較對象是否存在
  4. 如果存在則返回對象

之后我來看get()方法的源碼,可以看到可以訪問的公有的方法.是先對key進(jìn)行hash之后調(diào)用一個getNode()方法,這個方法是包訪問權(quán)限

public V get(Object key) {
    java.util.HashMap.Node<K,V> e;
    return (e = getNode(hash(key), key)) == null ? null : e.value;
}

繼續(xù)看getNode()方法

final java.util.HashMap.Node<K,V> getNode(int hash, Object key) {
    //tab為hash表,first為hash桶的頭指針,n為表的長度,k為用來遍歷鏈表的指針
    java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> first, e; int n; K k;
    // 第一步:獲取表的長度n,獲取到hash桶的頭指針first
    if ((tab = table) != null && (n = tab.length) > 0 &&
            //這里用n-1和hash值進(jìn)行hash,之后講解為什么要這樣
            (first = tab[(n - 1) & hash]) != null) {
        // 第二步:檢查hash桶的頭指針是否和要找的對象key相等
        if (first.hash == hash && 
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        // 第三步:遍歷桶進(jìn)行查找
        if ((e = first.next) != null) {
            // 判斷如果是紅黑樹的結(jié)構(gòu)腔召,則用TreeNode的靜態(tài)方法遞歸查找
            if (first instanceof java.util.HashMap.TreeNode)
                return ((java.util.HashMap.TreeNode<K,V>)first).getTreeNode(hash, key);
            // 否則使用鏈表進(jìn)行遍歷查找
            do {
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    // 如果都沒有找到,則返回null
    return null;
}

這里已經(jīng)把各個步驟都詳細(xì)的寫了注釋扮惦,這里有一個細(xì)節(jié)就是桶的下標(biāo)tab[(n - 1) & hash]為什么是通過(n - 1) & hash進(jìn)行定位?

hashmap要求容量是2的冪次方

/**
 * The default initial capacity - MUST be a power of two.
 */

而n是hashmap的容量

假設(shè)這里有一個key:使用hash()方法得到的hash值為16位:
1111111111110101
換為十進(jìn)制就是65535

hashmap的n為:
2<<4
換為十進(jìn)制就是16

意味著最大的能定位到的下標(biāo)也只是16-1=15
如果直接用hash值就數(shù)組越界了
因此我們需要對hash對n進(jìn)行取余

n-1 = 15
換位二進(jìn)制就是1111
hash & (n - 1)即:
  1111111111110101
& 0000000000001111
= 0000000000000101
最后取到(n-1)位0101

用hash & (n - 1)進(jìn)行取余效率更快臀蛛,同時也解釋了為什么hashmap要求容量是2的冪次方

HashMap的put()方法

在HashMap的put()方法之前,我們也可以先思考put需要考慮什么問題

我們直到hashMap是基于數(shù)組實(shí)現(xiàn)

  1. 如果hash到同一個位置崖蜜,hash沖突了怎么辦
  2. 如果hash沖突嚴(yán)重浊仆,在一個桶內(nèi)有上萬個節(jié)點(diǎn)怎么辦

接下來看put方法的源碼

    //onlyIfAbsent代表key相同時,是否要替換值
    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

這里同樣調(diào)用到一個包訪問方法puVal()

    //onlyIfAbsent表示當(dāng)key重復(fù)需不需要用新值替換舊值
    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab為table,p為臨時指針,n為table的長度,i為hash到的桶
        java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, i;
        // 如果table沒有初始化纳猪,則用resize()方法初始化,resize()在后面提到
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //如果hash到的桶不存在氧卧,則作為頭指針插入
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        else {
            java.util.HashMap.Node<K,V> e; K k;
            //hash到的值相等
            if (p.hash == hash &&
                    //判斷是否是同一個對象桃笙,或者相等(例如String)
                    ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            //如果是樹節(jié)點(diǎn)
            else if (p instanceof java.util.HashMap.TreeNode)
                //則用樹節(jié)點(diǎn)的putTreeVal方法
                e = ((java.util.HashMap.TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //如果為鏈表結(jié)構(gòu)
            else {
                //使用尾插法
                for (int binCount = 0; ; ++binCount) {
                    //遍歷到尾部
                    if ((e = p.next) == null) {
                        //直接鏈入新節(jié)點(diǎn)
                        p.next = newNode(hash, key, value, null);
                        //如果到達(dá)長度限制
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //則轉(zhuǎn)換為紅黑樹或進(jìn)行一次resize();
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果查找到相同的值則返回
                    if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果key已經(jīng)存在,則直接返回
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //根據(jù)onlyIfAbsent決定是否要替換
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                //返回舊值
                return oldValue;
            }
        }
        //如果新插入的Node,就會執(zhí)行一下方法
        //更新操作數(shù)
        ++modCount;
        //如果大于闕值threshold氏堤,則需要resize
        if (++size > threshold)
            resize();
        //這時一個回調(diào)方法,當(dāng)插入節(jié)點(diǎn)的時候執(zhí)行這個方法搏明,但是在HashMap里方法是空的鼠锈,留給子類覆寫
        afterNodeInsertion(evict);
        return null;
    }

關(guān)于put()方法,上面也已經(jīng)說的足夠詳細(xì)了,設(shè)計(jì)到一個比較重要的方法resize(),這個在下一節(jié)會繼續(xù)講到

總結(jié)

  1. 在jdk1.7以前星著,鏈表的插入是使用頭插法购笆,jdk1.8之后是使用的尾插法,這一點(diǎn)不要混淆了
  2. 允許插入的Key為null,hash的桶下標(biāo)為0
  3. 允許插入的Value為null
  4. onlyIfAbsent參數(shù)默認(rèn)為false虚循,因此當(dāng)key重復(fù)時同欠,新value會替換掉舊的value
  5. 當(dāng)一個桶內(nèi)的元素?cái)?shù)量超過TREEIFY_THRESHOLD,則會將當(dāng)前桶由鏈表轉(zhuǎn)換為紅黑樹
  6. 當(dāng)當(dāng)前容器中的節(jié)點(diǎn)數(shù)量size到達(dá)threashold(即負(fù)載因子*容量)時,就會進(jìn)行擴(kuò)容
  7. 每次插入節(jié)點(diǎn)都會更新modCount

HashMap的resize()方法

HashMap的resize()方法主要有兩個作用:

  1. 初始化容器時横缔,為容器創(chuàng)建一個默認(rèn)的map
  2. 當(dāng)插入的數(shù)據(jù)到達(dá)閾值時铺遂,進(jìn)行擴(kuò)容
    final java.util.HashMap.Node<K,V>[] resize() {
        java.util.HashMap.Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //舊的閾值,如果size到達(dá)threshold茎刚,則需要擴(kuò)容
        int oldThr = threshold;
        int newCap, newThr = 0;
        //如果oldCap>0襟锐,則意味著table已經(jīng)初始化過了
        if (oldCap > 0) {
            //最大不能超過MAXIMUM_CAPACITY,如果到達(dá)MAXIMUM_CAPACITY,threshold不作限制
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //進(jìn)行兩倍擴(kuò)容
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                    oldCap >= DEFAULT_INITIAL_CAPACITY)
                newThr = oldThr << 1; // double threshold
        }
        //如果oldCap==0,oldThr>0意味著table還未初始化,同時是調(diào)用的有初始化容量的構(gòu)造器膛锭,有給定的初始容量
        else if (oldThr > 0) 
            //則新容量=oldThr
            newCap = oldThr;
        //如果oldCap==0,oldThr==0意味著table還未初始化粮坞,同時調(diào)用的是默認(rèn)的構(gòu)造器
        else {
            //則新容量為默認(rèn)值
            newCap = DEFAULT_INITIAL_CAPACITY;
            //newThr等于負(fù)載因子*容量大小
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //對threshold賦值
        if (newThr == 0) {
            //等于負(fù)載因子*容量大小
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                    (int)ft : Integer.MAX_VALUE);
        }
        threshold = newThr;
        //下面是需要把舊的table的數(shù)據(jù)全部再hash到新的table
        @SuppressWarnings({"rawtypes","unchecked"})
        java.util.HashMap.Node<K,V>[] newTab = (java.util.HashMap.Node<K,V>[])new java.util.HashMap.Node[newCap];
        table = newTab;
        if (oldTab != null) {
            //對table每個桶進(jìn)行遍歷
            for (int j = 0; j < oldCap; ++j) {
                java.util.HashMap.Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    //如果是桶的頭指針蚊荣,則直接再hash到新的桶
                    if (e.next == null)
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果是樹節(jié)點(diǎn),則進(jìn)行切分,切分成兩棵子樹莫杈,或者退化成兩個鏈表
                    else if (e instanceof java.util.HashMap.TreeNode)
                        ((java.util.HashMap.TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    //如果是鏈表互例,則拆分成兩個新鏈表
                    else {
                        //分為高位鏈表和低位鏈表
                        java.util.HashMap.Node<K,V> loHead = null, loTail = null;
                        java.util.HashMap.Node<K,V> hiHead = null, hiTail = null;
                        java.util.HashMap.Node<K,V> next;
                        do {
                            next = e.next;
                            //和舊容器長度進(jìn)行hash如果等于0則說明 hash<oldCap,鏈接到低位鏈表
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //如果>0則說明 hash>oldCap,鏈接到高位鏈表
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        //最后將高位低位鏈表放回到新的table
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

擴(kuò)容總結(jié)為三步驟

  1. 獲得新容量newCap,更新域里面的threshold
  2. 創(chuàng)建一個新table,長度為newCap
  3. 將舊的table里面的Node,拷貝到新容器(桶的Key的hash值不需要重新計(jì)算筝闹,只需要計(jì)算hash在新table的高位還是低位)

HashMap的remove()方法

remove()方法比較簡單

    public V remove(Object key) {
        java.util.HashMap.Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
                null : e.value;
    }
    //matchValue表示只有value相等的時候刪除
    final java.util.HashMap.Node<K,V> removeNode(int hash, Object key, Object value,
                                                 boolean matchValue, boolean movable) {
        java.util.HashMap.Node<K,V>[] tab; java.util.HashMap.Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
                (p = tab[index = (n - 1) & hash]) != null) {
            java.util.HashMap.Node<K,V> node = null, e; K k; V v;
            //如果是桶的頭指針
            if (p.hash == hash &&
                    ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                //判斷是否是紅黑樹
                if (p instanceof java.util.HashMap.TreeNode)
                    //獲得紅黑樹的節(jié)點(diǎn)
                    node = ((java.util.HashMap.TreeNode<K,V>)p).getTreeNode(hash, key);
                //否則遞歸獲得鏈表節(jié)點(diǎn)
                else {
                    do {
                        if (e.hash == hash &&
                                ((k = e.key) == key ||
                                        (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //如果matchValue為true就需要判斷聂示,兩個對象時候相等,或者是否equals
            if (node != null && (!matchValue || (v = node.value) == value ||
                    (value != null && value.equals(v)))) {
                //如果是紅黑樹節(jié)點(diǎn)
                if (node instanceof java.util.HashMap.TreeNode)
                    ((java.util.HashMap.TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果是鏈表且是鏈表的頭節(jié)點(diǎn)
                else if (node == p)
                    tab[index] = node.next;
                //如果是鏈表的中間節(jié)點(diǎn)
                else
                    p.next = node.next;
                //操作數(shù)+1
                ++modCount;
                //size-1
                --size;
                //回調(diào)函數(shù)纵竖,目前實(shí)現(xiàn)為空
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

最后

這里沒有涉及紅黑樹的算法部分
如果有寫的不正確的地方墓造,歡迎提出來,如果有不理解的地方解寝,也可以提出來

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末扩然,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子聋伦,更是在濱河造成了極大的恐慌夫偶,老刑警劉巖,帶你破解...
    沈念sama閱讀 223,126評論 6 520
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件觉增,死亡現(xiàn)場離奇詭異兵拢,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)逾礁,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,421評論 3 400
  • 文/潘曉璐 我一進(jìn)店門说铃,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人嘹履,你說我怎么就攤上這事腻扇。” “怎么了砾嫉?”我有些...
    開封第一講書人閱讀 169,941評論 0 366
  • 文/不壞的土叔 我叫張陵幼苛,是天一觀的道長。 經(jīng)常有香客問我焕刮,道長舶沿,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,294評論 1 300
  • 正文 為了忘掉前任配并,我火速辦了婚禮括荡,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘荐绝。我一直安慰自己一汽,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,295評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著召夹,像睡著了一般岩喷。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上监憎,一...
    開封第一講書人閱讀 52,874評論 1 314
  • 那天纱意,我揣著相機(jī)與錄音,去河邊找鬼鲸阔。 笑死偷霉,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的褐筛。 我是一名探鬼主播类少,決...
    沈念sama閱讀 41,285評論 3 424
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼渔扎!你這毒婦竟也來了硫狞?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,249評論 0 277
  • 序言:老撾萬榮一對情侶失蹤晃痴,失蹤者是張志新(化名)和其女友劉穎残吩,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體倘核,經(jīng)...
    沈念sama閱讀 46,760評論 1 321
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡泣侮,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,840評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了紧唱。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片活尊。...
    茶點(diǎn)故事閱讀 40,973評論 1 354
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖琼蚯,靈堂內(nèi)的尸體忽然破棺而出酬凳,到底是詐尸還是另有隱情,我是刑警寧澤遭庶,帶...
    沈念sama閱讀 36,631評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站稠屠,受9級特大地震影響峦睡,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜权埠,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,315評論 3 336
  • 文/蒙蒙 一榨了、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧攘蔽,春花似錦龙屉、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,797評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽作岖。三九已至,卻和暖如春五芝,著一層夾襖步出監(jiān)牢的瞬間痘儡,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,926評論 1 275
  • 我被黑心中介騙來泰國打工枢步, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留沉删,地道東北人。 一個月前我還...
    沈念sama閱讀 49,431評論 3 379
  • 正文 我出身青樓醉途,卻偏偏與公主長得像矾瑰,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子隘擎,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,982評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 前言 今天來介紹下HashMap脯倚,之前的List,講了ArrayList嵌屎、LinkedList推正,就前兩者而言,反映...
    嘟爺MD閱讀 2,881評論 2 56
  • 1.HashMap是一個數(shù)組+鏈表/紅黑樹的結(jié)構(gòu)宝惰,數(shù)組的下標(biāo)在HashMap中稱為Bucket值植榕,每個數(shù)組項(xiàng)對應(yīng)的...
    誰在烽煙彼岸閱讀 1,028評論 2 2
  • 摘要 HashMap是程序猿使用頻率最高的用于映射(鍵值對)的數(shù)據(jù)類型。JDK1.8對HashMap進(jìn)行了優(yōu)化尼夺,例...
    一凡呀閱讀 735評論 0 2
  • HashMap我們經(jīng)常使用尊残,那么它的數(shù)據(jù)結(jié)構(gòu)和底層實(shí)現(xiàn)是怎么樣的,我們來啃一下淤堵。 HashMap的數(shù)據(jù)結(jié)構(gòu) Has...
    激情的狼王閱讀 625評論 1 4
  • 啟動mysql服務(wù) 關(guān)閉服務(wù) 登錄root 登錄遠(yuǎn)程數(shù)據(jù)庫 查看數(shù)據(jù)庫 創(chuàng)建數(shù)據(jù)庫 刪除數(shù)據(jù)庫 創(chuàng)建用戶 用戶查看...
    胡蘿卜櫻閱讀 424評論 0 0