遍历数据时arraylist效率高于linkedlist_遍历问题种类

遍历数据时arraylist效率高于linkedlist_遍历问题种类概述一个java程序猿比较广为人知的小知识,是ArrayList和LinkedList最好使用迭代器删除,而不是遍历删除。当我们尝试使用for循环或者forEach进行删除的

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

概述

一个 java 程序猿比较广为人知的小知识 ,是 ArrayList 和 LinkedList 最好使用迭代器删除,而不是遍历删除。

当我们尝试使用 for 循环或者 forEach 进行删除的时候,往往会出现一些意外的情况,导致集合全部删除失败。关于这点,我一直保持知其然不知其所以然的状态,刚好最近刚看完 ArrayList 和 LinkedList 的源码,今天这篇文章,就结合源码,总结一下 ArrayList 和 LinkedList 的几种错误删除。

一、List 集合的 fast-fail 机制

在开始前,我们需要了解一下集合的 fast-fail 机制。

List 接口有一个 AbstractList 抽象类,List 下的所有实现类都直接或间接的继承了它。

在它的成员变量中,有一个变量叫 modCount,当实现类进行结构性操作的时候——一般指会影响底层数据结构的操作,比如删除——就会+1。

在每一个迭代器创建的时候,会从外部获取当前的 modCount赋给迭代器的成员变量 expectedModCount,然后每次调用迭代器的 next()方法,或者其他增删方法都会比较modCountexpectedModCount是否相等,否则就会抛出 ConcurrentModificationException 异常。

这个并发修改检查可以在出现问题是时候快速抛出异常,避免可能错误的数据进入后续的操作。这也是集合操作中大部分 ConcurrentModificationException 异常的来源。

二、ArrayList 的 for 循环删除

ArrayList 的 remove()有根据下标删除与根据元素删除两种,后者每次删除必然需要先遍历集合,效率非常低,所以这里只讨论前者,也就是根据下标删除的方法。

1.实例

我们知道, ArrayList 底层实现是数组,他又实现了 RandomAccess 的接口,因此官方是推荐使用 for 循环去操作遍历集合的。但是当我们使用 for + 下标删除 ArrayList 中的元素时,会发生“漏删”的问题

我们来模拟一下:

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list); // [b, d]

可见,b 和 d 被跳过了。

2.原因

我们可以看看 ArrayList 中 remove()方法的源码:

public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

我们可以看到他调用了fastRemove()

private void fastRemove(int index) {
    // modCount++
    modCount++;
    int numMoved = size - index - 1;
    // 是否需要移动数组
    if (numMoved > 0)
        // 拷贝并且移动数组
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null;
}

fastRemove()方法里,调用了数组拷贝的方法 System.arraycopy(),他将删除位置后的数组整体前移一位

我们来复原一下这个删除的流程:

ArrayList for循环删除的流程

简单的来说,我把 index = a 的元素删掉了,那么原本 index = a + 1 的元素就会跑到 index = a 的位置,当开始下一次循环的时候,我们以为删的是 indedx = a + 1 的元素,其实是 index = a + 2 的元素,索引发生了“偏移”,这就是“漏删”的原因。

3.解决办法

要避免这种情况,有两种办法:

  • 每次索引偏移以后都手动把 index–;
  • 想办法不让索引“偏移”,也就是不调用 arraycopy()方法。

第一种办法是在偶次操作前让 index–

int size = list.size();
for (int i = 0, j = 0; i < size; i++, j++) {
    list.remove(j);
    if (j % 2 == 0) {
        j--;
    }
}
System.out.println(list); // []

实际上,这个思路也是 ArrayList 中迭代器的 remove() 思路,但是用 for 循环写出来的代码非常繁琐,而且不便于理解。

第二种办法是倒序删除

我们回去看看 fastRemove(),会看到这样一段代码:

int numMoved = size - index - 1;
// 是否需要移动数组
if (numMoved > 0) {
    ... ...
}

实际上,numMoved = szie - 1 - index决定了是否需要移动数组,也就是说,我们传入的 index 只要大于等于 size,就不会引起下标,那样我们可以倒序删除:

for (int i = list.size() - 1; i >= 0; i--) {
    list.remove(i);
}
System.out.println(list); // []

三、ArrayList 的 forEach 删除

1.实例

先说问题,ArrayList 在使用 forEach()循环删除的时候会抛异常:

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    list.forEach(list::remove);
} catch (ConcurrentModificationException e) {
    System.out.println(list); // [b, c, d]
    e.printStackTrace(); // ConcurrentModificationException
}

在删除第二个元素的时候,这段代码抛异常了。

2.原因

ArrayList 的 forEach 方法来自 Collection 的父接口 Iterable,Iterable 的默认显示方式是增强 for 循环,而 ArrayList 重写了这个方法:

public void forEach(Consumer<? super E> action) {
    Objects.requireNonNull(action);
    // 获取当前 modCount
    final int expectedModCount = modCount;
    @SuppressWarnings("unchecked")
    final E[] elementData = (E[]) this.elementData;
    final int size = this.size;
    // 每次循环开始前检查 modCount
    for (int i=0; modCount == expectedModCount && i < size; i++) {
        action.accept(elementData[i]);
    }
    if (modCount != expectedModCount) {
        throw new ConcurrentModificationException();
    }
}

forEach()开始就使用 expectedModCount 记录了方法开始时的 modCount,然后每次循环的时候和循环结束的时候都会判断 modCount == expectedModCount, 我们回头看看 ArrayList 的 remove()方法,会看到在 fastRemove()中开始就让 modCount++了,因此我们不难推断出这整个流程:

  • forEach(),方法调用,此时expectedModCount = modCount = 0
  • 进入 for 循环,判断 expectedModCount = modCount通过,进行第一次遍历
  • action.accept()中我们使用 lambda 表达式传入了 remove()方法,此时删除了第一个元素,并且 modCount++。现在 modCount=1
  • 判断expectedModCount = modCount不通过,跳出循环
  • 判断 modCount != expectedModCount通过,抛出异常

也就说,不止是删除,所有会导致 modCount增加的方法,都不可以在 forEach()中使用

我们可以使用 add()检验看看:

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    list.forEach(list::add); // [a, b, c, d, a]
} catch (ConcurrentModificationException e) {
    System.out.println(list);
    e.printStackTrace(); // ConcurrentModificationException
}

四、ArrayList 的迭代器删除

使用迭代器的方法删除是没问题的,但是如果在迭代器迭代过程中,调用了非迭代器的方法,就会出问题

ArrayList<String> list = new ArrayList<>(Arrays.asList("a","b","c","d"));
try {
    Iterator<String> iterator = list.iterator();
    while (iterator.hasNext()) {
        String s = (String) iterator.next();
        // 使用非iterator的方法删除
        list.remove(s);
    }
} catch (ConcurrentModificationException e) {
    System.out.println(list); // [b, c, d]
    e.printStackTrace(); // ConcurrentModificationException
}

可以看到抛异常了,但是把 list.remove()换成 iterator.remove()就没问题。

我们可以看看 iterator.remove()的源码:

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

    try {
        // 调用外部的remove方法
        ArrayList.this.remove(lastRet);
        cursor = lastRet;
        lastRet = -1;
        // 获取最新的 modCount
        expectedModCount = modCount;
    } catch (IndexOutOfBoundsException ex) {
        throw new ConcurrentModificationException();
    }
}

明显的,相比直接调用外部 remove() ,迭代器内部的 remove()在调用外部的 remove()以后,又更新了 expectedModCount,这个 expectedModCount是个迭代器内部的成员变量,在构造方法执行的时候从外部获取 modCount并赋给他,每一次调用迭代器的 next()方法前都会比较 expectedModCountmodCount,如果不相等就会抛异常。

至此问题就明了了,当我们不使用迭代器内部的 remove()删除节点的时候,modCount更新了,但是expectedModCount,因而在迭代第二个元素的时候就会抛出 ConcurrentModificationException 异常

换句话说,和 forEach()一样,并不是只有 remove()才会引起如此问题,在迭代器迭代过程中,调用任何外部会导致 modCount改变的方法都会使其抛异常。

五、LinkedList 的 for 循环删除

LinkedList 的 for 循环删除也会导致“漏删”

LinkedList<String> list = new LinkedList<>(Arrays.asList("a","b","c","d"));
for (int i = 0; i < list.size(); i++) {
    list.remove(i);
}
System.out.println(list); // [b, d]

和 ArrayList 的 for 循环删除出错的原因一样,也是因为索引发生了“偏移”。但是和 ArrayList 不一样的是,由于 LinkedList 底层实现是链表,所以他不是通过 arraycopy()方法,而是直接解除了前后节点的引用关系:

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

解决方法和 ArrayList 一样,只要避免循环中索引“偏移”即可,ArrayList 中手动 index– 和倒序删除两种办法对他同样适用

六、LinkedList 的 forEach 删除

ArrayList 中的 forEach()是重写了 Iterable 接口的 forEach()方法,但是 LinkedList 中没有重写,所以 LinkedList 的 forEach() 使用的仍然还是 Iterable 接口中提供的实现:

default void forEach(Consumer<? super T> action) {
    Objects.requireNonNull(action);
    for (T t : this) {
        action.accept(t);
    }
}

当我们使用增强 for 循环遍历数组的时候,最终编译以后得到的是 for + 下标的普通 for 循环,而遍历集合则会编译为迭代器版的循环。因此:

// forEach
list.forEach(list::remove);

// 增强for
for (T t : list) {
    list.remove(t);
}

// 迭代器
Iterator<T> iterator = list.listIterator();
while (iterator.hasNext()) {
    list.remove(iterator.next());
}

上面三种写法是等价的。在 LinkedList 中, forEach 遍历和迭代器遍历是等价的,前者到最后还是用的迭代器。而实际上,当我们看到迭代器里面的 list.remove()就应该明白 LinkedList 的 forEach()为什么会抛异常了。

和 ArrayList 的迭代器删除一样,由于调用的是外部的 remove()导致modCount改变,而expectedModCount没有改变,因此在调用next()的时候会因为过不了 expectedModCount = modCount而抛出 ConcurrentModificationException 异常

七、总结

为什么有时候会抛出 ConcurrentModificationException 异常?

List 集合中存在并发修改检查机制,AbstractList 提供 modCount字段,当使用 add()或者 remove()这样结构性操作的方法时,会让 modCount + 1。List 实现类的迭代器在创建的时候,都会使用成员变量 expectedModCount 记录当前的 modCount每次调用 next()的时候都会检查最新的 modCountexpectedModCount是否相等,否则就抛出 ConcurrentModificationException 异常

因此,只有调用迭代器内部提供的方法,才会同步更新expectedModCount,否则只会更新modCount所以 ArrayList 与 LinkedList 在迭代器迭代过程中增删会抛异常

ArrayList 重写了 forEach()方法,从增强 for 改为了普通的 for 循环,但是在方法最开始也记录了modCount,每次循环都会对比,因此也会因为在循环中改变了 modCount而抛异常

LinkedList 未重写 forEach()方法,底层仍然使用增强 for,编译后还是迭代器,因此抛异常的原因同迭代器中操作

为什么普通 for 循环删除会“漏删”?

ArrayList 的删除底层是使用 arraycopy方法生成了一个新数组,新数组上被删除节点以后的全部元素都会前移一位,导致了索引的“偏移”,因此删除了 a,那 a+1 的元素就会调到 a 的位置,下一次删除 a + 1 实际上是删除 a + 2,因此 a + 1 就被跳过了。

LinkedList 是链表,但是删除一个节点也会导致后一个节点“补到”被删除节点的下标对应的位置,因此同样也会因为索引“偏移”而出现“漏删”的情况。

解决方法是有两种,一种是在删除元素以后让索引继续指向当前位置,另一种是倒序删除。

其实如果添加元素的话也会有问题,虽然能够添加成功,但是不会按照指定的顺序插入,这也是因为上面这个原因。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170776.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • sstream读取文件

    sstream读取文件对于如下图所示的数据文件:274表示有274个点对,以下每一行代表一个点对,每一行的四个数从左到右依次是一个第一个点的x坐标、y坐标、第二个点的x坐标、y坐标,现在要把点对数和每个点对读取并存储,具体代码如下:#include<iostream>#include<sstream>#include<fstream>#include<string&…

  • axios实现跨域三种方法_跨域的解决方案

    axios实现跨域三种方法_跨域的解决方案Axios是不允许跨域访问的,别说跨域,跨端口都不行。例如某项目我本地vue前端frontEnd为`localhost:8888`,Java后台backEnd为`localhost:8889`。这个时候就有两个方案了:-修改`frontEnd`前端,支持跨域(通过代理的形式,当然这种是`伪跨域`,但是挺有用,前提是后端不限制即可)。-修改`backEnd`后台,支持跨域(同时限制可跨域名,不在本文讨论范围,且看过往处理方式)。

  • 微信公众平台开发(十) 消息回复总结

    微信公众平台开发(十) 消息回复总结一、简介微信公众平台提供了三种消息回复的格式,即文本回复、音乐回复和图文回复,在这一篇文章中,我们将对这三种消息回复的格式做一下简单讲解,然后封装成函数,以供读者使用。二、思路分析对于每一个POST请

  • acwing1106. 山峰和山谷(宽搜bfs)「建议收藏」

    acwing1106. 山峰和山谷(宽搜bfs)「建议收藏」FGD小朋友特别喜欢爬山,在爬山的时候他就在研究山峰和山谷。为了能够对旅程有一个安排,他想知道山峰和山谷的数量。给定一个地图,为FGD想要旅行的区域,地图被分为 n×n 的网格,每个格子 (i,j) 的高度 w(i,j) 是给定的。若两个格子有公共顶点,那么它们就是相邻的格子,如与 (i,j) 相邻的格子有(i−1,j−1),(i−1,j),(i−1,j+1),(i,j−1),(i,j+1),(i+1,j−1),(i+1,j),(i+1,j+1)。我们定义一个格子的集合 S 为山峰(山谷)当且仅当:

  • VC中获取窗体句柄的各种方法

    VC中获取窗体句柄的各种方法

  • 星际密码[通俗易懂]

    星际密码[通俗易懂]题目:https://www.nowcoder.com/pat/2/problem/254

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号