HashMap底層學習筆記

最近開始在閱讀一些源碼之類的學習茄茁,趁著周末魂贬,今天詳細學習了一些HashMap底層的知識,遂記錄下來裙顽。有很多理解或者描述不當之處付燥,望請指正。

一愈犹、數(shù)據(jù)底層結(jié)構(gòu)圖

在這里插入圖片描述

首先放一張HashMap底層結(jié)構(gòu)圖键科,由于現(xiàn)在JDK幾乎都用8及以上了,因此本文記錄的都是基于JDK8的HashMap漩怎。
在JDK8以后勋颖,HashMap底層采用數(shù)組+鏈表+紅黑樹的形式來進行存儲。
HashMap底層用一個數(shù)組來存放節(jié)點勋锤,節(jié)點在數(shù)組中的位置是由一個特殊的算法計算出來的(下文會提到)授帕。如果兩個節(jié)點計算出來的hash值相同核无,那么就將新的節(jié)點以鏈表的形式宵呛,連接在已存在的節(jié)點的后面油猫。如果同一位置的節(jié)點數(shù)超過8個,那么會將鏈表改成紅黑樹的形式進行存儲谈宛。
這樣說有點抽象次哈,結(jié)合源碼一起看吧。

二吆录、HashMap源碼解讀

首先我們來看HashMap中的基本單位窑滞,節(jié)點,包括鏈表節(jié)點和紅黑樹節(jié)點。
鏈表節(jié)點:

/**
     * Basic hash bin node, used for most entries.  (See below for
     * TreeNode subclass, and in LinkedHashMap for its Entry subclass.)
     */
     //map內(nèi)的存儲單位哀卫,以節(jié)點方式存儲巨坊,有hash,key,value,nextNode四個屬性
    static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        //node的構(gòu)造方法
        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; }
        //重寫Node的hashCode方法,用默認的hashCode方法計算出key的hashCode聊训,
        //再和value的hashCode進行異或操作作為node的hashCode
        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = value;
            value = newValue;
            return oldValue;
        }
        
        //重寫Node的equals方法
        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;
        }
    }

每個節(jié)點都有hash,key,value,Node<K,V> next四個屬性抱究,hash是該節(jié)點的hash值恢氯,next是此節(jié)點的下一個節(jié)點带斑。hash是此節(jié)點的hash值。在這個內(nèi)部靜態(tài)類中勋拟,重寫了hashCode()和equals()方法勋磕。計算hash值的方法是用默認的hashCode方法計算出key的hashCode,再和value的hashCode進行異或操作作為node的hash碼敢靡。

樹節(jié)點的屬性:

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }
        }

每個樹節(jié)點有父節(jié)點挂滓,左節(jié)點,右節(jié)點等屬性啸胧。構(gòu)造器則是和Node一樣赶站,需要hash,key,value,next等參數(shù)。

接下來看HashMap的插入方法纺念。

public V put(K key, V value) {
        //直接調(diào)用putVal方法
        return putVal(hash(key), key, value, false, true);
    }

底層是通過putVal()方法進行插值贝椿,繼續(xù)看putVal()方法,打了很多注釋陷谱,應該看得懂~
屬性說明:
table:Node<K,V>[]烙博,底層存儲節(jié)點的數(shù)組

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果當前存node的數(shù)組tab是空的
        if ((tab = table) == null || (n = tab.length) == 0)
            //調(diào)用resize()方法對tab進行擴容,把長度返回給n
            n = (tab = resize()).length;
        //計算新的節(jié)點在table中的位置烟逊,算法是用數(shù)組長度n-1來和哈希進行與運算(目前還不懂這個算法有啥好處)
        //如果那個位置是空的渣窜,就直接插入新的node
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

        //如果那個位置有節(jié)點了
        else {
            Node<K,V> e; K k;
            //p代表計算出來新節(jié)點應該存放位置的節(jié)點
            //如果需要添加的node的key已經(jīng)存在了
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //把p的值賦給e,也就是直接把table[i]的值給新插入的元素宪躯,在后面會替換掉value
                e = p;
            //如果key不存在的情況
            //先判斷p是不是樹節(jié)點
            else if (p instanceof TreeNode)
                //是樹節(jié)點的話乔宿,用傳入的參數(shù),插入一個新節(jié)點访雪,并賦值給e
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //是鏈表節(jié)點的話
            else {
                for (int binCount = 0; ; ++binCount) {
                    //如果table[i]的下一個節(jié)點是空的
                    if ((e = p.next) == null) {
                        //把table[i]的下一個節(jié)點設置為要插入的節(jié)點
                        p.next = newNode(hash, key, value, null);
                        //如果table[i]那個位置上已經(jīng)存在的node數(shù)量大于等7了详瑞,說明鏈表要轉(zhuǎn)換成紅黑樹了
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            //替換鏈表結(jié)構(gòu)改為紅黑樹結(jié)構(gòu)
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果key已經(jīng)存在了,就直接把e的值賦值給table[i]上那個節(jié)點
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果map中已經(jīng)存在要新添加的節(jié)點的key了
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                //判斷已存在的key對應的value是否為空冬阳,是的話直接覆蓋值
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                //回調(diào)方法
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        //如果數(shù)組中的節(jié)點數(shù)大于閥值了蛤虐,擴容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

在上面源碼中,計算節(jié)點在table中位置的算法是i = (n - 1) & hash]肝陪,在底層源碼中驳庭,定義的HashMap的容量只能是2的次冪數(shù),如果不是,也算強制通過resize()轉(zhuǎn)換成2的高次冪饲常。

/**
     * The default initial capacity - MUST be a power of two.
     */
    //初始化容量蹲堂,16,必須是2的次冪
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16


在n-1后贝淤,這個數(shù)的二進制數(shù)就全是1了柒竞,再和hash值進行&操作,這操作好像很騷播聪,我還沒能get到它具體騷在哪里朽基,只是覺得這種方式運算起來好像很簡單,計算出來的位置离陶,直接能夠截取hash值(n-1)對應的二進制位數(shù)長度的低位稼虎。

結(jié)合源碼和上面的結(jié)構(gòu)圖,應該能對HashMap結(jié)構(gòu)以及JDK是如何實現(xiàn)它的有了一點點了解~
無奈我語言表達能力過差招刨,不能像其他博主一樣很生動形象的將自己意思表達出來霎俩,只能上圖和源碼了emmmm希望今年能多寫點學習筆記,把自己學習到的知識記錄分享沉眶。

小感想

通過閱讀源碼打却,能夠稍微得了解一些大觸們的編程世界,除了感嘆那些精巧的算法和設計谎倔,源碼里有很多值得學習的思想柳击。
最后...一句雞湯,只有努力永遠不會辜負你传藏。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末腻暮,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子毯侦,更是在濱河造成了極大的恐慌哭靖,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,744評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件侈离,死亡現(xiàn)場離奇詭異试幽,居然都是意外死亡,警方通過查閱死者的電腦和手機卦碾,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,505評論 3 392
  • 文/潘曉璐 我一進店門铺坞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人洲胖,你說我怎么就攤上這事济榨。” “怎么了绿映?”我有些...
    開封第一講書人閱讀 163,105評論 0 353
  • 文/不壞的土叔 我叫張陵擒滑,是天一觀的道長腐晾。 經(jīng)常有香客問我,道長丐一,這世上最難降的妖魔是什么藻糖? 我笑而不...
    開封第一講書人閱讀 58,242評論 1 292
  • 正文 為了忘掉前任,我火速辦了婚禮库车,結(jié)果婚禮上巨柒,老公的妹妹穿的比我還像新娘。我一直安慰自己柠衍,他們只是感情好洋满,可當我...
    茶點故事閱讀 67,269評論 6 389
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著拧略,像睡著了一般芦岂。 火紅的嫁衣襯著肌膚如雪瘪弓。 梳的紋絲不亂的頭發(fā)上垫蛆,一...
    開封第一講書人閱讀 51,215評論 1 299
  • 那天,我揣著相機與錄音腺怯,去河邊找鬼袱饭。 笑死,一個胖子當著我的面吹牛呛占,可吹牛的內(nèi)容都是我干的虑乖。 我是一名探鬼主播,決...
    沈念sama閱讀 40,096評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼晾虑,長吁一口氣:“原來是場噩夢啊……” “哼疹味!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起帜篇,我...
    開封第一講書人閱讀 38,939評論 0 274
  • 序言:老撾萬榮一對情侶失蹤糙捺,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后笙隙,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體洪灯,經(jīng)...
    沈念sama閱讀 45,354評論 1 311
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,573評論 2 333
  • 正文 我和宋清朗相戀三年竟痰,在試婚紗的時候發(fā)現(xiàn)自己被綠了签钩。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,745評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡坏快,死狀恐怖铅檩,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情莽鸿,我是刑警寧澤昧旨,帶...
    沈念sama閱讀 35,448評論 5 344
  • 正文 年R本政府宣布,位于F島的核電站,受9級特大地震影響臼予,放射性物質(zhì)發(fā)生泄漏鸣戴。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 41,048評論 3 327
  • 文/蒙蒙 一粘拾、第九天 我趴在偏房一處隱蔽的房頂上張望窄锅。 院中可真熱鬧,春花似錦缰雇、人聲如沸入偷。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,683評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽疏之。三九已至,卻和暖如春暇咆,著一層夾襖步出監(jiān)牢的瞬間锋爪,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,838評論 1 269
  • 我被黑心中介騙來泰國打工爸业, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留其骄,地道東北人。 一個月前我還...
    沈念sama閱讀 47,776評論 2 369
  • 正文 我出身青樓扯旷,卻偏偏與公主長得像拯爽,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子钧忽,可洞房花燭夜當晚...
    茶點故事閱讀 44,652評論 2 354

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