java.util.concurrentバッグのソースコードは読みます.

10793 ワード

Java集合フレームにおけるMapタイプのデータ構造は非スレッドセキュリティであり、マルチスレッド環境で使用する場合は手動でスレッド同期を行う必要がある.したがって、java.util.co ncurrentパケットには、スレッドセキュリティバージョンのMapタイプのデータ構造が提供されている.この文章は主にConcerentMapインタフェースとそのHashバージョンの実現に注目しています.
ConcerentMapはMapインターフェースのサブインターフェースです.
public interface ConcurrentMap<K, V> extends Map<K, V>
Mapインターフェースに比べて、ConcerentMapは4つの方法が多いです.
1)putIfAbsent方法:もしkeyが存在しないなら、key-valueを追加する.方法はkeyに関連するvalueを返します.
V putIfAbsent(K key, V value);
2)Remove方法
boolean remove(Object key, Object value);
Mapインターフェースにもremove方法があります.
V remove(Object key);
ConccurrentMapのremove方法は元のvalueとパラメータの中のvalueが一致しているかどうかを比較する必要があります.一致しないと削除できません.
3)Replace方法:2つの重さがあります.
boolean replace(K key, V oldValue, V newValue);

V replace(K key, V value);
二つの重荷重の違いと2)の中の二つのremove方法の違いは似ています.もう一つの検査valueが一致します.
 
ConccurrentMapの多くの方法でマルチスレッドの中の重要な概念を見ることができます.compreの役割はvalueの整合性を保証するためです.
 
重要なシーンが来ました.ConcerenthashMap.
public class ConcurrentHashMap<K, V> extends AbstractMap<K, V>

        implements ConcurrentMap<K, V>, Serializable
ConccurrenthashMapとHashMapは似ていますが、ここで注目しているのはスレッドの安全、つまりどのようにロックをかけるかです.
HashMapには、Entry配列があり、Keyのhash値に基づいて配列長を取得し、配列の下に表示され、Enttryを見つけ、Entryチェーン全体を巡回し、equals比較でkeyのあるEntryを決定します.
ConcerenthashMapの基本思想はブロック分割方式でロックされ、分割ブロック数はパラメータ「concurrencyLevel」によって決定される(HashMapの「initial Capacity」と同様、実際のブロック数は最初のconcurrencyLevelの2より大きいn乗である).各ブロックはSegmentと呼ばれ、Segmentのインデックス方式はHashMapのEntryインデックス方式と一致しています.
Segmentにロックをかける方式は簡単で、直接SegmentをRentrantLockのサブクラスと定義します.同時にSegmentはまた特定の実現のhash tableです.
static final class Segment<K,V> extends ReentrantLock implements Serializable
ここではConcerenthashMapの読み書きにロックをかける方法を分析します.
まず操作類を読む方法です.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;

    }
読み込むときに呼び出すSegmentのロックを取得する方法ではなく、hash値でEntryに位置し、Entryのチェーンを巡回しているのが見えます.なぜここはロックをかけないですか?Hash Entryのコードを見れば分かります.
    static final class HashEntry<K,V> {

        final int hash;

        final K key;

        volatile V value;

        volatile HashEntry<K,V> next;
valueとnext属性はvolatile修饰符を持っているので、大胆で安心できる遍歴と比较ができます.
 
次に書き込み操作です.書き込み操作は必ずロックをかけます.Segmentはhash tableとして見られているので、ConcerenthashMapはSegmentの対応する書き込み方法をput、replaceなどを直接呼び出します.
たとえばputの方法
    public V put(K key, V value) {

        Segment<K,V> s;

        if (value == null)

            throw new NullPointerException();

        int hash = hash(key);

        int j = (hash >>> segmentShift) & segmentMask;

        if ((s = (Segment<K,V>)UNSAFE.getObject          // nonvolatile; recheck

             (segments, (j << SSHIFT) + SBASE)) == null) //  in ensureSegment

            s = ensureSegment(j);

        return s.put(key, hash, value, false);

    }
ここで直接にSegmentの対応に注目して操作方法を書けばいいです.各書き込み操作の方法の先頭にはこのようなコードがあります.
        final V remove(Object key, int hash, Object value) {

            if (!tryLock())

                scanAndLock(key, hash);
            HashEntry<K,V> node = tryLock() ? null :

                scanAndLockForPut(key, hash, value);
つまり、まずロックを取ってみて、成功すればロックをかけて操作を続けます.失敗すればscanAndLockまたはscanAndLockForPutを通じてロックを取得します.ここで注目されているポイントはこの2つの方法に移ります.
マルチスレッド環境のルールに従って、ロックの取得に失敗するとブロック待ち状態になります.この2つの方法の役割は似ているはずです.
        private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {

            HashEntry<K,V> first = entryForHash(this, hash);

            HashEntry<K,V> e = first;

            HashEntry<K,V> node = null;

            int retries = -1; // negative while locating node

            while (!tryLock()) {

                HashEntry<K,V> f; // to recheck first below

                if (retries < 0) {

                    if (e == null) {

                        if (node == null) // speculatively create node

                            node = new HashEntry<K,V>(hash, key, value, null);

                        retries = 0;

                    }

                    else if (key.equals(e.key))

                        retries = 0;

                    else

                        e = e.next;

                }

                else if (++retries > MAX_SCAN_RETRIES) {

                    lock();

                    break;

                }

                else if ((retries & 1) == 0 &&

                         (f = entryForHash(this, hash)) != first) {

                    e = first = f; // re-traverse if entry changed

                    retries = -1;

                }

            }

            return node;

        }
この二つの方法のロジック:待つ間に暇を見つけて、その準備をして、目的のイベントを探してください.新規のイベントなら、イベントを作成して、そして、もし大丈夫なら、ロック()で自分をブロックします.つまり、準備を整えて、待っています.
 
Segment自体はhash tableと見なされているので、必ずrehashに関する問題があります.hashMapのrehashに似ているので、ここで省略します.