首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Java HashMap.get(对象)无限循环

Java HashMap.get(对象)无限循环
EN

Stack Overflow用户
提问于 2016-02-21 18:22:07
回答 2查看 8.6K关注 0票数 27

一些关于此的答案提到,如果没有正确同步,HashMap中的get方法可能会陷入无限循环(例如this onethis one) (通常底线是“不要在多线程环境中使用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指令重新排序有关(因此该问题只能在多处理器机器上发生)?

EN

回答 2

Stack Overflow用户

发布于 2017-05-25 20:20:37

您的链接是针对Java6中的HashMap的。它在Java8中被重写了。在此之前,如果有两个写入线程,则可以在get(Object)上进行无限循环。我不知道get上的无限循环可以在单个编写器上发生的方式。

具体地说,当同时有两个调用transferresize(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;

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

在Java 8中,resize保持节点顺序,因此循环不会以这种方式发生。但是,您可能会丢失数据。

在保持访问顺序的情况下,当有多个读取器而没有写入器时,LinkedHashMap类的迭代器可能会陷入无限循环。对于多个读取器和访问顺序,每次读取都会从节点的双向链表中删除然后插入被访问的节点。多个读取器可能导致同一节点被多次重新插入到列表中,从而导致循环。同样,这个类已经针对Java8进行了重写,我不知道这个问题是否仍然存在。

票数 16
EN

Stack Overflow用户

发布于 2017-05-22 21:01:46

假设我看到的无限循环的唯一可能性是在get方法中使用e.next = e

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,我相信只有一个线程的无限循环是不可能的。在JDK6(或5)之前的旧的get实现中,这一点更加明显:

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

即使这样,这种情况看起来仍然是不太可能的,除非有很多冲突。

附言:我很想被证明是错的!

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/35534906

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档