death00 · 2019年09月19日

Java面试-容器的遍历

当我们用增强for循环遍历非并发容器(HashMap、ArrayList等),如果修改其结构,会抛出异常ConcurrentModificationException,因此在阿里巴巴的Java规范中有说到:不要在foreach循环里进行元素的remove/add操作,remove元素请使用Iterator方式。,但是不是真的就不可以在增强for循环中修改结构吗?其原理又是什么呢?
<!-- more -->

ConcurrentModificationException的含义

ConcurrentModificationException可以将其通俗的翻译为并发修改异常,那么关注点就在并发修改了。也许有些人会说,我只是在单线程中修改了,并没有并发操作,但系统也抛了这样的这样的错误,这是为什么呢?别急,我们看看它的源码解释:

This exception may be thrown by methods that have detected concurrent modification of an object when such modification is not permissible.

这个异常就是应用程序在做一些系统不允许的操作时抛出的。记住,只要是系统不允许的操作,就一定会抛错的。

后面有一个值得注意的地方

Note that fail-fast behavior cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast operations throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: ConcurrentModificationException should be used only to detect bugs.

fail-fast(快速失败)并不能一定被保证,所以fail-fast操作会尽最大努力抛出该异常。既然是尽最大努力,因此无论是不是并发操作,只要是修改了,就一定会报错。

既然如此,我们来看看for循环中遍历修改容器结构,系统是如何知道的。

增加for循环的原理

我们来看看增强for循环遍历修改HashMap的代码:

    Map<String, String> hashMap = new HashMap<>(10);
    // 添加
    for (int i = 0; i < 10; i++) {
      hashMap.put("key" + i, "value" + i);
    }
    // 遍历修改
    for (Entry<String, String> entry : hashMap.entrySet()) {
      String key = entry.getKey();
      hashMap.remove(key);
    }

这个时候,你如果运行的话,就会抛出ConcurrentModificationException,这个时候我们需要具体调试一下,发现遍历第一次并删除时没有报错,但第二次遍历,在for循环的括号执行完后,就抛出了异常,这又是为什么呢?

让我们反编译一下class文件,看看究竟增强for循环做了什么:

    Map<String, String> hashMap = new HashMap(10);

    for(int i = 0; i < 10; ++i) {
      hashMap.put("key" + i, "value" + i);
    }

    Iterator var5 = hashMap.entrySet().iterator();
    while(var5.hasNext()) {
      Entry<String, String> entry = (Entry)var5.next();
      String key = (String)entry.getKey();
      hashMap.remove(key);
    }

我们发现,虽然写法上是增强for循环,但实际还是使用的while结合iterator进行遍历,现在我们贴上这个代码进行调试。

发现在第二次var5.next()处抛异常,接下来我们看看next方法究竟做了什么?

HashMap的源码中显示:

    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

    final Node<K,V> nextNode() {
        Node<K,V>[] t;
        Node<K,V> e = next;
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        if (e == null)
            throw new NoSuchElementException();
        if ((next = (current = e).next) == null && (t = table) != null) {
            do {} while (index < t.length && (next = t[index++]) == null);
        }
        return e;
    }

我们注意到,nextNode()方法的第一个判断就决定了是否抛出ConcurrentModificationException,那么modCountexpectedModCount究竟是什么呢?

modCount和expectedModCount

我们来看看modCountexpectedModCount的关系,当我们调用Iterator var5 = hashMap.entrySet().iterator();时,源代码做了什么:

    HashIterator() {
        expectedModCount = modCount;
        Node<K,V>[] t = table;
        current = next = null;
        index = 0;
        if (t != null && size > 0) { // advance to first entry
            do {} while (index < t.length && (next = t[index++]) == null);
        }
    }

在一开始,就让expectedModCount等于modCount,而当我们调用hashMap.remove(key);时,实际上修改了modCount的值:

    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            Node<K,V> node = null, e; K k; V v;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            else if ((e = p.next) != null) {
                if (p instanceof TreeNode)
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else {
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                if (node instanceof TreeNode)
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                else if (node == p)
                    tab[index] = node.next;
                else
                    p.next = node.next;
                ++modCount;
                --size;
                afterNodeRemoval(node);
                return node;
            }
        }
        return null;
    }

modCount增大1,那么,当我们下一次调用var5.next()时,自然就发现modCountexpectedModCount不等了。

修改结构的正确姿势

使用增强for循环,本质还是在使用iterator,那为什么大家都在推介使用iterator.remove()呢?让我们看看源代码:

    public final void remove() {
        Node<K,V> p = current;
        if (p == null)
            throw new IllegalStateException();
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
        current = null;
        K key = p.key;
        removeNode(hash(key), key, null, false, false);
        expectedModCount = modCount;
    }

我们发现,这个remove方法虽然也调用了removeNode,但它在最后一步再次将modCount的值赋给expectedModCount,因此保证了下一次调用next()方法是不抛错。

所以,我们要么就直接显示地使用iterator,用它的remove方法移除对象。如果你实在想用增强for循环遍历删除,那么也只能在删除一个后,立刻退出循环。但无论用哪种方法,当多个线程同时修改时,都会有出错的可能性,因为你即时保证单个线程内的modCountexpectedModCount,但这个操作并不能保证原子性。

总结

如果在多线程环境下,我更推介使用ConcurrentHashMap,因为它没有modCountexpectedModCount的概念,因此,即时你是使用增强for循环遍历删除,也不会出现问题。

有兴趣的话可以关注我的公众号或者头条号,说不定会有意外的惊喜。

推荐阅读
关注数
0
文章数
70
目录
极术微信服务号
关注极术微信号
实时接收点赞提醒和评论通知
安谋科技学堂公众号
关注安谋科技学堂
实时获取安谋科技及 Arm 教学资源
安谋科技招聘公众号
关注安谋科技招聘
实时获取安谋科技中国职位信息