【代码优化】List.remove() 剖析

一、犯错经历

1.1 故事背景

最近有个需求大致的背景类似:

我已经通过一系列的操作拿到一批学生的考试成绩数据,现在需要筛选成绩大于 95 分的学生名单。

善于写 bug 的我,三下五除二完成了代码的编写:

@Test
public void shouldCompile() {
    for (int i = 0; i < studentDomains.size(); i++) {
        if (studentDomains.get(i).getScore() < 95.0) {
            studentDomains.remove(studentDomains.get(i));
        }
    }
    System.out.println(studentDomains);
}

测试数据中四个学生,成功筛选出了两个 95 分以上的学生,测试成功,打卡下班。

[StudentDomain{id=1, name='李四', subject='科学', score=95.0, classNum='一班'}, StudentDomain{id=1, name='王六', subject='科学', score=100.0, classNum='一班'}]

1.2 貌似,下不了班!

从业 X 年的直觉告诉我,事情没这么简单。

但是自测明明没问题,难道写法有问题?那我换个写法(增强的 for 循环):

@Test
public void commonError() {
    for (StudentDomain student : studentDomains) {
        if (student.getScore() < 95.0) {
            studentDomains.remove(student);
        }
    }
    System.out.println(studentDomains);
}

好家伙,这一试不得了,直接报错:ConcurrentModificationException

  • 普通 for 循环“没问题”,增强 for 循环有问题,难道是【增强 for 循环】的问题?

1.3 普通 for 循环真没问题吗?

为了判断普通 for 循环是否有问题,我将原代码加了执行次数的打印:

@Test
public void shouldCompile() {
    System.out.println("studentDomains.size():" + studentDomains.size());
    int index = 0;
    for (int i = 0; i < studentDomains.size(); i++) {
        index ++;
        if (studentDomains.get(i).getScore() < 95.0) {
            studentDomains.remove(studentDomains.get(i));
        }
    }
    System.out.println(studentDomains);
    System.out.println("执行次数:" + index);
}

这一加不得了,我的 studentDomains.size() 明明等于 4,怎么循环体内只执行了 2 次。

更巧合的是:执行的两次循环的数据,刚好都符合我的筛选条件,故会让我错以为【需求已完成】。

二、问题剖析

一个个分析,我们先看为什么普通 for 循环比我们预计的执行次数要少。

2.1 普通 for 循环次数减少

这个原因其实稍微有点儿开发经验的人应该都知道:在循环中删除元素后,List 的索引会自动变化,List.size() 获取到的 List 长度也会实时更新,所以会造成漏掉被删除元素后一个索引的元素。

比如:循环到第 1 个元素时你把它删了,那么第二次循环本应访问第 2 个元素,但这时实际*问到的是原来 List 的第 3 个元素,因为第 1 个元素被删除了,原来的第 3 个元素变成了现在的第 2 个元素,这就造成了元素的遗漏。

2.2 增强 for 循环抛错

  • 我们先看 JDK 源码中 ArrayListremove() 源码是怎么实现的:
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;
}

只要不为空,程序的执行路径会走到 else 路径下,最终调用 fastRemove() 方法:

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index, numMoved);
    elementData[--size] = null;
}

fastRemove() 方法中,看到第 2 行【把 modCount 变量的值加 1】。

  • 增强 for 循环实际执行

【代码优化】List.remove() 剖析

通过编译代码可以看到:增强 for 循环在实际执行时,其实使用的是Iterator,使用的核心方法是 hasnext()next()

next() 方法调用了 checkForComodification()

final void checkForComodification() {
	if (modCount != expectedModCount)
         throw new ConcurrentModificationException();
 	}

看到 throw new ConcurrentModificationException() 那么就可以结案了:

因为上面的 remove() 方法修改了 modCount 的值,所以这里肯定会抛出异常。

三、正确方式

既然知道了普通 for 循环和增强 for 循环都不能用的原因,那么我们先从这两个地方入手。

3.1 优化普通 for 循环

我们知道使用普通 for 循环有问题的原因是因为数组坐标发生了变化,而我们仍使用原坐标进行操作。

  • 移除元素的同时,变更坐标。
@Test
public void forModifyIndex() {
    for (int i = 0; i < studentDomains.size(); i++) {
        StudentDomain item = studentDomains.get(i);
        if (item.getScore() < 95.0) {
            studentDomains.remove(i);
            // 关键是这里:移除元素同时变更坐标
            i = i - 1;
        }
    }
    System.out.println(studentDomains);
}
  • 倒序遍历

采用倒序的方式可以不用变更坐标,因为:后一个元素被移除的话,前一个元素的坐标是不受影响的,不会导致跳过某个元素。

@Test
public void forOptimization() {
    List<StudentDomain> studentDomains = genData();
    for (int i = studentDomains.size() - 1; i >= 0; i--) {
        StudentDomain item = studentDomains.get(i);
        if (item.getScore() < 95.0) {
            studentDomains.remove(i);
        }
    }
    System.out.println(studentDomains);
}

3.2 使用 Iterator 的 remove()

@Test
public void iteratorRemove() {
    Iterator<StudentDomain> iterator = studentDomains.iterator();
    while (iterator.hasNext()) {
        StudentDomain student = iterator.next();
        if (student.getScore() < 95.0) {
            iterator.remove();
        }
    }
    System.out.println(studentDomains);
}

你肯定有疑问,为什么迭代器的 remove() 方法就可以呢,同样的,我们来看看源码:

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();
    }
}

我们可以看到:每次执行 remove() 方法的时候,都会将 modCount 的值赋值给 expectedModCount,这样 2 个变量就相等了。

3.3 Stream 的 filter()

了解 Stream 的童鞋应该都能想到该方法,这里就不过多赘述了。

@Test
public void streamFilter() {
    List<StudentDomain> studentDomains = genData();
    studentDomains = studentDomains.stream().filter(student -> student.getScore() >= 95.0).collect(Collectors.toList());
    System.out.println(studentDomains);
}

3.4 Collection.removeIf()【推荐】

JDK1.8 中,Collection 以及其子类新加入了 removeIf() 方法,作用是按照一定规则过滤集合中的元素。

@Test
public void removeIf() {
    List<StudentDomain> studentDomains = genData();
    studentDomains.removeIf(student -> student.getScore() < 95.0);
    System.out.println(studentDomains);
}

看下 removeIf() 方法的源码,会发现其实底层也是用的 Iteratorremove() 方法:

default boolean removeIf(Predicate<? super E> filter) {
    Objects.requireNonNull(filter);
    boolean removed = false;
    final Iterator<E> each = iterator();
    while (each.hasNext()) {
        if (filter.test(each.next())) {
            each.remove();
            removed = true;
        }
    }
    return removed;
}

四、总结

详细认真的看完本文的话,最大感悟应该是:还是源码靠谱!

4.1 啰嗦几句

其实在刚从事 Java 开发的时候,这个问题就困扰过我,当时只想着解决问题,所以采用了很笨的方式:

新建一个新的 List,遍历老的 List ,将满足条件的元素放到新的元素中,这样的话,最后也完成了当时的任务。

现在想一想,几年前,如果就像现在一样,抽空好好想想为什么不能直接 remove() ,多问几个为什么,估计自己会比现在优秀很多吧。

当然,只要意识到这个,什么时候都不算晚,共勉!

4.2 文中代码示例

Github/vanDusty

上一篇:boost::fusion::remove用法的测试程序


下一篇:一次for循环使用引发的思考