HashMap-getEntry多线程阻塞分析

HashMap

本文记述一次hashMap引起阻塞问题


问题现象:
程序是将一个数据库里面的数据导入到另外一个数据库中，两边表结构不一样但业务是一致的(mysql->mssql)。由于每次都是全量循环校验导入，所以运行时间要2-3个小时。

运行过程中，发现在调用jdbcTemplate查询的过程中,经常发生阻塞。



问题分析:
一开始以为，是数据库连接池问题或网络较慢，一直在等待数据库连接或数据库服务器端任务阻塞，一直等待执行

光靠猜想是没有道理的，还是dump看下，

"Thread-1" prio=6 tid=0x000000000b365000 nid=0x15e8 runnable [0x000000000d2af000]
   java.lang.Thread.State: RUNNABLE
	at java.util.HashMap.getEntry(HashMap.java:446)
	at java.util.HashMap.containsKey(HashMap.java:434)
	at java.util.HashSet.contains(HashSet.java:201)

"Thread-0" prio=6 tid=0x000000000b364800 nid=0x714 runnable [0x000000000ca7e000]
   java.lang.Thread.State: RUNNABLE
	at java.util.HashMap.getEntry(HashMap.java:446)
	at java.util.HashMap.containsKey(HashMap.java:434)
	at java.util.HashSet.contains(HashSet.java:201)

    final Entry<K,V> getEntry(Object key) {
        int hash = (key == null) ? 0 : hash(key);
        for (Entry<K,V> e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k))))
                return e;
        }
        return null;
    }

应该是在e = e.next一直循环，那为什么会形成环呢？

然后各种baidu,google,在多线程情况下，hashMap扩容的时候，可能生成环

    /**
     * Transfers all entries from current table to newTable.
     */
    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方法执行

引用

线程一，执行上述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;
            }
        }
    }

这时，线程1线程栈中，e为3，next值为7


然后，线程2执行上述代码，最终将结点3，结点7放入新表中，即: 7和3在table下标为3中，7->3

在这个过程中，线程2修改了引用结点7，使其中的next字段指向了3（这就是引起闭环的主要原因）


接着线程一继续执行，当前e为3，next为7

第一步，将当前处理的结点3放入新表newTable（下标为3），然后将结点3的next指向null（因此newTable是处于线程栈中，是线程私有的，并不受线程2影响）

  这部处理完后，newTable下标为3的内容为：3(其next指向null)

第二步，处理结点7，这时当前结点e为7，而next由于线程2修改了其引用，所以next为3。

            这步处理完后，其newTable下标为3的内容为：7（指向3），3(指向null)


第三步，这步是引起闭环的最终原因，当前处理结点为3，next值为null

        这时使3指向newTable中的7，然后将3存入newTable

      这步处理完后，newTable下标为3的内容为：

    3(指向7)，7(指向3)。


查找时，查找key为11的值，这时查找table下标为3的内容，先找3，不匹配，然后找7.也不对，这时查7指向的3.。。。。

死循环

参考:
【java基础 12】HashMap中是如何形成环形链表的？
http://blog.csdn.net/hhx0626/article/details/54024222

HashMap并发情况下，导致闭环链
http://blog.csdn.net/zhaozhenzuo/article/details/18800063


并发环境下HashMap引起full gc排查
http://blog.lichengwu.cn/java/2015/04/06/case-of-hashmap-in-concurrency/

多线程下HashMap的死循环问题
http://www.cnblogs.com/ITtangtang/p/3966467.html