专栏首页健程之道Java中容器的遍历

Java中容器的遍历

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

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的关系,当我们调用 Iteratorvar5=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循环遍历删除,也不会出现问题。

本文分享自微信公众号 - 健程之道(JianJianCoder),作者:健健

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-04-22

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 力扣560——和为K的子数组

    给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

    健程之道
  • 力扣494——目标和

    给定一个非负整数数组,a1, a2, ..., an, 和一个目标数,S。现在你有两个符号 + 和 -。对于数组中的任意一个整数,你都可以从 + 或 -中选择一...

    健程之道
  • 力扣213——打家劫舍 II

    你是一个专业的小偷,计划偷窃沿街的房屋,每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈,这意味着第一个房屋和最后一个房屋是紧挨着的。同时,相邻的房屋装有...

    健程之道
  • 桶排序的单链表实现及其变种

    《算法导论》CLRS 第八章 线性时间排序 8.4 桶排序 桶排序的思想就是把区间[0, 1)划分成n个相同大小的子区间,每一个区间称为桶(buck...

    Enjoy233
  • Js基础教程之for循环语句

    老雷PHP全栈开发
  • 素数(质数)筛选法模板

    echobingo
  • 【最新】人工智能领域顶会AAAI 2018 Pre-Proceedings 论文列表(附pdf下载链接)

    【导读】人工智能领域顶尖学术会议 AAAI 2018,暨第32届 AAAI 大会将于 2 月 2 日 - 2 月 7 日 在新奥尔良举行。AAAI 是由人工智能...

    WZEARW
  • 使用 Satis 创建 Composer 私有库

    创建好之后,可以托管到任意的VCS仓库里,如:GIT、SVN等,也可以放在本地以Path的方式指定路径,更多可参考:点击这里

    俗可耐
  • Leetcode 994. 腐烂的橘子

    腐烂橘子的传播以一种类似广播扩散的形式进行。这里不妨以队列来模拟腐烂橘子的扩散过程,队列中存储新的被感染的橘子,则队列为空时表示扩散停止。此时若网格中仍有新鲜橘...

    zhipingChen
  • 情绪识别这么高级,为什么非要监控高中生课堂?

    最近,杭州第十一中学试行的慧眼系统,通过教室内安装组合摄像头,捕捉学生在课堂上的表情和动作,借助人脸识别技术,采集学生的 6 种课堂行为和 7 种课堂表情。

    HyperAI超神经

扫码关注云+社区

领取腾讯云代金券