マルチスレッド環境で重複キーを持つハッシュマップ

Question

Collections.synchronizedMap()を使用せず、私にマルチスレッド環境があるとします。

私はなどリサイズ問題に関する競合状態を知っている

私の質問は、ケース2つのスレッドTaとTbが同じオブジェクトを持つとマップに入れしようとしているがあることができます。

どのように防止されていない場合でも、2つのエントリが存在することはできますか？ 2つの異なるスレッドが同時に実行されている2つのputコールの間には、時間差がありますか？

私の理解しているように、TaとTbの両方については、両方を置く前にチェックするので、ここで重複するキーがある場合があります。

hashcodeとequalsが適切にオーバーライドされていることを考慮してください。

Answer 1

のJavadoc HashMapのための状態：この実装は同期化されていないことを

注意。複数のスレッド が同時にハッシュマップにアクセスし、少なくとも1つのスレッド がマップを構造的に変更する場合、はが外部と同期する必要があります。 （ 構造変更とは、1つまたは複数のマッピングを追加または削除する操作で、 インスタンスに既に含まれているキーに関連付けられた値を変更するだけです。構造的な変更はありません）。これは、通常、 です。自然に はマップをカプセル化します。そのようなオブジェクトが存在しない場合は、Collections.synchronizedMapメソッドを使用して を "ラップ"する必要があります。

だから、ドキュメントは、あなたがが何とかアクセスを同期する必要がありますが、そうでない場合はどうなるか言っていないと言います。つまり、このときの動作は未定義です - すべての賭けはオフです。

あなた自身the source code for HashMapを見ることができます。 putの心は次のとおりです。

 for (Entry<K,V> e = table[i]; e != null; e = e.next) { 
     Object k; 
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { 
      V oldValue = e.value; 
      e.value = value; 
      e.recordAccess(this); 
      return oldValue; 
     } 
    } 

    modCount++; 
    addEntry(hash, key, value, i); 
    return null; 

（編集 - ポイントを補強している - これは、Java 6のJava 8のは劇的に異なっているで実装である）2つのスレッドがしようとすると、我々は結果を推測することができます

これは同時に起こりますが、理由を考えるのはかなり難しいです。場合によっては同じキーで2つのエントリが得られることもありますが、時にはそうではありません。タイミングによって異なります。

TreeMapのput()はもちろん、このように乱用された場合の違いはまったく異なります。

このような動作は、実装の奇抜であり、未定義の動作については話しているので、将来は警告なく変更される可能性があります。実装はそれがないことを、あなたに何の約束を行いません：

• は黙ってメモリの
• NullPointerException
• 請求巨額
• 壊れ店舗となるよう
• が無限ループに入るエントリをドロップ他のキーを持つエントリは失われます
• 前に削除したエントリを再度表示します。
• ヒープmエモリー
• など

ドキュメントはIteratorがオブジェクト上で作業している間、ConcurrentModificationExceptionスローするIteratorの原因となります、他の場所から変更することを状態を行います - しかし、これは異なる関心事でありますSynchronizedMap

要約すると、それをしないでください。