HashMap及ConcurrentHashMap源碼分析

HashMap

hashMap1.7的數(shù)據(jù)結(jié)構(gòu)

1.7的結(jié)構(gòu)如下圖,底層是一個(gè)大的Entry數(shù)組,每個(gè)數(shù)組元素為一個(gè)鏈表。圖中同時(shí)可以看出put和get的流程查库。下面對(duì)put和get的部分代碼用圖示方式展示,同時(shí)可以參考源碼自己分析黄琼。

HashMap1.7.png

put方法源碼

public V put(K key, V value) {
        if (table == EMPTY_TABLE) {
            // 初始化桶
            inflateTable(threshold);
        }
        if (key == null)
            return putForNullKey(value);
        int hash = hash(key);
        int i = indexFor(hash, table.length);
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }

        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

void addEntry(int hash, K key, V value, int bucketIndex) {
        if ((size >= threshold) && (null != table[bucketIndex])) {
            // 此處擴(kuò)容
            resize(2 * table.length);
            hash = (null != key) ? hash(key) : 0;
            bucketIndex = indexFor(hash, table.length);
        }
        // 創(chuàng)建鍵值對(duì)并加入map中
        createEntry(hash, key, value, bucketIndex);
    }

void createEntry(int hash, K key, V value, int bucketIndex) {
        Entry<K,V> e = table[bucketIndex];
        table[bucketIndex] = new Entry<>(hash, key, value, e);
        size++;
    }

get方法源碼

public V get(Object key) {
        if (key == null)
            return getForNullKey();
        Entry<K,V> entry = getEntry(key);

        return null == entry ? null : entry.getValue();
    }

hashMap1.8的數(shù)據(jù)結(jié)構(gòu)

1.8的數(shù)據(jù)結(jié)構(gòu)如下圖樊销,同時(shí)跟1.7一樣,put個(gè)get操作的大體流程也繪制在圖中了。朋友們可以對(duì)照著源碼和圖自行消化一下围苫。


HashMap 1.8 的數(shù)據(jù)結(jié)構(gòu).png

老規(guī)矩裤园,源碼說(shuō)話。

put方法

public V put(K key, V value) {
        // 先計(jì)算hashcode剂府,key為0時(shí)直接返回0
        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)建Map時(shí)并未初始化table拧揽,第一次put時(shí)先進(jìn)行初始化操作  
        if ((tab = table) == null || (n = tab.length) == 0)
            // 初始化也是通過(guò)resize來(lái)實(shí)現(xiàn)的
            n = (tab = resize()).length;
        // 根據(jù)hashcode和table長(zhǎng)度計(jì)算index,確定對(duì)應(yīng)index下是否已經(jīng)有值腺占。
        if ((p = tab[i = (n - 1) & hash]) == null只
            // 為空時(shí)直接創(chuàng)建Node并插入
            tab[i] = newNode(hash, key, value, null);
        else {
            // 否則先判斷key是否與表頭元素相同淤袜,相同則直接返回node節(jié)點(diǎn)
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            // 不同時(shí)判斷是否為樹(shù)節(jié)點(diǎn),若為樹(shù)節(jié)點(diǎn)則通過(guò)紅黑樹(shù)插入元素
            else if (p instanceof TreeNode)
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                // 不是樹(shù)節(jié)點(diǎn)說(shuō)明還是鏈表湾笛,遍歷鏈表
                for (int binCount = 0; ; ++binCount) {
                    // 判斷是否為鏈尾,鏈尾的話直接插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        // 插入元素后判斷元素個(gè)數(shù)是否超過(guò)閾值闰歪,超過(guò)則將鏈表轉(zhuǎn)成紅黑樹(shù)
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);
                        break;
                    }
                    // 不是鏈尾就繼續(xù)判斷是否和key相同嚎研,相同則將node返回
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            // 如果改key已經(jīng)存在,則根據(jù)onlyIfAbsent參數(shù)或舊值是否為空判斷是否要覆蓋元素
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        // 修改modCount
        ++modCount;
        // 修改map的size并判斷是否需要擴(kuò)容
        if (++size > threshold)
            // 擴(kuò)容
            resize();
        afterNodeInsertion(evict);
        return null;
    }

get方法

public V get(Object key) {
        Node<K,V> e;
        // 同樣還是先計(jì)算hashcode库倘,然后通過(guò)getNode返回的節(jié)點(diǎn)獲取value
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        // 當(dāng)map不為空且根據(jù)hash與table.length計(jì)算得到的index處元素不為空時(shí)
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            // 這里判斷頭元素是否與給定key相同临扮,相同就返回該node
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            // 如果不是尾節(jié)點(diǎn)
            if ((e = first.next) != null) {
                // 為紅黑樹(shù)時(shí)調(diào)用紅黑樹(shù)的方法獲取元素
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                // 否則遍歷鏈表獲取指定key的元素
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

HashMap 1.7和1.8的區(qū)別

主要有如下幾點(diǎn)區(qū)別:

  • 1.7與1.8在數(shù)據(jù)結(jié)構(gòu)上來(lái)說(shuō)底層都是一個(gè)大數(shù)組來(lái)存儲(chǔ),唯一的區(qū)別是數(shù)組的每個(gè)元素類型不同教翩,1.7下是一個(gè)鏈表杆勇。1.8為了優(yōu)化鏈表的檢索速度將數(shù)組其結(jié)構(gòu)改成了鏈表+紅黑樹(shù)。默認(rèn)情況下在鏈表長(zhǎng)度大于等于8時(shí)會(huì)將鏈表轉(zhuǎn)成紅黑樹(shù)饱亿,在長(zhǎng)度小于等于6時(shí)會(huì)退回鏈表蚜退。

  • 在put時(shí)1.7采用的是頭插法,而1.8采用的是尾插法彪笼。感興趣的朋友可以繼續(xù)深入看看為什么會(huì)有這種修改钻注。

  • 1.7的擴(kuò)容發(fā)生在addEntry之前,而1.8的擴(kuò)容發(fā)生在put結(jié)束之后配猫。

如果還有其他的區(qū)別還請(qǐng)大家和我聯(lián)系幅恋,我會(huì)補(bǔ)充上去。

ConcurrentHashMap

ConcurrentHashMap1.7的數(shù)據(jù)結(jié)構(gòu)

1.7中ConcurrentHashMap采用了分段鎖+Entry數(shù)組的結(jié)構(gòu)泵肄,每個(gè)Segment其實(shí)是ReentrantLock的子類捆交。因此天然擁有加鎖的功能,其數(shù)據(jù)結(jié)構(gòu)如下圖腐巢。

ConcurrentHashMap1.7.png

1.7中的put和get流程如上圖所示品追。其實(shí)并不復(fù)雜,由于表示數(shù)據(jù)的幾個(gè)關(guān)鍵變量都被volatile修飾冯丙。因此大部分操作不需要加鎖诵盼,僅在put時(shí)對(duì)所操作的分段加鎖。get操作不加鎖,size方法視具體情況而定风宁,下面單獨(dú)分析洁墙。

ConcurrentHashMap1.7的幾處關(guān)鍵代碼

初始化ConcurrentHashMap時(shí)確定分段大小即其他分段參數(shù)。

    public ConcurrentHashMap(){
        // ...省略其他代碼
        int sshift = 0;
        // 分段大小
        int ssize = 1;
        // 默認(rèn)concurrencyLevel是16戒财,這里ssize每次 * 2热监,即循環(huán)可以執(zhí)行4次,此時(shí)sshift=4饮寞,ssize = 16
        while (ssize < concurrencyLevel) {
            ++sshift;
            ssize <<= 1;
        }
        // 從上方計(jì)算結(jié)果可以得到孝扛,segmentShift = 28
        this.segmentShift = 32 - sshift;
        // segmentMark = 15
        this.segmentMask = ssize - 1;
        // ...省略其他代碼
        // create segments and segments[0]
        Segment<K,V> s0 =
            new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
                             (HashEntry<K,V>[])new HashEntry[cap]);
        Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
        UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
        this.segments = ss;
    }

segments數(shù)組的大小僅在上述初始化創(chuàng)建代碼中確定,一旦map創(chuàng)建成功后分段個(gè)數(shù)不會(huì)改變幽崩,每次擴(kuò)容也只針對(duì)某個(gè)分段內(nèi)的桶進(jìn)行擴(kuò)容苦始。

put方法

public V put(K key, V value) {
        Segment<K,V> s;
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key);
        // 通過(guò)segmentShift和segmentMask計(jì)算key所在的分段位置
        int j = (hash >>> segmentShift) & segmentMask;
        // 如果分段尚未初始化(==null),則初始化該分段(即使用第一分段為原型創(chuàng)建新對(duì)象)
        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck
             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment
            s = ensureSegment(j);
        // 委托給分段的put方法
        return s.put(key, hash, value, false);
    }

private Segment<K,V> ensureSegment(int k) {
        final Segment<K,V>[] ss = this.segments;
        long u = (k << SSHIFT) + SBASE; // raw offset
        Segment<K,V> seg;
        if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
            // 使用第一個(gè)分段作為原型
            Segment<K,V> proto = ss[0]; // use segment 0 as prototype
            int cap = proto.table.length;
            float lf = proto.loadFactor;
            int threshold = (int)(cap * lf);
            HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
            if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                == null) { // recheck
                Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
                while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
                       == null) {
                    if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
                        break;
                }
            }
        }
        return seg;
    }

final V put(K key, int hash, V value, boolean onlyIfAbsent) {
            // 嘗試獲取鎖,這里肯定能拿到鎖慌申,否則會(huì)掛起陌选,直到拿到鎖為止
            HashEntry<K,V> node = tryLock() ? null :
                scanAndLockForPut(key, hash, value);
            V oldValue;
            try {
                HashEntry<K,V>[] tab = table;
                // scanAndLockForPut方法中獲取node節(jié)點(diǎn)時(shí)bucket的index計(jì)算方法與此處計(jì)算方法不同,下面對(duì)node進(jìn)行操作時(shí)有什么影響蹄溉?
                int index = (tab.length - 1) & hash;
                HashEntry<K,V> first = entryAt(tab, index);
                for (HashEntry<K,V> e = first;;) {
                    if (e != null) {
                        K k;
                        if ((k = e.key) == key ||
                            (e.hash == hash && key.equals(k))) {
                            oldValue = e.value;
                            if (!onlyIfAbsent) {
                                e.value = value;
                                ++modCount;
                            }
                            break;
                        }
                        e = e.next;
                    }
                    else {
                        // node不為null說(shuō)明獲取鎖的時(shí)候創(chuàng)建了node對(duì)象咨油,直接將node插入表頭即可
                        if (node != null)
                            node.setNext(first);
                        else
                            node = new HashEntry<K,V>(hash, key, value, first);
                        int c = count + 1;
                        // 判斷是否需要擴(kuò)容
                        if (c > threshold && tab.length < MAXIMUM_CAPACITY)
                            rehash(node);
                        else
                            setEntryAt(tab, index, node);
                        ++modCount;
                        count = c;
                        oldValue = null;
                        break;
                    }
                }
            } finally {
                // 釋放鎖
                unlock();
            }
            return oldValue;
        }

get方法

 public V get(Object key) {
        Segment<K,V> s; // manually integrate access methods to reduce overhead
        HashEntry<K,V>[] tab;
        int h = hash(key);
        long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
        if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
            (tab = s.table) != null) {
            for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
                     (tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
                 e != null; e = e.next) {
                K k;
                if ((k = e.key) == key || (e.hash == h && key.equals(k)))
                    return e.value;
            }
        }
        return null;
    }

size方法

public int size() {
        // Try a few times to get accurate count. On failure due to
        // continuous async changes in table, resort to locking.
        final Segment<K,V>[] segments = this.segments;
        int size;
        boolean overflow; // true if size overflows 32 bits
        long sum;         // sum of modCounts
        long last = 0L;   // previous sum
        int retries = -1; // first iteration isn't retry
        try {
            for (;;) {
                // RETRIES_BEFORE_LOCK默認(rèn)為2,說(shuō)明先嘗試3次柒爵,如果其中連續(xù)兩次結(jié)果一樣則直接返回役电。如果沒(méi)有則對(duì)所有分段加鎖,在計(jì)算棉胀。隨后解鎖
                if (retries++ == RETRIES_BEFORE_LOCK) {
                    for (int j = 0; j < segments.length; ++j)
                        ensureSegment(j).lock(); // force creation
                }
                sum = 0L;
                size = 0;
                overflow = false;
                for (int j = 0; j < segments.length; ++j) {
                    Segment<K,V> seg = segmentAt(segments, j);
                    if (seg != null) {
                        sum += seg.modCount;
                        int c = seg.count;
                        // 如果大小溢出的話標(biāo)識(shí)位設(shè)為true
                        if (c < 0 || (size += c) < 0)
                            overflow = true;
                    }
                }
                // last用來(lái)記錄上次循環(huán)的計(jì)算結(jié)果法瑟,sum為本次循環(huán)的計(jì)算結(jié)果。如果連續(xù)兩次結(jié)果一致則退出循環(huán)
                if (sum == last)
                    break;
                last = sum;
            }
        } finally {
            // 如果重試次數(shù)超過(guò)加鎖所需的次數(shù)唁奢,則對(duì)所有分段解鎖
            if (retries > RETRIES_BEFORE_LOCK) {
                for (int j = 0; j < segments.length; ++j)
                    segmentAt(segments, j).unlock();
            }
        }
        // 如果溢出則返回Integer.MAX_VALUE瓢谢,否則返回正確size
        return overflow ? Integer.MAX_VALUE : size;
    }

ConcurrentHashMap1.8的數(shù)據(jù)結(jié)構(gòu)

未完待續(xù)

ConcurrentHashMap與hashtable的區(qū)別

未完待續(xù)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市驮瞧,隨后出現(xiàn)的幾起案子氓扛,更是在濱河造成了極大的恐慌,老刑警劉巖论笔,帶你破解...
    沈念sama閱讀 221,635評(píng)論 6 515
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件采郎,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡狂魔,警方通過(guò)查閱死者的電腦和手機(jī)蒜埋,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,543評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)最楷,“玉大人整份,你說(shuō)我怎么就攤上這事待错。” “怎么了烈评?”我有些...
    開(kāi)封第一講書人閱讀 168,083評(píng)論 0 360
  • 文/不壞的土叔 我叫張陵火俄,是天一觀的道長(zhǎng)。 經(jīng)常有香客問(wèn)我讲冠,道長(zhǎng)瓜客,這世上最難降的妖魔是什么? 我笑而不...
    開(kāi)封第一講書人閱讀 59,640評(píng)論 1 296
  • 正文 為了忘掉前任竿开,我火速辦了婚禮谱仪,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘否彩。我一直安慰自己疯攒,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 68,640評(píng)論 6 397
  • 文/花漫 我一把揭開(kāi)白布列荔。 她就那樣靜靜地躺著敬尺,像睡著了一般。 火紅的嫁衣襯著肌膚如雪肌毅。 梳的紋絲不亂的頭發(fā)上筷转,一...
    開(kāi)封第一講書人閱讀 52,262評(píng)論 1 308
  • 那天姑原,我揣著相機(jī)與錄音悬而,去河邊找鬼。 笑死锭汛,一個(gè)胖子當(dāng)著我的面吹牛笨奠,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播唤殴,決...
    沈念sama閱讀 40,833評(píng)論 3 421
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼般婆,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了朵逝?” 一聲冷哼從身側(cè)響起蔚袍,我...
    開(kāi)封第一講書人閱讀 39,736評(píng)論 0 276
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎配名,沒(méi)想到半個(gè)月后,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,280評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡茴她,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,369評(píng)論 3 340
  • 正文 我和宋清朗相戀三年档叔,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片芋膘。...
    茶點(diǎn)故事閱讀 40,503評(píng)論 1 352
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡鳞青,死狀恐怖霸饲,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情臂拓,我是刑警寧澤厚脉,帶...
    沈念sama閱讀 36,185評(píng)論 5 350
  • 正文 年R本政府宣布,位于F島的核電站埃儿,受9級(jí)特大地震影響器仗,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜童番,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,870評(píng)論 3 333
  • 文/蒙蒙 一精钮、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧剃斧,春花似錦轨香、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書人閱讀 32,340評(píng)論 0 24
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至根蟹,卻和暖如春脓杉,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背简逮。 一陣腳步聲響...
    開(kāi)封第一講書人閱讀 33,460評(píng)論 1 272
  • 我被黑心中介騙來(lái)泰國(guó)打工球散, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人散庶。 一個(gè)月前我還...
    沈念sama閱讀 48,909評(píng)論 3 376
  • 正文 我出身青樓蕉堰,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親悲龟。 傳聞我的和親對(duì)象是個(gè)殘疾皇子屋讶,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,512評(píng)論 2 359

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