1

インタビューで、インタビュアーはコンカレント Hash Map とその機能について尋ねたので、詳しく説明しました。彼は、同時 HashMap 更新操作の場合、ConcurrentHashMap は Map 全体ではなく、Map の一部のみをロックすると述べました。

そこで彼は、更新操作中に ConcurrentHashMap が Map 全体ではなく Map の一部のみをロックすることを証明する簡単なプログラムを作成するように私に言いました。これができなかったので、これを達成する方法を教えてください。

4

1 に答える 1

4

インタビュアーは、次のような簡単な答えを期待していた可能性があります。

  • マップ全体がget/put操作で同期されている場合、ボトルネックは同期されたブロックになるため、スレッドを追加してもスループットは向上しません。次に、synchronizedMapを使用して、スレッドの追加が役に立たないことを示すコードを記述できます。
  • マップは複数のロックを使用し、マシンに複数のコアがあると想定しているため、スレッドを追加するとスループットが向上します

以下の例は、以下を出力します。

同期された1つのスレッド：30
同期された複数のスレッド：96
同時の1つのスレッド：219
同時の複数のスレッド：142

したがって、同期バージョンは、高い競合（16スレッド）では3倍以上遅くなりますが、同時バージョンは、単一スレッドの場合のほぼ2倍の速度です。

ConcurrentMapには、シングルスレッドの状況で無視できないオーバーヘッドがあることに注意することも興味深いです。

これは非常に工夫された例であり、マイクロベンチマークが原因で発生する可能性のあるすべての問題があります（最初の結果はとにかく破棄する必要があります）。しかし、それは何が起こるかについてのヒントを与えます。

public class Test1 {
    static final int SIZE = 1000000;
    static final int THREADS = 16;
    static final ExecutorService executor = Executors.newFixedThreadPool(THREADS);

    public static void main(String[] args) throws Exception{

        for (int i = 0; i < 10; i++) {
            System.out.println("Concurrent one thread");
            addSingleThread(new ConcurrentHashMap<Integer, Integer> ());
            System.out.println("Concurrent multiple threads");
            addMultipleThreads(new ConcurrentHashMap<Integer, Integer> ());
            System.out.println("Synchronized one thread");
            addSingleThread(Collections.synchronizedMap(new HashMap<Integer, Integer> ()));
            System.out.println("Synchronized multiple threads");
            addMultipleThreads(Collections.synchronizedMap(new HashMap<Integer, Integer> ()));
        }   
        executor.shutdown();
    }

    private static void addSingleThread(Map<Integer, Integer> map) {
        long start = System.nanoTime();
        for (int i = 0; i < SIZE; i++) {
            map.put(i, i);
        }
        System.out.println(map.size()); //use the result
        long end = System.nanoTime();
        System.out.println("time with single thread: " + (end - start) / 1000000);
    }

    private static void addMultipleThreads(final Map<Integer, Integer> map) throws Exception {
        List<Runnable> runnables = new ArrayList<> ();
        for (int i = 0; i < THREADS; i++) {
            final int start = i;
            runnables.add(new Runnable() {

                @Override
                public void run() {
                    //Trying to have one runnable by bucket
                    for (int j = start; j < SIZE; j += THREADS) {
                        map.put(j, j);
                    }
                }
            });
        }
        List<Future> futures = new ArrayList<> ();
        long start = System.nanoTime();
        for (Runnable r : runnables) {
            futures.add(executor.submit(r));
        }
        for (Future f : futures) {
            f.get();
        }
        System.out.println(map.size()); //use the result
        long end = System.nanoTime();
        System.out.println("time with multiple threads: " + (end - start) / 1000000);
    }
}
于 2013-02-27T18:19:39.210 に答える