java 带有 LinkedHashMap 的 ConcurrentModificationException

ConcurrentModificationException with LinkedHashMap

提问by Aditya Sakhuja

Not sure what is triggering a java.util.ConcurrentModificationExceptionwhen I iterate over the LinkedHashMapstructure in the code below. Using the Map.Entryapproach works fine. Did not get a good explanation on what is triggering this from the previous posts.

java.util.ConcurrentModificationException当我遍历LinkedHashMap下面代码中的结构时，不确定是什么触发了 a 。使用该Map.Entry方法工作正常。没有从以前的帖子中得到关于是什么触发这个的很好的解释。

Any help would be appreciated.

任何帮助，将不胜感激。

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();

    }

}

回答by gparyani

Read the Javadoc for LinkedHashMap:

阅读Javadoc 以了解LinkedHashMap：

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with getis a structural modification.

结构修改是添加或删除一个或多个映射的任何操作，或者在访问顺序链接的散列映射的情况下，影响迭代顺序的任何操作。在插入顺序链接的哈希映射中，仅更改与映射中已包含的键关联的值不是结构修改。在按访问顺序链接的哈希映射中，仅查询映射get是一种结构修改。

Since you're passing in trueto the LinkedHashMapconstructor, it is in access order and when you are trying to getsomething from it, you are structurally modifying it.

由于您正在传递true给LinkedHashMap构造函数，因此它按访问顺序排列，当您尝试从中获取get某些内容时，您正在结构上修改它。

Also note that when you use the enhanced forsyntax, you are actually using an iterator. Simplified quote from JLS §14.14.2:

另请注意，当您使用增强for语法时，您实际上是在使用迭代器。JLS §14.14.2 的简化引用：

The enhanced forstatement has the form:

EnhancedForStatement:

for ( TargetType Identifier : Expression ) Statement

[...]

If the type of Expressionis a subtype of Iterable<X>for some type argument X, then let Ibe the type java.util.Iterator<X>; otherwise, let Ibe the raw type java.util.Iterator.

The enhanced forstatement is equivalent to a basic forstatement of the form:

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

#iis an automatically generated identifier that is distinct from any other identifiers (automatically generated or otherwise) that are in scope (§6.3) at the point where the enhanced for statement occurs.

增强for语句具有以下形式：

EnhancedForStatement:

for ( TargetType Identifier : Expression ) Statement

[...]

如果Expression的类型是Iterable<X>某个类型参数的子类型X，则令I为类型java.util.Iterator<X>；否则，I设为原始类型java.util.Iterator。

增强for语句等效于for以下形式的基本语句：

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

#i是一个自动生成的标识符，它不同于在增强的 for 语句发生点的范围内（第 6.3 节）的任何其他标识符（自动生成的或以其他方式生成的）。

Also, in the Javadoc for LinkedHashMap:

此外，在 Javadoc 中LinkedHashMap：

The iterators returned by the iteratormethod of the collections returned by all of this class's collection view methods are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own removemethod, the iterator will throw a ConcurrentModificationException.

由iterator该类的所有集合视图方法返回的集合的方法返回的迭代器是 快速失败的：如果在迭代器创建后的任何时间以任何方式修改映射的结构，除了通过迭代器自己的 remove方法，迭代器会抛出一个 ConcurrentModificationException.

Therefore, when you are calling geton the map, you are performing structural modifications to it, causing the iterator in the enhanced-for to throw an exception. I think you meant to do this, which avoids calling get:

因此，当您get在地图上调用时，您正在对其进行结构修改，从而导致增强型 for 中的迭代器抛出异常。我认为您打算这样做，以避免调用get：

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

回答by Femi

You're using an access-ordered linked hash map: from the spec at http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html,

您正在使用按访问顺序排列的链接哈希映射：来自http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html的规范，

A structural modification is any operation that adds or deletes one or more mappings or, in the case of access-ordered linked hash maps, affects iteration order. In insertion-ordered linked hash maps, merely changing the value associated with a key that is already contained in the map is not a structural modification. In access-ordered linked hash maps, merely querying the map with get is a structural modification.)

结构修改是添加或删除一个或多个映射的任何操作，或者在访问顺序链接的散列映射的情况下，影响迭代顺序的任何操作。在插入顺序链接的哈希映射中，仅更改与映射中已包含的键关联的值不是结构修改。在按访问顺序链接的哈希映射中，仅使用 get 查询映射是一种结构修改。）

Simply calling getis enough to be considered a structural modification, triggering the exception. If you use the entrySet()sequence you're only querying the entry and NOT the map, so you don't trigger the ConcurrentModificationException.

简单的调用get就足以被认为是结构修改，触发异常。如果您使用entrySet()序列，您只是查询条目而不是地图，因此您不会触发ConcurrentModificationException.

回答by earcam

In the constructor of LinkedHashMapyou pass trueto get the LRU behaviour (meaning the eviction policy is access orderrather than falsefor insertion order).

在构造函数中LinkedHashMap传递true，以获得LRU行为（指驱逐策略是访问顺序，而不是false用于插入顺序）。

So every time you call get(key)the underlying Map.Entry increments an access counter AND reorders the collection by moving the (last accessed) Map.Entry to the head of the list.

因此，每次调用get(key)底层 Map.Entry 时，都会增加一个访问计数器，并通过将（上次访问的）Map.Entry 移动到列表的头部来重新排序集合。

The iterator (implicitly created by the for loop) checks the modified flag, which is different from the copy it took originally, so throws the ConcurrentModificationException.

迭代器（由 for 循环隐式创建）检查修改后的标志，这与它最初采用的副本不同，因此抛出ConcurrentModificationException.

To avoid this you should use the entrySet()as the implementation is inherited from java.util.HashMap and therefore the iterator doesn't check the modification flags:

为了避免这种情况，您应该使用 ，entrySet()因为实现是从 java.util.HashMap 继承的，因此迭代器不会检查修改标志：

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

Be aware this class isn't threadsafe so in concurrent environments you will need to use an potentially expensive guards like Collections.synchronizedMap(Map). In this scenario a better option might be Google's Guava Cache.

请注意，此类不是线程安全的，因此在并发环境中，您需要使用可能昂贵的守卫，例如 Collections.synchronizedMap(Map)。在这种情况下，更好的选择可能是Google 的 Guava Cache。

回答by Sergey Alaev

Your code

你的代码

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

Actually compiles to:

实际上编译为：

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

Next, your LRU cache shrinks itself to MAX_SIZE elements not when calling set(), but when calling get()- above answers explain why.

接下来，您的 LRU 缓存不是在调用set()时而是在调用时将自身缩小到 MAX_SIZE 元素get()- 以上答案解释了原因。

Thus we have following behavior:

因此，我们有以下行为：

• new iterator created to iterate over lru_cache.keySet()collection
• lru_cache.get()called to extract element from your cache
• get()invocation truncates lru_cacheto MAX_SIZE elements (in your case 3)
• iterator itbecomes invalid due to collection modification and throws on next iteration.

• 创建新的迭代器以迭代lru_cache.keySet()集合
• lru_cache.get()调用从缓存中提取元素
• get()调用截断lru_cache为 MAX_SIZE 个元素（在您的情况下为 3）
• 迭代器it由于集合修改而无效并在下一次迭代中抛出。

回答by SparkOn

java.util.ConcurrentModificationException: If there are any structural changes (additions, removals, rehashing, etc.) to the underlying list while the iterator exists. The iterator checks to see if the list has changed before each operation. This is known as 'failsafe operation'.

java.util.ConcurrentModificationException: 如果迭代器存在时底层列表有任何结构变化（添加、删除、重新散列等）。迭代器会在每次操作之前检查列表是否已更改。这称为“故障安全操作”。

If a thread modifies a collection directly while it is iterating over the collection with a fail-fast iterator, the iterator will throw this exception.Here you cannot call the get()method while using an iterator because calling get()structurally modifies the map and hence the next call to one of the iterators method fails and throws a ConcurrentModificationException.

如果线程在使用快速失败迭代器迭代集合时直接修改集合，则迭代器将抛出此异常。此处您不能get()在使用迭代器时调用该方法，因为调用get()会在结构上修改映射，因此下一次调用其中一个迭代器方法失败并抛出一个ConcurrentModificationException.

回答by sampopes

It is coz of fail-fast behaviour of collections framework also when you modify the list (by adding or removing elements) while traversing a list with this error will be there with Iterator. I came across this error some time back . Refer below threads to for detail info.

当您在遍历列表时修改列表（通过添加或删除元素）时，集合框架的快速失败行为也是因为迭代器会出现此错误。前段时间我遇到了这个错误。有关详细信息，请参阅以下线程。

ConcurrentModificationException when adding inside a foreach loop in ArrayList

在 ArrayList 的 foreach 循环中添加时出现 ConcurrentModificationException

Though this says array list, it applies for most of the collection(s) data strucutres.

虽然这说的是数组列表，但它适用于大多数集合数据结构。

Concurrent Modification Exception : adding to an ArrayList

并发修改异常：添加到 ArrayList

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

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