HashMap modCount fast-fail 非原子性论证

技术博客已迁移至个人页，欢迎查看 yloopdaed.icu

您也可以关注 JPP - 这是一个Java养成计划，需要您的加入。

前言

HashMap源码中定义的成员变量并不多，其中我们最不熟悉的应该就是modCount，那么它到底是做什么的呢？

modCount

如果你没时间思考这篇文章，你可以直接跳转到 9.结论处

modCount

modCount在HashMap中记录的是HashMap对象被修改的次数，这里专业的说法是集合在结构上修改时被会记录在modCount中。

文中源码版本为 JDK1.7，modCount的部分在JDK1.8中作用是相同的。只因为JDK1.7中源码比较简洁，所以本文选用JDK1.7来缩减篇幅。

在源码中记录到的modCount++的方法包括：

HashMap put方法[图片上传中...(modcount.jpg-dff60f-1604249139377-0)]
HashMap的remove->removeEntryForKey方法通过key移除元素
HashMap的removeMapping方法，通过object移除元素
HashMap的clear方法

从这里可以看出，结构上的修改主要是添加和删除两部分。

线程不安全

我们都知道在JDK1.7中HashMap是线程不安全的，这个 不安全 我是分两方面理解的：

1 多线程数组扩容时出现循环链表问题

因为扩容时链表顺序会反转，所以多线程操作时可能会出现循环链表的情况，那么在get方法时就会死循环

JDK1.8中也修复了这个问题

2 多线程读写时造成数据混乱的问题

HashMap中有引入了一个 fast-fail 的概念，目的是避免高并发读写造成的数据错乱的隐患。

expectedModCount

expectedModCount这个变量被记录在HashIterator迭代器中。顾名思义，表示期望的修改次数，当期望修改的次数不等于实际修改的次数时，就会触发 fast-fail 快速失败的容错处理

fast-fail

final Entry<K,V> nextEntry() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
    ...
}

迭代器调用 next() 方法时会调用 nextEntry() 方法，方法中首先会判断 modCount 与 expectedModCount 是否相等

如果不相等直接抛出 java.util.ConcurrentModificationException 异常

GeeksForGeeks中的解释为：

In multi threaded environment, if during the detection of the resource, any method finds that there is a concurrent modification of that object which is not permissible, then this ConcurrentModificationException might be thrown.

If this exception is detected, then the results of the iteration are undefined.

Generally, some iterator implementations choose to throw this exception as soon as it is encountered, called fail-fast iterators.

For example: If we are trying to modify any collection in the code using a thread, but some another thread is already using that collection, then this will not be allowed.

在多线程环境中，如果在检测资源期间，任何方法发现该对象存在并发修改，而这是不允许的，则可能会抛出此ConcurrentModificationException。

1 如果检测到此异常，则迭代结果不确定。

2 通常，某些迭代器实现选择将遇到此异常的异常立即抛出，称为快速失败迭代器。

例如：如果我们试图使用一个线程来修改代码中的任何集合，但是另一个线程已经在使用该集合，则将不允许这样做。

验证

相关代码可以在 JPP/ConcurrentModificationExceptionDemo类中查看。

HashMap m = new HashMap();
for (int i = 0; i <100 ; i++) {
    m.put(String.valueOf(i), "value"+i);
}

new Thread(new Runnable() {
    @Override
    public void run() {
        Iterator iterator = m.keySet().iterator();
        while (iterator.hasNext()) {
            String next = (String) iterator.next();
            if (Integer.parseInt(next) % 2 == 0) {
                System.out.println("thread 1");
                iterator.remove();
            }
        }
    }
}).start();

new Thread(new Runnable() {
    @Override
    public void run() {
        Iterator iterator  = m.keySet().iterator();
        while (iterator.hasNext()) {
            String next = (String) iterator.next();
            System.out.println(m.get(next));
        }
    }
}).start();

这里第一个线程中的 System.out.println("thread 1"); 的作用是 触发数据和内存同步。

这部分内容和寄存器的 缓存行 知识有关，如果不触发数据和内存同步，第二个线程无法正确获取modCount。

单线程错误案例

HashMap m = new HashMap();
m.put("key1", "value2");
m.put("key2", "value2");
for (String key: m.keySet()) {
    if (key.equals("key2")) {
        m.remove(key);
    }
}

这个代码块也有可能发生 fast-fail

我们来看一下上面代码块编译后的class文件

HashMap m = new HashMap();
m.put("key1", "value2");
m.put("key2", "value2");
Iterator i$ = m.keySet().iterator();
while(i$.hasNext()) {
    Object key = i$.next();
    if (key.equals("key2")) {
        m.remove(key);
    }
}

这么看应该就很容易理解了，而且这个错误也很容易发生。

在迭代器遍历的过程中，会将key值为“key2”的元素移除。移除时调用的HashMap的remove方法会对modCount值+1，但是这个方法并不会同步expectedModCount的值。所以在下一次迭代器调用i$.next();方法时，会发生异常。

expectedModCount // For fast-fail：在以下方法会同步modCount值

HashIterator的构造方法
HashIterator的remove方法

所以将上面移除元素的代码。替换为 i$.remove(); 就可以了。

思考

关于 i++ 计算不是原子性的怀疑：

HashMap源码记录modCount++这个计算方式在多线程操作时如果不能保证原子性，那么岂不是也有可能触发ConcurrentModificationException异常？

验证过程：
1 因为HashMap的put操作会进行modCount++
2 modCount声明时也没有指明volatile
那么多线程put是否会造成modCount的值不准确？

相关代码可以在 JPP/ConcurrentModificationExceptionDemo类中查看。

static void atomicTest() throws InterruptedException {

    HashMap m = new HashMap();

    new Thread(new Runnable() {
        @Override
        public void run() {
            for (int i = 0; i < 10000; i++) {
                // System.out.println(i);
                m.put(i, String.valueOf(i).hashCode());
            }
        }
    }).start();

    new Thread(new Runnable() {
        @Override
        public void run() {
            for (int i = 10000; i < 20000; i++) {
                // System.out.println(i);
                m.put(i, String.valueOf(i).hashCode());
            }
        }
    }).start();

    Thread.sleep(5000);
    Iterator iterator = m.keySet().iterator();
    iterator.next(); // 对比modCount
}

运行的结果是，如果循环次数不多，最后可以保证modCount的数值正确。但是提升循环插入的次数，会锁住一个线程，导致其他线程的数据没有插入成功，但是modCount的值依然是正确的。

~~具体这个魂循环次数设定的阈值，我也没有过多尝试。至少目前我没有因为++计算不是原子性的原因出现过fast-fail~~

运行结果有意外收获:

modcount++.jpg

从上图可以看出，不仅在多线程写入的时候modCount的值无法保证（从expectedModCount看出），而且HashMap的size也不满足期望（因为多线程put时，两个线程的key不重复）

为了再次证明我的猜测，可以在多线程中添加 System.out.println(i); 代码，来达到内存同步的目的

结果不出所料：

sysmodcount++.jpg

结论

1 HashMap多线程读写时可能会抛出ConcurrentModificationException异常，这是fast-fail快速失败机制。

2 fast-fail实现的原理是判断modCount和expectedModCount是否相等

3 modCount++在多线程操作时无法保证原子性，甚至HashMap整个put方法都出现了问题

PS：所以在JDK1.7的ConcurrentHashMap中出现大量 UNSAFE 和 volatile 关键字。

最后

上文所有代码片段都是基于JDK1.7，虽然JDK1.8中对HashMap做了较大的改动。但是文章的思路和结论都是相同的。