一道面试题引发的思考

Java基础

浏览数:154

2019-5-13

AD:资源代下载服务

一、背景及题目

首先我们给出这道面试题的代码以及题目:

List<String> a = new ArrayList<String>(); 
list.add("1");
list.add("2");
for (String item : list) {
    if ("1".equals(item)) { list.remove(item);
    } 
}

问:上段代码运行会报错吗?如果把”1”换成“2”会报错吗?为什么?

二、解开这段代码背后的秘密

首先给出答案:

  1. 上面这段代码运行不会报错。

  2. 把”1”换成“2”再运行就会报错。

为什么呢?那么我们怎么来发现它背后的秘密呢?答案只有一个:那就是通过源码来解惑(ArrayList部分源码)。

public E remove(int index) {
    rangeCheck(index);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}

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

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; // clear to let GC do its work
}
/**
 * An optimized version of AbstractList.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;

    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();
    }
}
  • 我们知道,foreach循环其实是走的list的迭代器进行循环的。

  • 迭代器中有一个”指针”:cursor来记录当前遍历到了哪个位置,还有一个lastRet变量来表示上次返回的值的位置。

  • foreach每次循环时先调用迭代器的hastNext()方法,判断cursor != size。

  • 然后调用迭代器的next()方法,在方法中会首先调用checkForComodification()判断是否要抛出ConcurrentModificationException(判断条件是modCount != expectedModCount,默认两个值相等),然后修改cursor和lastRet变量的值,并返回下一个元素的值。

  • ArrayList的remove()方法会去把modCount增加1,若再次进行第3步则抛异常。

  • 但删除倒数第二个元素时remove()后size-1,所以会导致在hasNext()方法返回false,最后一个值不遍历,不遍历也就意味着不会调用checkForComodification()。

  • 迭代器中的remove()方法会把cursor修改为lastRet,然后把modCount修改为expectedModCount,所以无论怎么删除都不会出错。

  • 遍历下标remove(index)方法不会走迭代器,所以无论怎么删除也不会出错。

三、总结

  我们通过查询ArrayList的源码,可以清楚的知道,它的内部是有一个迭代器类的,然后它的底层其实就是一个数组而已。对于要删除一个ArrayList中的某些元素的时候,我们可以通过遍历下标,找到要删除的元素,直接通过下标删除,或者通过ArrayList的迭代器进行删除,千万不能直接用foreach遍历删除。还有就是遇见问题看到表象要想着去找本质,懂了原理才能知其然知其所以然。

作者:阿豪聊干货