21

HashMapを使用して状態を共有するアプリケーションに取り組んでいます。マルチスレッド環境で問題が発生することを単体テストで証明する必要があります。

シングルスレッド環境とマルチスレッド環境のHashMap両方でサイズと要素を確認することで、アプリケーションの状態を確認しようとしました。しかし、これは役に立たないようです。状態は常に同じです。

それを証明する、またはマップ上で操作を実行するアプリケーションが同時要求でうまく機能することを証明する他の方法はありますか?

4

11 に答える 11

6

マルチスレッド環境で問題が発生することを単体テストで証明する必要があります。

これを行うのは非常に困難です。競合状態を実証するのは非常に困難です。確かに、多数のスレッドで HashMap への書き込みと書き込みを行うプログラムを作成できvolatileますが、アプリケーションのロギング、フィールド、その他のロック、およびその他のタイミングの詳細により、特定のコードを強制的に失敗させることが非常に困難になる場合があります。

これは、ばかげた小さなHashMap失敗のテストケースです。のメモリ破損によりスレッドが無限ループに入るとタイムアウトするため、失敗しますHashMap。ただし、コア数やその他のアーキテクチャの詳細によっては、失敗しない場合があります。

@Test(timeout = 10000)
public void runTest() throws Exception {
    final Map<Integer, String> map = new HashMap<Integer, String>();
    ExecutorService pool = Executors.newFixedThreadPool(10);
    for (int i = 0; i < 10; i++) {
        pool.submit(new Runnable() {
            @Override
            public void run() {
                for (int i = 0; i < 10000; i++) {
                    map.put(i, "wow");
                }
            }
        });
    }
    pool.shutdown();
    pool.awaitTermination(Long.MAX_VALUE, TimeUnit.MILLISECONDS);
}
于 2013-08-30T22:10:13.947 に答える
5

それを証明する他の方法はありますか？

ドキュメンテーションを読んでみてはどうですか(そして強調された「必須」に注意してください):

複数のスレッドが同時にハッシュ マップにアクセスし、少なくとも 1 つのスレッドがマップを構造的に変更する場合は、外部で同期する必要があります。

正しくない動作を示す単体テストを作成しようとする場合は、次のことをお勧めします。

  • すべてが同じハッシュコード (たとえば 30 または 40) を持つ一連のキーを作成します。
  • 各キーのマップに値を追加します
  • (1) キーがマップ内に存在することをアサートし、(2) そのキーのマッピングを削除し、(3) マッピングを追加し直すという無限ループを持つ、キー用の別のスレッドを生成します。

運が良ければ、ハッシュ バケットの背後にあるリンク リストが破損するため、ある時点でアサーションが失敗します。HashMap運が悪いと、ドキュメンテーションにもかかわらず、実際にスレッドセーフであるように見えます。

于 2013-08-30T22:04:31.423 に答える
5

古いスレッドです。しかし、ハッシュマップの問題を実証できるサンプルコードを貼り付けるだけです。

以下のコードを見てください。10 スレッド (スレッドあたり 3000 アイテム) を使用して 30000 アイテムをハッシュマップに挿入しようとしています。

したがって、すべてのスレッドが完了すると、ハッシュマップのサイズが 30000 になることが理想的です。ただし、実際の出力は、ツリーの再構築中に例外が発生するか、最終カウントが30000 未満になるかのいずれかになります。

class TempValue {
    int value = 3;

    @Override
    public int hashCode() {
        return 1; // All objects of this class will have same hashcode.
    }
}

public class TestClass {
    public static void main(String args[]) {
        Map<TempValue, TempValue> myMap = new HashMap<>();
        List<Thread> listOfThreads = new ArrayList<>();

        // Create 10 Threads
        for (int i = 0; i < 10; i++) {
            Thread thread = new Thread(() -> {

                // Let Each thread insert 3000 Items
                for (int j = 0; j < 3000; j++) {
                    TempValue key = new TempValue();
                    myMap.put(key, key);
                }

            });
            thread.start();
            listOfThreads.add(thread);
        }

        for (Thread thread : listOfThreads) {
            thread.join();
        }
        System.out.println("Count should be 30000, actual is : " + myMap.size());
    }
}

出力 1 : 

Count should be 30000, actual is : 29486

出力 2 : (例外)

java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNodejava.lang.ClassCastException: java.util.HashMap$Node cannot be cast to java.util.HashMap$TreeNode
    at java.util.HashMap$TreeNode.moveRootToFront(HashMap.java:1819)
    at java.util.HashMap$TreeNode.treeify(HashMap.java:1936)
    at java.util.HashMap.treeifyBin(HashMap.java:771)
    at java.util.HashMap.putVal(HashMap.java:643)
    at java.util.HashMap.put(HashMap.java:611)
    at TestClass.lambda$0(TestClass.java:340)
    at java.lang.Thread.run(Thread.java:745)

ただし、行Map<TempValue, TempValue> myMap = new HashMap<>();をConcurrentHashMapに変更すると、出力は常に 30000 になります。

別の観察: 上記の例では、クラスのすべてのオブジェクトのハッシュコードTempValueは同じでした (** つまり、1**)。HashMap に関するこの問題は、(ハッシュコードが原因で) 衝突が発生した場合にのみ発生する可能性があります。別の例を試しました。

TempValue クラスを次のように変更します。

class TempValue {
    int value = 3;
}

ここで、同じコードを再実行します。
5回の実行ごとに、2〜3回の実行でも 30000 とは異なる出力が得られることがわかります。
そのため、通常はあまり衝突しない場合でも、問題が発生する可能性があります。(HashMapの再構築等によるものかも)

全体として、これらの例は、ConcurrentHashMap が処理する HashMap の問題を示しています。

于 2016-12-18T14:13:49.293 に答える