Java HashMap.get（Object）无限循环 [英] Java HashMap.get(Object) infinite loop
问题描述
关于SO的一些答案提到HashMap中的get方法可能陷入无限循环（例如此或此）（如果未正确同步）（通常的底线是请勿在多线程环境中，请使用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）并调用 transfer ：
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屋！
