Java HashMap.get（Object）无限循环

Question

关于SO的一些答案提到，如果不能正确同步，HashMap中的get方法可能陷入无限循环（例如this one或this one）（通常底线是“don '在多线程环境中使用HashMap，请使用ConcurrentHashMap“）。

虽然我很容易明白为什么对HashMap.put（Object）方法的并发调用会导致无限循环，但我不明白为什么get（Object）方法在尝试读取HashMap时会卡住那时正在调整大小。我有一个看看implementation in openjdk，它包含一个周期，但退出条件e != null应该迟早满足。它怎么会永远循环？ 被明确提到是受到此问题的一段代码是：

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指令重新排序有关（因此问题只能发生在多处理器机器上）？

Answer 1

虽然我从来没有亲自使用HashMap和结束了一个无限循环（曾经）我会说，如果我们谈论的主题，答案是死锁。

死锁是当多个线程试图同时访问相同的资源，因此，所有的参与线程等待所有其他线程完成，因此他们都挨饿。

在Java synchronized关键字确保指定方法在所有线程同步，因此没有两个线程试图同时访问相同的信息。

回到资源的事情......如果我没记错的话......在Java整个HashMap的被认为是一种资源，所以一个方法将尽快启动“检查出来”。但是，如果两种方法尝试同时获取散列映射：死锁。

这是很好的注意，Java是一种非常安全的语言，因此干脆把synchronized关键字在处理这个多线程资源的所有方法前应该让一切闪耀就像是全新的。

更多阅读： 有一位非常鼓舞人心的人，我相信荷兰的Edsgar W. Dijkstra非常专注于预防死锁和多线程系统。他最着名的关于僵局的可视化和难题之一是餐饮哲学家问题。真是一个了不起的人。

Answer 2

既然我看到了一个无限循环的唯一可能性是e.next = e的get方法中：

for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) 

这只会改变大小的过程中transfer方法发生：

do { 
    Entry<K,V> next = e.next; 
    int i = indexFor(e.hash, newCapacity); 
    e.next = newTable[i]; //here e.next could point on e if the table is modified by another thread 
    newTable[i] = e; 
    e = next; 
} while (e != null); 

如果只有一个线程正在修改Map，我认为只用一个线程就无法进行无限循环。

public Object get(Object key) { 
     Object k = maskNull(key); 
     int hash = hash(k); 
     int i = indexFor(hash, table.length); 
     Entry e = table[i]; 
     while (true) { 
      if (e == null) 
       return e; 
      if (e.hash == hash && eq(k, e.key)) 
       return e.value; 
      e = e.next; 
     } 
    } 

即使是这样的情况似乎仍然除非有很多的碰撞很不可思议：它的JDK 6（或5）之前，是与旧的实施get更加明显。

P.S：我很想被证明是错误的！

Answer 3

链接用于Java 6中的HashMap。它在Java 8中重写。在此重写之前，如果有两个写入线程，则get(Object)上的无限循环是可能的。我不知道在单个作者身上可能会出现get的无限循环。

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; 
     } 
    } 
} 

此逻辑反转的散列桶中的节点的排序：

具体地，当存在要resize(int)两个同时呼叫它调用transfer发生无限循环。两个同时反转可以形成一个循环。

看：

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

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

在Java 8中，调整大小保持节点排序，因此循环不能以这种方式发生。尽管你可能会丢失数据。

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

Answer 4

情况：

HashMap中的默认容量为16和负载系数为0.75，这意味着当第12键值对在地图（16 * 0.75 = 12）进入的HashMap将加倍其容量。

当2个线程试图同时访问HashMap时，您可能会遇到无限循环。线程1和线程2尝试放置第12个键值对。

线程1获得执行机会：

1. 线程1名试图把12键值对，
2. 线程1所创立达到该门槛限制，它创造能力提高的新桶。因此地图的容量从16增加到32.
3. 线程1现在将所有现有键值对传输到新桶。
4. 线程1指向第一个键值对和下一个（第二个）键值对以开始传输过程。

线程1在指向键值对之后，在开始传输过程之前，松开控制线程并且线程2有机会执行。

线程2获得执行机会：

1. 线程2名试图把12键值对，
2. 线程2个开创达到该门槛限制，它创造能力提高的新桶。所以地图的容量从16增加到32.
3. 线程2现在将所有现有的键值对转移到新桶中。
4. 线程2指向第一个键值对和下一个（第二个）键值对以启动传输过程。
5. 将键值对从旧桶转移到新桶时，键值对将在新桶中反转，因为hashmap将在开始时而不是结束时添加键值对。散列图在开始时添加新的键值对，以避免每次遍历链表并保持性能不变。
6. 线程2将把旧桶中的所有键 - 值对转移到新桶中，线程1将获得执行机会。

线程1获得执行机会：

1. 线程1离开控制指着第一个元素和旧桶的下一个元素之前。
2. 现在当线程1开始将键值对从旧桶放到新桶时。它成功地将（90，val）和（1，val）放入新桶中。
3. 当它尝试将（1，val）（90，val）的下一个元素添加到新Bucket中时，它将以无限循环结束。

解决方案：

为了解决这个或者使用一个或Collections.synchronizedMapConcurrentHashMap。

ConcurrentHashMap是线程安全的，即代码可以一次由单个线程访问。

HashMap可以通过使用Collections.synchronizedMap(hashMap)方法进行同步。通过使用这个方法，我们得到了一个与HashTable对象等价的HashMap对象。所以每个修改都在Map上执行，锁定在Map对象上。