Java HashMap.get(Object) 无限循环 [英] Java HashMap.get(Object) infinite loop

问题描述

关于 SO 的一些答案提到 HashMap 中的 get 方法可能会陷入无限循环(例如 这个或 this one) 如果没有正确同步(通常底线是不要在多线程中使用 HashMap线程环境，使用 ConcurrentHashMap").

A few answers on SO mention that the get method in a HashMap can fall into an infinite loop (e.g. this one or this one) if not synchronized properly (and usually the bottom line is "don't use a HashMap in a multi-threaded environment, use a ConcurrentHashMap").

虽然我可以很容易地看出为什么对 HashMap.put(Object) 方法的并发调用会导致无限循环，但我不太明白为什么 get(Object) 方法在尝试读取 HashMap 时会卡住在那一刻正在调整大小.我看了一下 openjdk中的实现，它包含一个循环，但是退出条件e != null迟早要满足.怎么可能永远循环?明确提到易受此问题影响的一段代码是:

While I can easily see why concurrent calls to the HashMap.put(Object) method can cause an infinite loop, I can't quite see why the get(Object) method can get stuck when it tries to read a HashMap that is being resized at that very moment. I had a look at the implementation in openjdk and it contains a cycle, but the exit condition e != null should be fulfilled sooner or later. How can it loop forever? A piece of code that is mentioned explicitly to be vulnerable to this issue is:

public class MyCache {
    private Map<String,Object> map = new HashMap<String,Object>();

    public synchronized void put(String key, Object value){
        map.put(key,value);
    }

    public Object get(String key){
        // can cause in an infinite loop in some JDKs!!
        return map.get(key);
    }
}

谁能解释一个线程将一个对象放入 HashMap 和另一个读取它的线程如何以生成无限循环的方式交错?是否与某些缓存一致性问题或 CPU 指令重新排序有关(所以问题只能发生在多处理器机器上)?

Can someone explain how a thread putting an object into the HashMap and another reading from it can interleave in such a way that an infinite loop is generated? Is it the case that it has to do with some cache coherency issue or CPU instruction reordering (so the problem can only happen on a multi-processor machine)?

推荐答案

你的链接是针对 Java 6 中的 HashMap.它在 Java 8 中被重写.在此之前重写一个无限循环 get(Object) 如果有两个写入线程是可能的.我不知道 get 上的无限循环可以通过单个编写器发生的方式.

You link is for the HashMap in Java 6. It was rewritten in Java 8. Prior to this rewrite an infinite loop on get(Object) was possible if there were two writing threads. I am not aware of a way the infinite loop on get can occur with a single writer.

具体来说，当有两个同时调用 resize(int) 调用 传输:

Specifically, the infinite loop occurs when there are two simultaneous calls to resize(int) which calls transfer:

 void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
         while(null != e) {
             Entry<K,V> next = e.next;
             if (rehash) {
                 e.hash = null == e.key ? 0 : hash(e.key);
             }
             int i = indexFor(e.hash, newCapacity);
             e.next = newTable[i];
             newTable[i] = e;
             e = next;
         }
     }
 }

这个逻辑颠倒了哈希桶中节点的顺序.两个同时反转可以形成一个循环.

This logic reverses the ordering of the nodes in the hash bucket. Two simultaneous reversals can make a loop.

看看:

             e.next = newTable[i];
             newTable[i] = e;

如果两个线程正在处理同一个节点e，那么第一个线程正常执行但第二个线程设置e.next = e，因为newTable[i] 已被第一个线程设置为 e.e 节点现在指向自己，当 get(Object) 被调用时，它进入一个无限循环.

If two threads are processing the same node e, then first thread executes normally but the second thread sets e.next = e, because newTable[i] has already been set to e by the first thread. The node e now points to itself, and when get(Object) is called it enters an infinite loop.

在 Java 8 中，调整大小保持节点顺序，因此不会以这种方式发生循环.但您可能会丢失数据.

In Java 8, the resize maintains the node ordering so a loop cannot occur in this fashion. You can lose data though.

LinkedHashMap 类的迭代器在维护访问顺序时，如果有多个读取器且没有写入器，则可能会陷入无限循环.使用多个读取器和访问顺序，每次读取都会从节点的双链表中删除然后插入访问的节点.多个读取器可能导致同一节点多次重新插入到列表中，从而导致循环.再次为 Java 8 重写了该类，我不知道这个问题是否仍然存在.

The Iterators for LinkedHashMap class can get stuck in an infinite loop when there are multiple readers and no writers when access ordering is being maintained. With multiple readers and access order every read removes and then inserts the accessed node from a double linked list of nodes. Multiple readers can lead to the same node being reinserted more than once into the list, causing a loop. Again the class has been rewritten for Java 8 and I do not know if this issue still exists or not.

这篇关于Java HashMap.get(Object) 无限循环的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！