HashMap的resize死循环

       当HashMap有数据插入时，都会检查容量有没有超过设定的thredhold，如果超过就要做rehash操作。代码如下：

void resize(int newCapacity) {

Entry[] oldTable = table;

        int oldCapacity = oldTable.length;

        if (oldCapacity == MAXIMUM_CAPACITY) {

            threshold = Integer.MAX_VALUE;

            return;

        }

        Entry[] newTable = new Entry[newCapacity];

        transfer(newTable, initHashSeedAsNeeded(newCapacity));

        table = newTable;

        threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);

}

 

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;

            }

        }

}

        大概看下transfer的步骤：

1.         1.对索引数组中的元素遍历
2.         2.对链表上的每一个节点遍历：用 next 取得要转移那个元素的下一个，将 e 转移到新 Hash 表的头部，使用头插法插入节点。
3.         3.循环2，直到链表节点全部转移
4.         4.循环1，直到所有索引数组全部转移

        经过这几步，我们会发现转移的时候是逆序的。假如转移前链表顺序是1->2->3，那么转移后就会变成3->2->1。这时候在多线程场景下，就会产生死锁问题了，因为可能会造成1->2的同时2->1。

 

         关键代码分析：

while(null != e) {

     Entry<K,V> next = e.next;

     e.next = newTable[i];

     newTable[i] = e;

     e = next;

}

    1. Entry<K,V> next = e.next;——因为是单链表，如果要转移头指针，一定要保存下一个结点，不然转移后链表就丢了

 

    2. e.next = newTable[i];——e 要插入到链表的头部，所以要先用 e.next 指向新的 Hash 表第一个元素（为什么不加到新链表最后？因为复杂度是 O（N））

 

    3. newTable[i] = e;——现在新 Hash 表的头指针仍然指向 e 没转移前的第一个元素，所以需要将新 Hash 表的头指针指向 e

 

    4. e = next——转移 e 的下一个结点      

 

    假设HashMap某位的链表有两个对象，且有两个线程同时执行了put()操作，并进入了transfer()环节。 线程1在执行到第1步时挂起了，然后线程2先执行完毕。线程1继续执行。执行到转移到链表中第二个对象时，由于线程2已执行完，把对象2本应是null的next变成了对象1，于是transfer又继续执行转移对象1，于是对象1的next指向对象2，环形链表出现了。

 

    详见http://www.importnew.com/22011.html