LinkedHashMapを使用したConcurrentModificationException

Question

LinkedHashMap構造体を以下のコードで反復処理すると、java.util.ConcurrentModificationExceptionがトリガーされる原因がわかりません。 Map.Entryアプローチを使用すると問題はありません。以前の投稿からこれを引き起こしていることについて、良い説明はありませんでした。

ご協力いただければ幸いです。

import java.util.LinkedHashMap; 
import java.util.Map; 

public class LRU { 

    // private Map<String,Integer> m = new HashMap<String,Integer>(); 
    // private SortedMap<String,Integer> lru_cache = Collections.synchronizedSortedMap(new TreeMap<String, Integer>()); 

    private static final int MAX_SIZE = 3; 

    private LinkedHashMap<String,Integer> lru_cache = new LinkedHashMap<String,Integer>(MAX_SIZE, 0.1F, true){ 
     @Override 
     protected boolean removeEldestEntry(Map.Entry eldest) { 
      return(lru_cache.size() > MAX_SIZE); 
     } 
    };  

    public Integer get1(String s){ 
     return lru_cache.get(s);   
    } 

    public void displayMap(){ 
     /** 
     * Exception in thread "main" java.util.ConcurrentModificationException 
      at java.util.LinkedHashMap$LinkedHashIterator.nextEntry(LinkedHashMap.java:373) 
      at java.util.LinkedHashMap$KeyIterator.next(LinkedHashMap.java:384) 
      at LRU.displayMap(LRU.java:23) 
      at LRU.main(LRU.java:47) 
     */ 
     *for(String key : lru_cache.keySet()){ 
      System.out.println(lru_cache.get(key)); 
     }* 

// This parser works fine   
//  for(Map.Entry<String, Integer> kv : lru_cache.entrySet()){ 
//   System.out.println(kv.getKey() + ":" + kv.getValue()); 
//  } 
    } 

    public void set(String s, Integer val){ 
     if(lru_cache.containsKey(s)){    
      lru_cache.put(s, get1(s) + val); 
     } 
     else{ 
      lru_cache.put(s, val); 
     } 
    } 

    public static void main(String[] args) { 

     LRU lru = new LRU(); 
     lru.set("Di", 1); 
     lru.set("Da", 1); 
     lru.set("Daa", 1); 
     lru.set("Di", 1);   
     lru.set("Di", 1); 
     lru.set("Daa", 2); 
     lru.set("Doo", 2); 
     lru.set("Doo", 1);   
     lru.set("Sa", 2); 
     lru.set("Na", 1); 
     lru.set("Di", 1); 
     lru.set("Daa", 1); 

     lru.displayMap(); 

    } 

} 

Answer 1

あなたがアクセス順のリンクハッシュマップを使用している：スペックからhttp://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.htmlで、

構造的な変更がいずれかまたは 以上のマッピングを追加または削除操作や、ですアクセス順のリンクされたハッシュマップの場合、 は反復順序に影響します。挿入順のリンクされたハッシュマップでは、すでに に含まれているキーに関連付けられた値を変更するだけで、構造的な変更はありません。アクセス順の単なるgetでマップを照会することは、構造 変形であり、 ハッシュマップにリンクされます。）

では単にgetを呼び出して例外をトリガする、構造的な変更とみなされるのに十分です。 entrySet()シーケンスを使用している場合は、入力するのはクエリでありマップではないため、ConcurrentModificationExceptionはトリガーしません。

Answer 2

はJavadoc for LinkedHashMap読む：構造的な変更がアクセス順のリンクハッシュマップの場合には、追加または1つのまたは 以上のマッピングを削除したりする操作である

、 は、繰り返し順序に影響を与えます。挿入順のリンクされたハッシュマップでは、すでに に含まれているキーに関連付けられた値を変更するだけで、構造的な変更はありません。 アクセス順のリンク ハッシュマップでは、マップをgetと照会するだけで、構造 が変更されます。

あなたはLinkedHashMapコンストラクタにtrueを渡しているので、アクセス順序にあり、あなたはそれからget何かしようとしているとき、あなたは構造的にそれを変更しています。

また、拡張されたfor構文を使用すると、実際にはイテレータが使用されていることに注意してください。 JLS §14.14.2から簡体字の引用：

強化forの文の形式は次のとおりです。

EnhancedForStatement: 

for (TargetType Identifier : Expression) Statement 

[...]

式の種類はいくつかのタイプのIterable<X>のサブタイプがある場合 引き数Xの場合は、となるようにIを入力します。そうでない場合は Iを生タイプjava.util.Iteratorとします。

向上for文が の基本for陳述形態と等価である：

for (I #i = Expression.iterator(); #i.hasNext();) { 
    TargetType Identifier = 
     (TargetType) #i.next(); 
    Statement 
} 

#iは にある任意の他の識別子（自動的に、さもなければ発生又は）から区別される、自動的に生成された識別子であります拡張されたforステートメントが発生する時点でのスコープ（§6.3）。

また、LinkedHashMapのJavadocに：このクラスのコレクションビューメソッドのすべてによって返されたコレクション のiteratorメソッドによって返さ

イテレータは フェイルファストがあります。ifイテレータが作成された後の任意の時点で、イテレータ自身の removeメソッド以外の方法で構造的に変更された場合、イテレータは ConcurrentModificationExceptionをスローします。

あなたは地図上getを呼び出しているときので、あなたが例外をスローするように拡張-ためにイテレータを引き起こし、それに構造的な変更を行っています。私はgetを呼び出す回避する、あなたがこれを行うためのものだと思う：あなたは立ち退きポリシーを意味する（LRUの動作を取得するためにtrueを渡すLinkedHashMapのコンストラクタで

for (Integer i : lru_cache.values()) { 
    System.out.println(i); 
} 

Answer 3

はアクセス順序いうよりfalseある挿入順序のために）。

get(key)と呼び出すたびに、基礎となるMap.Entryはアクセスカウンタをインクリメントし、最後にアクセスしたMap.Entryをリストの先頭に移動してコレクションを並べ替えます。

反復子（暗黙的にforループによって作成されます）は、修正されたフラグをチェックします。このフラグは元のコピーとは異なり、ConcurrentModificationExceptionをスローします。

for(Map.Entry<String,Integer> e : lru_cache.entrySet()){ 
     System.out.println(e.getValue()); 
    } 

は、このクラスはスレッドセーフではありません注意してください：この実装はjava.util.HashMapをから継承されているため、イテレータは変更フラグをチェックしないと、あなたがentrySet()を使用する必要があります避けるために

並行環境では、Collections.synchronizedMap（Map）のような潜在的に高価なガードを使用する必要があります。このシナリオでは、より良いオプションはGoogle's Guava Cacheです。

Answer 4

あなたのコード

for(String key : lru_cache.keySet()){ 
    System.out.println(lru_cache.get(key)); 
} 

が実際にコンパイル： - 答えは理由を説明の上

Iterator<String> it = lru_cache.keySet().iterator(); 
while (it.hasNext()) { 
    String key = it.next(); 
    System.out.println(lru_cache.get(key)); 
} 

次に、あなたのLRUキャッシュはset()を呼び出すときに、しかしget()を呼び出すときの要素をないMAX_SIZEに自身を縮小します。

したがって、私たちは行動を次のようしている：あなたのキャッシュから要素を抽出するために呼び出さlru_cache.keySet()コレクションを

lru_cache.get()を反復するために作成した

• 新しいイテレータは
• get()呼び出しは、あなたのケース3内の要素を（MAX_SIZEするlru_cacheを切り捨て）
• イテレータitは、コレクションの変更によって無効になり、次の反復でスローされます。

Answer 5

リストを変更する（要素を追加または削除する）ときにも、このエラーが発生したリストをIteratorで追跡するときに、コレクションフレームワークのフェイルファースト動作が発生します。私はしばらく前にこのエラーに遭遇しました。詳細情報については、下のスレッドを参照してください。

ConcurrentModificationException when adding inside a foreach loop in ArrayList

これは配列リストを言いますが、それはコレクション（s）はデータstrucutresのほとんどに適用されます。

Concurrent Modification Exception : adding to an ArrayList

http://docs.oracle.com/javase/6/docs/api/java/util/ConcurrentModificationException.html

Answer 6

java.util.ConcurrentModificationException：反復子が存在する間、基礎となるリストの構造を変更（追加、削除、再ハッシュなど）がある場合。イテレータは、各操作の前にリストが変更されたかどうかを確認します。これは「フェイルセーフ操作」として知られています。

それはフェイルファスト反復子を持つコレクションを反復処理している間、スレッドが直接コレクションを変更する場合、反復子はこのexception.Hereをスローしますget()を呼び出すと、構造的にマップを変更するので、あなたはイテレータを使用しながらget()メソッドを呼び出すことはできません次のイテレータメソッドの呼び出しは失敗し、ConcurrentModificationExceptionがスローされます。