疫苗：Java HashMap的死循环

作者：网络转载发布时间：[ 2013/6/14 10:01:31 ] 推荐标签：

　　迁移的源代码，注意高亮处：

    void transfer(Entry[] newTable)
    {
        Entry[] src = table;
        int newCapacity = newTable.length;
        //下面这段代码的意思是：
        // 从OldTable里摘一个元素出来，然后放到NewTable中
        for (int j = 0; j < src.length; j++) {
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry next = e.next;
                    int i = indexFor(e.hash， newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

　　好了，这个代码算是比较正常的。而且没有什么问题。

　　正常的ReHash的过程

　　画了个图做了个演示。

　　● 我假设了我们的hash算法是简单的用key mod 一下表的大小（也是数组的长度）。

　　● 上面的是old hash 表，其中的Hash表的size=2，所以key = 3， 7， 5，在mod 2以后都冲突在table[1]这里了。

　　● 接下来的三个步骤是Hash表 resize成4，然后所有的重新rehash的过程

　　并发下的Rehash

　　1）假设我们有两个线程。我用红色和浅蓝色标注了一下。

　　我们再回头看一下我们的 transfer代码中的这个细节：

    do {
        Entry next = e.next; // <--假设线程一执行到这里被调度挂起了
        int i = indexFor(e.hash， newCapacity);
        e.next = newTable[i];
        newTable[i] = e;
        e = next;
    } while (e != null);

　　而我们的线程二执行完成了。于是我们有下面的这个样子。