Java用Iterator遍历集合以及如何保证安全性的原理

硅谷探秘者 算法基础 661 0 0

Java中遍历集合的方式

以list集合为例,有三种遍历方式。

List<String> list=new ArrayList<>();
list.add("2");
list.add("2");
list.add("2");

方式1,增强for循环

for (String s : list) {
    if("2".equals(s)){
        list.remove(s);
    }
}

方式2,for循环

for(int i=0;i<list.size();i++){
    String s=list.get(i);
    if("2".equals(s)){
        list.remove(s);
    }
}

方式3,iterator遍历器

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
    String next = iterator.next();
    if("2".equals(next)){
        iterator.remove();
    }
}

集合遍历过程中删除元素时的安全问题

首先上述三种遍历集合的方式,只有方式3能够安全的删除满足条件的元素。

第一种方式会报一个java.util.ConcurrentModificationException异常,其实增强for循环在遍历元素的时候底层是用迭代器实现的,虽然用迭代器遍历时删除元素是安全的,但是,代码中删除元素还是用的集合原本的remove方法。以至于为什么会报错,下面的文章再讨论。

第二种遍历方式,虽然不会报错,但是却没有完善删除满足条件的元素,由于ArrayList底层使用数组方式实现,当删除其中某一元素时,其余数组下标会前移,导致继续进行删除时会略过下一元素,最终的结果也会异常。

只有第三种方式会正常删除所有满足条件的元素。

Iterator删除元素是如何保证安全的

以ArrayList为例,在获取iterator对象时,底层是创建了一个Itr对象。

public Iterator<E> iterator() {
    return new Itr();
}

Itr主要的属性和方法如下:

private class Itr implements Iterator<E> {
    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such
    int expectedModCount = modCount;
    Itr() {}
    public boolean hasNext() {
        return cursor != size;
    }

    @SuppressWarnings("unchecked")
    public E next() {
        checkForComodification();
        int i = cursor;
        if (i >= size)
            throw new NoSuchElementException();
        Object[] elementData = ArrayList.this.elementData;
        if (i >= elementData.length)
            throw new ConcurrentModificationException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 0)
            throw new IllegalStateException();
        checkForComodification();

        try {
            ArrayList.this.remove(lastRet);
            cursor = lastRet;
            lastRet = -1;
            expectedModCount = modCount;
        } catch (IndexOutOfBoundsException ex) {
            throw new ConcurrentModificationException();
        }
    }
    final void checkForComodification() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }
}

注意到,Itr 中有个 expectedModCount 属性初始化和 ArrayList 的 modCount 属性相等。

modCount属性是做什么用的呢?

从 ArrayList 源码中可以看出,函数中在每次执行 remove,add,clear 方法时,都会对 modCount 加一,其实他就相当于一个记录 ArrayList 版本的变量,每对他进行操作时就会将其加一,表示进行了新的操作。

那么回到 Iterator 中的 expectedModCount,初始化也就对应当前集合的版本。在调用 Iterator 的 next 方法或者 remove 方法时,在实际删除元素之前先进行版本校验(checkForComodification方法),如果版本不一致则会抛出一个异常。就比如在遍历器遍历的时候,又对原集合进行了添加或删除元素的操作,则会导致异常。在实际删除元素之后 Iterator 也会同步一下 ArrayList 的 modCount。因为 Iterator 中 remove 方法删除元素的时候也是调用 ArrayList 的 remove 方法。

其实就是因为在执行Iterator的一些方法之前要对原集合的版本进行校验,所以才能保证操作的安全。

猜你喜欢
java基础 1139 java之TreeMap实现TreeMap实现其实说简单也简单说复杂也复杂,说简单是因为TreeMap底层实现完依靠红黑树这个数据结构,相比与HashMap来说TreeMap不考虑
算法基础 487 只能单向移动。(2)Iterator.remove()是唯一方式来在迭代过程中修改果在迭代过程中其它方式修改了基本将会产生未知行为。而且每调一次next()方法,remov
数据结构与算法 9620 问题:上图一个链表,判断一个链表中是否存在环,求出环入口求出链表长度。方案一:利hash表首先准备一个hash表hashMap等,然后从链表头部链表,每次一个
java虚拟机(jvm) 3639 类加载机制。加载,验,准备,初始化这5个阶段顺序是确定,类加载过程,必须按照这种顺序开始。这些阶段通常是相互交叉和混进行。解析阶段在某些情况下,可在初始化阶段之后再开始---为了支持j
ASM,java基础 482   关于cglib代概念和api,请参考:初步探究cglib动态代:http://www.jiajiajia.club/blog/artical/yjw520
java虚拟机(jvm) 1096 jmap是java虚拟机自带一种内存映像工具,我们可通过该工具配不同参数来查看java虚拟机内存详细信息(程序中出现所有对象数量内存大小等),通过虚拟机内存使情况来定
java基础 1761 学习开发中,灵活熟练地使这些框架,可很明显地提高我们开发效率,当然仅仅会还是不够解其中设计思想与才能更好地提高我们开发水平。1.Collection接口从图中可知道Col
official 434 leetcode第589题题目描述给定一个N叉树,返回其节点值前序。例,给定一个3叉树:返回其前序:[1,3,5,6,2,4]。解题思路递归,深度优先搜索代码(java
归档
2018年11月  12 2018年12月  33 2019年01月  28 2019年02月  28 2019年03月  32 2019年04月  27 2019年05月  33 2019年06月  6 2019年07月  12 2019年08月  12 2019年09月  21 2019年10月  8 2019年11月  15 2019年12月  25 2020年01月  9 2020年02月  5 2020年03月  16 2020年04月  4 2020年06月  1 2020年07月  7 2020年08月  13 2020年09月  9 2020年10月  5 2020年12月  3 2021年01月  1 2021年02月  5 2021年03月  7 2021年04月  4 2021年05月  4 2021年06月  1 2021年07月  7 2021年08月  2 2021年09月  8 2021年10月  9 2021年11月  16 2021年12月  14 2022年01月  7 2022年05月  1 2022年08月  3 2022年09月  2 2022年10月  2
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。