Java HashMap.get(Object)无限循环

Question

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

虽然我可以很容易地看到为什么对HashMap.put(Object)方法的并发调用会导致无限循环的原因,但是当我尝试读取正在调整大小的HashMap时,我无法理解为什么get(Object)方法会被卡住那一刻.我看一下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

你链接的是Java 6中的HashMap.它是用Java 8重写的.在重写之前,get(Object)如果有两个写入线程,则无法循环.我不知道get单个编写器可以发生无限循环的方式.

具体而言,当有两个同时呼叫到发生无限循环resize(int)其中要求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;
         }
     }
 }

该逻辑反转了散列桶中节点的顺序.两个同时反转可以形成一个循环.

看着:

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

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

在Java 8中,resize维护节点排序,因此不能以这种方式发生循环.你可以丢失数据.

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

Answer 2

情况：

HashMap 的默认容量为 16，Load factor 为 0.75，这意味着当第 12 个 Key-Value 对进入映射时，HashMap 的容量将增加一倍（16 * 0.75 = 12）。

当 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 会在开始而不是在末尾添加键值对。Hashmap 在开始时添加了新的键值对，以避免每次都遍历链表并保持性能不变。
6. 线程 2 将所有键值对从旧桶转移到新桶，线程 1 将有机会执行。

线程 1 获得执行机会：

1. 离开控制之前的线程 1 指向旧存储桶的第一个元素和下一个元素。
2. 现在，当线程 1 开始将键值对从旧桶放入新桶时。它成功地将 (90, val) 和 (1, val) 放入新的 Bucket 中。
3. 当它尝试将 (1, val) 的下一个元素 (90, val) 添加到新的 Bucket 中时，它将最终陷入无限循环。

解决方案：

要解决此问题，请使用 aCollections.synchronizedMap或ConcurrentHashMap。

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

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

Answer 3

鉴于我看到的无限循环的唯一可能性是在方法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，我相信只有一个线程不可能出现无限循环。get在 jdk 6（或 5）之前的旧实现中，这一点更为明显：

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

即使如此，除非发生大量碰撞，否则这种情况似乎仍然不太可能发生。

PS：我很乐意被证明是错的！