CopyOWriteArayListとCocurrenthashMapの原理解析

8654 ワード
Java
CopyOWriteArayList
この二つは非常によく使われている合併類で、まずCopyOWriteArayListから話します。このクラスは名前からも分かるように、彼は書き込み作業中にコピーしていますので、他のスレッドの読み取り操作時には問題が発生しません。その実現も簡単です。簡単なソースコードを見に来ました。
public boolean add(E e) {
    final ReentrantLock lock = this.lock;
    lock.lock();
    try {
        Object[] elements = getArray();
        int len = elements.length;
        Object[] newElements = Arrays.copyOf(elements, len + 1);
        newElements[len] = e;
        setArray(newElements);
        return true;
    } finally {
        lock.unlock();
    }
}
は、add動作を行うときに、まずロックをかけて、配列内容を新しい配列にコピーし、その後、新しい配列上でadd動作を行う。操作が終わったら古い配列の針を新しい配列に向けてロックを解除します。
public E get(int index) {
    return get(getArray(), index);
}
get操作はチェーンブロックがなくなり、とても簡単です。
CopyOWriteArayListは「読み書き分離」という非常に重要な思想を体現しています。読み操作は頻繁ですが、書く操作は少ないです。
完璧ではないです。栗を挙げます。
package com.app.JavaMaven;/**
 * Created by Tim on 2017/7/13.
 */

import java.util.List;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * create by    
 */
public class CopyOnWriteArrayListTest {

    @org.junit.Test
    public void test() {
        final List list = new CopyOnWriteArrayList();
        for (int i = 0; i < 100; i++)
            list.add(i);


        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                        System.out.println(list.get(list.size()-1));
                }
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true) {
                    for (int i = 0; i < list.size(); i++)
                        list.remove(list.size() - 1);
                }
            }
        }).start();

        while (true) ;

    }
}
このような情況の下で分に分けて組を投げて境界を越えました。
コンカレントHashMap:
次にもう一つ話します。ConcerenthashMapはもう一つの非常に重要な思想を表しています。それはセグメントロックです。これはHashtableに比べて、最適化されている点は、配列全体をロックするのではなく、セグメント化されたロックを行うことです。
まずいくつかのよくあるロックの最適化案を紹介します。
ロック範囲を狭める
最適化前
public synchronized void synchronizedOnMethod(){ //          synchronized,           
           prefix();
           try {
               TimeUnit.SECONDS.sleep(1);
           }catch (InterruptedException e){
           }
           post();
       }
       private void post(){
           try {
               TimeUnit.SECONDS.sleep(1);
           }catch (InterruptedException e){
           }
       }
       private void prefix(){
           try {
               TimeUnit.SECONDS.sleep(1);
           }catch (InterruptedException e){
           }
       }
   }
最適化後
//  prefix post        （       ）
static class SynchronizedClazz{
        public void mineSynOnMethod(){
            prefix();
            synchronized (this){ //synchronized            
                try {
                    TimeUnit.SECONDS.sleep(1);
                }catch (InterruptedException e){
                }
            }
            post();
        }
分離ロック
最適化前
static class DecomposeClazz{
        private final Set allUsers = new HashSet();
        private final Set allComputers = new HashSet();
        
        public synchronized void addUser(String user){ //     
            allUsers.add(user);
        }
        
        public synchronized void addComputer(String computer){
            allComputers.add(computer);
        }
    }
最適化後
static class DecompossClazz2{
        private final Set allUsers = new HashSet();
        private final Set allComputers = new HashSet();
        public void addUser(String user){ //      
            synchronized (allUsers){
                allUsers.add(user);
            }
        }
        public void addComputer(String computer){
            synchronized (allComputers){
                allComputers.add(computer);
            }
        }
    }
セグメントロック
package com.app.JavaMaven;/**
 * Created by Tim on 2017/7/13.
 */

import java.util.HashMap;
import java.util.Map;

/**
 * create by    
 */
public class ConcurrentHashMapTest {

    @org.junit.Test
    public void test() {
        final MyConcurrentHashMap map = new MyConcurrentHashMap();

//        Map map = new HashMap();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true)
                    map.put("100", "100");
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true)
                    map.put("100", null);
            }
        }).start();

        new Thread(new Runnable() {
            @Override
            public void run() {
                while (true)
                    if (map.get("100") == null)
                        System.out.println(map.get("100"));
            }
        }).start();

        while (true) ;

    }
}

class MyConcurrentHashMap {
    private final int LOCK_COUNT = 16;
    private final Map map;
    private final Object[] locks;

    public MyConcurrentHashMap() {
        this.map = new HashMap();
        locks = new Object[LOCK_COUNT];
        for (int i = 0; i < LOCK_COUNT; i++) {
            locks[i] = new Object();
        }
    }

    private int keyHashCode(K k) {
        return Math.abs(k.hashCode() % LOCK_COUNT);
    }

    public V get(K k) {
        int keyHashCode = keyHashCode(k);
        synchronized (locks[keyHashCode % LOCK_COUNT]) {
            return map.get(k);
        }
    }

    public V put(K k, V v) {
        int keyHashCode = keyHashCode(k);
        synchronized (locks[keyHashCode % LOCK_COUNT]) {
            return map.put(k, v);
        }
    }

}
自分で実現したシンプルなConcerenthashMapは、jdkとはかなり違っています。でも大体原理を反映できます。
初期化
着信パラメータはinitial Capacity、loadFactor、concurrencyLevelの3つです。initial Capacityは新しく作成されたこのConcerenthashMapの初期容量、つまり上の構造図のEnttryの数を表しています。デフォルト値はstatic final int DEFAULT_INITIA_.CAPACITY=16
loadFactorは負荷因子を表しています。つまり、ConcerenthashMapの要素の個数がloadFactor*の最大容量より大きい場合、rehashが必要です。デフォルト値はstatic final float DEFAULT_です。LOAD_FACTOR=0.75 f
concurrencyLevelは、同時にレベルを表し、この値はSegmentの個数を決定するために用いられ、Segmentの個数は、concurrencyLevelの最初の2つのn乗の数より大きい。例えば、concurrencyLevelが12、13、14、15、16のこれらの数であれば、Segmentの数は16（2の4乗）である。デフォルト値はstatic final int DEFAULT_CONCURRENCY_LEVEL=16理想的には、コンカレントHashMapの真の同時アクセスがconcurrencyLevelに達することができます。concurrencyLevel Segmentがあるので、コンカレントcyLevelスレッドがあればMapにアクセスする必要があります。また、アクセスが必要なデータはそれぞれ異なるSegmentに落ちます。これらのスレッドは競争なく自由にアクセスできます。同時に訪問する効果があります。これもなぜこのパラメータが「併発レベル」と名付けられたのかという理由です。
JDK 1.8の変更
改善の一つ：segmentsフィールドをキャンセルして、直接にtranient volatile Hash Enty tableでデータを保存して、table配列要素をロックとして採用して、それによって各行のデータにロックをかけて、さらに同時に衝突する確率を減らすことができます。改善二：元のケーブル配列＋一方向チェーンのデータ構造を、テーブル配列＋一方向チェーン＋レッドツリーの構造に変更します。hashテーブルにとって、最も核心的な能力は、key hashの後を配列に均等に分布させることである。hashの後にハッシュが均一であれば、テーブル配列の各列の長さは主に0または1である。しかし、いつも理想的ではなく、ConcerenthashMap類のデフォルトのローディング係数は0.75ですが、データ量が多すぎたり、運が悪い場合は、列の長さが長すぎる場合もあります。一方通行のリスト方式を採用している場合は、あるノードの時間の複雑さがO（n）であることを確認します。したがって、8（デフォルト値）を超える数のリストに対して、Jdk 1.8では、赤と黒のツリーの構造が採用されているので、クエリの時間複雑さは、O（logN）に低減され、性能を向上させることができる。
StringBuiderとStrigBufferについてどれぐらい知っていますか？
Linuxにkettleを配置するJob