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

    }

}

- Aditya Sakhuja

---

你真的想把负载因子设置为0.1吗？因为当你将初始容量设置为MAX_SIZE时，负载因子确保至少有一个大小为size()/load_factor的容量。例如，当你有3个键时，你将至少有30（实际上是32，因为它必须是2的幂）的容量。我建议使用MAX_SIZE*10/7和默认的负载因子0.7f，这将在这种情况下给你一个容量为4。 - Peter Lawrey

Answer 1

阅读LinkedHashMap的Javadoc文档:

任何添加或删除一个或多个映射项的操作，对于按访问顺序排序的链式哈希表而言，都会影响迭代顺序，这些操作被称为结构性修改。对于按插入顺序排序的链式哈希表而言，仅更改某个已经包含在映射中的键关联的值不是结构性修改。对于按访问顺序排序的链式哈希表而言，仅查询映射表使用get方法就属于结构性修改。

由于您向LinkedHashMap构造函数传递了true，因此它是按访问顺序排序的，当您试图从中获取某些内容时，您正在进行结构性修改。

还要注意，当您使用增强的for语法时，实际上使用的是迭代器。简化自JLS §14.14.2:

增强的for语句的形式为:

EnhancedForStatement:

for ( TargetType Identifier : Expression ) Statement

如果表达式的类型是某个类型参数为X的Iterable<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是一个自动生成的标识符，它与作用域（§6.3）中的任何其他标识符（自动生成或其他方式）都不同，在增强型for语句出现的位置。

此外，在LinkedHashMap的Javadoc中：

  

此类所有集合视图方法返回的集合的iterator方法返回的迭代器都是“fail-fast”的：如果在创建迭代器后的任何时候以除迭代器自己的remove方法之外的任何方式结构上修改了地图，则迭代器将抛出ConcurrentModificationException。

因此，在调用地图上的get方法时，您正在对其进行结构修改，从而导致增强型for中的迭代器抛出异常。我认为你的意思是这个，避免调用get：

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

- gparyani

Answer 2

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

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

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

- Femi

Answer 3

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

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

迭代器（由for循环隐式创建）检查修改标志，与其最初获取的副本不同，因此引发ConcurrentModificationException。

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

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

请注意，这个类不是线程安全的，因此在并发环境中，您需要使用一些可能很昂贵的保护措施，比如Collections.synchronizedMap(Map)。在这种情况下，更好的选择可能是Google Guava缓存。

- earcam

Answer 4

java.util.ConcurrentModificationException ：如果在迭代器存在的同时对底层列表进行任何结构更改（添加、删除、重新哈希等），则会抛出此异常。迭代器在每个操作之前检查列表是否已更改。这被称为“failsafe operation”。

如果一个线程在使用fail-fast迭代器迭代集合时直接修改了集合，那么迭代器将抛出此异常。在使用迭代器时不能调用get()方法，因为调用get()会结构性地修改映射，因此下一次调用迭代器方法失败并抛出ConcurrentModificationException异常。

- SparkOn

Answer 5

你的代码

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()时自动缩小到MAX_SIZE元素，而是在调用get()时 - 上面的答案解释了原因。

因此，我们有以下行为：

- 创建一个新的迭代器来遍历lru_cache.keySet()集合 - 调用lru_cache.get()从缓存中提取元素 - get()调用将lru_cache截断为MAX_SIZE（在您的情况下为3）个元素 - 由于集合修改，迭代器it变成无效状态并在下一次迭代时抛出异常。

- Sergey Alaev

Answer 6

这是由于集合框架的快速失败行为，当您在遍历列表时修改列表（通过添加或删除元素），使用迭代器会出现此错误。我曾经遇到过这个错误。请参考以下线程获取详细信息。

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

尽管这篇文章提到了ArrayList，但它适用于大多数集合数据结构。

Concurrent Modification Exception：向ArrayList添加元素

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

- sampopes