浅谈HashMap在高并发下的问题

前言

总所周知,HashMap不是线程安全的,在高并发情况下会出现问题。特别是,在java1.7中,多线程的HashMap会出现CPU 100%的严重问题。这个问题是怎样产生的,后续版本还会有这个问题吗(指java8及后续版本)?下面就来用通俗的语言讲解下。

解析

关于这个问题,是由于java7多线程扩容机制下链表变为循环链表,再获取该链表导致的。

看下java7中扩容的代码。java7中HashMap的实现为数组+链表的形式,没有红黑树。

java7扩容的原则很简单,新数组长度为原数组2倍。遍历原数组,将数组每个位置(有可能为空,有可能只有一个数组,有可能是一个链表)重新哈希,放到对应的新数组上。全部遍历完后更改数组指针,指向新数组。需要注意的是,这里重哈希将链表元素放到新数组,使用的是头插法。

// 扩容核心方法,基本思想就是遍历数据,使用头插法将旧数组元素移到新数组。
 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]; // 头插法,新节点next指向该位置首节点
                newTable[i] = e; // 新元素归位
                e = next; // 指向下一个节点,继续遍历
            }
        }
    }
   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);
    }

这里处理的话,如果单线程情况下不会有问题。如果在多线程情况下,会导致链表在扩容过程中形成循环链表。

形成循环链表的原因在于多线程和头插法。试想,两个线程在添加元素时,同时发现该扩容了,然后同时发起扩容过程。由上述代码可知,扩容完成之前是在自己的线程里创建一个新数组。等扩容完成后(也就是将原数组元素迁移到新数组后)再更改指针指向新扩容数组。

举例初始HashMap是这样的

59DC065A-B9CE-99E9-6A85-21AD5974853C.png

假设两个线程同时扩容,一个线程扩容到一半后被挂起。(标识了某链表的e和next),另一个线程执行扩容,且完成了扩容。

BB02CF31-EDEF-C142-3404-88D95595ED29.png

红色的数组和元素表示线程1,也就是扩容一半挂起的线程,而线程二已完成扩容。观察完成扩容的线程二,在3的位置,该链表的位置顺序已经改变(原数组顺讯为3->7,现在反过来了,这是使用头插法的效果,你也可以对着代码试试)。从图中也可以看出,线程1,2分别创建了自己的新数组,并在自己的新数组中完成扩容。

这时线程1开始执行。熟悉下它即将执行的代码。

// transfer 方法循环部分
         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]; // 头插法,新节点next指向该位置首节点
                newTable[i] = e; // 新元素归位
                e = next; // 指向下一个节点,继续遍历
            }

下面线程1将使用头插法将元素插入线程1新建的数组中去。注意此时e指向的是Key3,next指向的是Key7。不用想也知道后面操作会有问题。因为现在的next指针指的不是e的下一个元素,而是它的前一个元素!

如果继续走代码的话,把Key3(当前e指向元素)放入新数组后,再把Key7放入新数组,后面会放哪个元素?当然又是Key3了,因为Key7next是Key3,这样就形成了死循环。

7A4529A9-1C36-7BE7-B5C5-47C76EA55460.png

java8的改进
  1. 添加了红黑树,当链表长度大于8时,会将链表转为红黑树。
  2. 扩容后,新数组中的链表顺序依然与旧数组中的链表顺序保持一致。具体JDK8是用 head 和 tail 来保证链表的顺序和之前一样,这样就不会产生循环引用。也就没有死循环了。
  3. 虽然修复了死循环的BUG,但是HashMap 还是非线程安全类,仍然会产生数据丢失等问题。
收藏 (0)
评论列表
正在载入评论列表...
我是有底线的