Java HashMap.get（Object） infinite loop

concurrency hashmap multithreading java

2022-09-01 13:20:29

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

虽然我可以很容易地理解为什么对HashMap.put（Object）方法的并发调用会导致无限循环，但我不太明白为什么get（Object）方法在尝试读取当时正在调整大小的HashMap时会卡住。我看了一下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指令重新排序有关（因此问题只能发生在多处理器计算机上）？

答案 1

您的链接适用于 Java 6 中的 HashMap。它是用Java 8重写的。在此重写之前，如果有两个写入线程，则可以进行无限循环。我不知道无限循环可以发生在单个作家身上的方式。get(Object)get

具体而言，当有两个同时调用将呼叫转移到时，将发生无限循环：resize(int)

 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;

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

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

当有多个读取器且在维护访问顺序时没有写入器时，类的迭代器可能会陷入无限循环。对于多个读取器和访问顺序，每次读取都会从节点的双链接列表中删除并插入被访问的节点。多个读取器可能导致同一节点多次重新插入到列表中，从而导致循环。同样，该类已针对Java 8重写，我不知道此问题是否仍然存在。LinkedHashMap

答案 2

情况：

HashMap 的默认容量为 16，负载因子为 0.75，这意味着当第 12 个键值对进入映射时，HashMap 的容量将翻倍（16 * 0.75 = 12）。

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

线程 1 获得执行机会：

线程 1 尝试放置第 12 个键值对，
线程 1 发现已达到阈值限制，并创建容量增加的新存储桶。因此，地图的容量从16增加到32。
线程 1 现在将所有现有的键值对传输到新存储桶。
线程 1 指向第一个键值对和下一个（第二个）键值对以开始传输过程。

线程 1 指向键值对后，在开始传输过程之前，松开控制，线程 2 获得了执行的机会。

线程 2 获得执行机会：

线程 2 尝试放置第 12 个键值对，
线程 2 发现已达到阈值限制，并创建容量增加的新存储桶。因此，地图的容量从16增加到32。
线程 2 现在将所有现有的键值对传输到新存储桶。
线程 2 指向第一个键值对和下一个（第二个）键值对以开始传输过程。
将键值对从旧存储桶传输到新存储桶时，键值对将在新存储桶中反转，因为哈希映射将在开始时而不是在结束时添加键值对。Hashmap在开始时添加新的键值对，以避免每次都遍历链表并保持恒定的性能。
线程 2 会将所有键值对从旧存储桶传输到新存储桶，线程 1 将有机会执行。

线程 1 获得执行机会：

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

溶液：

要解决此问题，请使用或。Collections.synchronizedMapConcurrentHashMap

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

可以使用方法同步哈希映射。通过使用这种方法，我们得到一个HashMap对象，它相当于HashTable对象。因此，在Map上执行的每个修改都被锁定在Map对象上。Collections.synchronizedMap(hashMap)