ConcurrentHashMap

thollych 2012-01-14

展開(kāi)全文

曾經(jīng)研究過(guò)jkd1.5新特性,，其中ConcurrentHashMap就是其中之一,，其特點(diǎn)：效率比Hashtable高，并發(fā)性比hashmap好,。結(jié)合了兩者的特點(diǎn),。
集合是編程中最常用的數(shù)據(jù)結(jié)構(gòu),。而談到并發(fā)，幾乎總是離不開(kāi)集合這類(lèi)高級(jí)數(shù)據(jù)結(jié)構(gòu)的支持,。比如兩個(gè)線程需要同時(shí)訪問(wèn)一個(gè)中間臨界區(qū)（Queue）,，比如常會(huì)用緩存作為外部文件的副本（HashMap）。這篇文章主要分析jdk1.5的3種并發(fā)集合類(lèi)型（concurrent,，copyonright,，queue）中的ConcurrentHashMap，讓我們從原理上細(xì)致的了解它們,，能夠讓我們?cè)谏疃软?xiàng)目開(kāi)發(fā)中獲益非淺,。

在tiger之前，我們使用得最多的數(shù)據(jù)結(jié)構(gòu)之一就是 HashMap和Hashtable,。大家都知道,，HashMap中未進(jìn)行同步考慮，而Hashtable則使用了synchronized,，帶來(lái)的直接影響就是可選擇,，我們可以在單線程時(shí)使用HashMap提高效率，而多線程時(shí)用Hashtable來(lái)保證安全,。

當(dāng)我們享受著jdk帶來(lái)的便利時(shí)同樣承受它帶來(lái)的不幸惡果,。通過(guò)分析Hashtable就知道，synchronized是針對(duì)整張Hash表的,，即每次鎖住整張表讓線程獨(dú)占,，安全的背后是巨大的浪費(fèi)，慧眼獨(dú)具的Doug Lee立馬拿出了解決方案----ConcurrentHashMap,。

ConcurrentHashMap和Hashtable主要區(qū)別就是圍繞著鎖的粒度以及如何鎖。如圖

左邊便是Hashtable的實(shí)現(xiàn)方式---鎖整個(gè)hash表,；而右邊則是ConcurrentHashMap的實(shí)現(xiàn)方式---鎖桶（或段）,。 ConcurrentHashMap將hash表分為16個(gè)桶（默認(rèn)值），諸如get,put,remove等常用操作只鎖當(dāng)前需要用到的桶,。試想,，原來(lái)只能一個(gè)線程進(jìn)入，現(xiàn)在卻能同時(shí)16個(gè)寫(xiě)線程進(jìn)入（寫(xiě)線程才需要鎖定,，而讀線程幾乎不受限制,，之后會(huì)提到），并發(fā)性的提升是顯而易見(jiàn)的,。

更令人驚訝的是ConcurrentHashMap的讀取并發(fā),，因?yàn)樵谧x取的大多數(shù)時(shí)候都沒(méi)有用到鎖定，所以讀取操作幾乎是完全的并發(fā)操作,，而寫(xiě)操作鎖定的粒度又非常細(xì),，比起之前又更加快速（這一點(diǎn)在桶更多時(shí)表現(xiàn)得更明顯些）,。只有在求size等操作時(shí)才需要鎖定整個(gè)表。而在迭代時(shí),，ConcurrentHashMap使用了不同于傳統(tǒng)集合的快速失敗迭代器（見(jiàn)之前的文章《JAVA API備忘---集合》）的另一種迭代方式,，我們稱(chēng)為弱一致迭代器。在這種迭代方式中,，當(dāng)iterator被創(chuàng)建后集合再發(fā)生改變就不再是拋出 ConcurrentModificationException,，取而代之的是在改變時(shí)new新的數(shù)據(jù)從而不影響原有的數(shù)據(jù)，iterator完成后再將頭指針替換為新的數(shù)據(jù),，這樣iterator線程可以使用原來(lái)老的數(shù)據(jù),，而寫(xiě)線程也可以并發(fā)的完成改變，更重要的,，這保證了多個(gè)線程并發(fā)執(zhí)行的連續(xù)性和擴(kuò)展性,，是性能提升的關(guān)鍵。

接下來(lái),，讓我們看看ConcurrentHashMap中的幾個(gè)重要方法,，心里知道了實(shí)現(xiàn)機(jī)制后，使用起來(lái)就更加有底氣,。

ConcurrentHashMap中主要實(shí)體類(lèi)就是三個(gè)：ConcurrentHashMap（整個(gè)Hash表）,Segment（桶）,，HashEntry（節(jié)點(diǎn)），對(duì)應(yīng)上面的圖可以看出之間的關(guān)系,。

get 方法（請(qǐng)注意,，這里分析的方法都是針對(duì)桶的，因?yàn)镃oncurrentHashMap的最大改進(jìn)就是將粒度細(xì)化到了桶上）,，首先判斷了當(dāng)前桶的數(shù)據(jù)個(gè)數(shù)是否為0,，為0自然不可能get到什么，只有返回null,，這樣做避免了不必要的搜索,，也用最小的代價(jià)避免出錯(cuò)。然后得到頭節(jié)點(diǎn)（方法將在下面涉及）之后就是根據(jù)hash和key逐個(gè)判斷是否是指定的值,，如果是并且值非空就說(shuō)明找到了,，直接返回；程序非常簡(jiǎn)單,，但有一個(gè)令人困惑的地方,，這句return readValueUnderLock(e)到底是用來(lái)干什么的呢？研究它的代碼,，在鎖定之后返回一個(gè)值,。但這里已經(jīng)有一句V v = e.value得到了節(jié)點(diǎn)的值，這句return readValueUnderLock(e)是否多此一舉,？事實(shí)上,，這里完全是為了并發(fā)考慮的,，這里當(dāng)v為空時(shí)，可能是一個(gè)線程正在改變節(jié)點(diǎn),，而之前的 get操作都未進(jìn)行鎖定,，根據(jù)bernstein條件，讀后寫(xiě)或?qū)懞笞x都會(huì)引起數(shù)據(jù)的不一致,，所以這里要對(duì)這個(gè)e重新上鎖再讀一遍,，以保證得到的是正確值，這里不得不佩服Doug Lee思維的嚴(yán)密性,。整個(gè)get操作只有很少的情況會(huì)鎖定,，相對(duì)于之前的Hashtable，并發(fā)是不可避免的??！

        V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

        V readValueUnderLock(HashEntry e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

put 操作一上來(lái)就鎖定了整個(gè)segment，這當(dāng)然是為了并發(fā)的安全,，修改數(shù)據(jù)是不能并發(fā)進(jìn)行的,，必須得有個(gè)判斷是否超限的語(yǔ)句以確保容量不足時(shí)能夠 rehash，而比較難懂的是這句int index = hash & (tab.length - 1),，原來(lái)segment里面才是真正的hashtable,，即每個(gè)segment是一個(gè)傳統(tǒng)意義上的hashtable,如上圖，從兩者的結(jié)構(gòu)就可以看出區(qū)別,，這里就是找出需要的entry在table的哪一個(gè)位置,，之后得到的entry就是這個(gè)鏈的第一個(gè)節(jié)點(diǎn)，如果e!=null,，說(shuō)明找到了,，這是就要替換節(jié)點(diǎn)的值（onlyIfAbsent == false），否則,，我們需要new一個(gè)entry,，它的后繼是first，而讓tab[index]指向它,，什么意思呢,？實(shí)際上就是將這個(gè)新entry 插入到鏈頭,，剩下的就非常容易理解了,。

        V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();
            try {
                int c = count;
                if (c++ > threshold) // ensure capacity
                    rehash();
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = (HashEntry) tab[index];
                HashEntry e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {
                    oldValue = e.value;
                    if (!onlyIfAbsent)
                        e.value = value;
                }
                else {
                    oldValue = null;
                    ++modCount;
                    tab[index] = new HashEntry(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

remove 操作非常類(lèi)似put，但要注意一點(diǎn)區(qū)別,，中間那個(gè)for循環(huán)是做什么用的呢,？（*號(hào)標(biāo)記）從代碼來(lái)看，就是將定位之后的所有entry克隆并拼回前面去,，但有必要嗎,？每次刪除一個(gè)元素就要將那之前的元素克隆一遍,？這點(diǎn)其實(shí)是由entry的不變性來(lái)決定的，仔細(xì)觀察entry定義,，發(fā)現(xiàn)除了value,，其他所有屬性都是用final來(lái)修飾的，這意味著在第一次設(shè)置了next域之后便不能再改變它,，取而代之的是將它之前的節(jié)點(diǎn)全都克隆一次,。至于entry為什么要設(shè)置為不變性，這跟不變性的訪問(wèn)不需要同步從而節(jié)省時(shí)間有關(guān),，關(guān)于不變性的更多內(nèi)容,，請(qǐng)參閱之前的文章《線程高級(jí)---線程的一些編程技巧》

        V remove(Object key, int hash, Object value) {
            lock();
            try {
                int c = count - 1;
                HashEntry[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry first = (HashEntry)tab[index];
                HashEntry e = first;
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue = null;
                if (e != null) {
                    V v = e.value;
                    if (value == null || value.equals(v)) {
                        oldValue = v;
                        // All entries following removed node can stay
                        // in list, but all preceding ones need to be
                        // cloned.
                        ++modCount;
                        HashEntry newFirst = e.next;
                    *    for (HashEntry p = first; p != e; p = p.next)
                    *        newFirst = new HashEntry(p.key, p.hash,
                                                          newFirst, p.value);
                        tab[index] = newFirst;
                        count = c; // write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }

    static final class HashEntry {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry next;

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

本站是提供個(gè)人知識(shí)管理的網(wǎng)絡(luò)存儲(chǔ)空間，所有內(nèi)容均由用戶發(fā)布,，不代表本站觀點(diǎn),。請(qǐng)注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購(gòu)買(mǎi)等信息,，謹(jǐn)防詐騙,。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請(qǐng)點(diǎn)擊一鍵舉報(bào),。

轉(zhuǎn)藏 分享

QQ空間 QQ好友新浪微博微信

獻(xiàn)花（0） +1

來(lái)自： thollych > 《我的圖書(shū)館》

舉報(bào)/認(rèn)領(lǐng)