一个曾经困扰作为初学者的我的一个问题--ArrayList迭代删除元素
一个曾经令我非常疑惑的“ArrayList迭代删除元素”问题。大概就是，在遍历ArrayList的过程中，若数组元素满足条件则将该元素删除。这是一个非常经典的坑，网上也有很多关于这个坑的记录，但在我初学Java的时候确实困扰了我一段时间，（正好是昨晚一位非常喜欢远坂凛且不愿透露姓名的朋友问到过这个问题，手动无限狗头）正巧最近也看了ArrayList和迭代器的源码，写篇文章分享分享。
我们先来康康一段貌似正确的代码
public static void main(String[] args) {
List<Integer> list=new ArrayList<>();
list.add(1);
list.add(2);
list.add(2);
list.add(3);
list.add(4);
list.add(4);
for (int i = 0; i < list.size(); i++) {
//当元素值为2或3时删除该元素
if (list.get(i).equals(2)||list.get(i).equals(3)){
list.remove(i);
}
}
System.out.println(list);
}
为什么说这段代码貌似正确？我们先康康运行结果吧
运行结果
代码中，我们遍历list，在元素为2或3时将该元素删除，咋一看倒没啥毛病，但运行结果显示我们少删了一个2，为什么会少删了一个元素呢？带着这个问题，我们来康康ArrayList的源码。
add方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//增加modCount的值 扩容...
ensureCapacityInternal(size + 1); // Increments modCount!!
//elementData为储存list元素的数组
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//DEFAULTCAPACITY_EMPTY_ELEMENTDATA是一个空Object数组
//该情况表示第一次添加元素
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//DEFAULT_CAPACITY为默认容量 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
//递增modCount 该值用于迭代器的fail-fast
//在后面迭代器会说
modCount++;
// overflow-conscious code
//若该数组所需最小容量大于原数组长度
if (minCapacity - elementData.length > 0)
//扩容
grow(minCapacity);
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//若新容量小于所需最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//若新容量超过容量最大值
if (newCapacity - MAX_ARRAY_SIZE > 0)
//最大化容量
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//将原数组元素复制到新数组中实现扩容
elementData = Arrays.copyOf(elementData, newCapacity);
}
值得注意的是，当未指定ArrayList初始容量时，第一次扩容时数组容量为10，之后的扩容则是将数组容量扩充至原数组容量的1.5倍。
下面是remove方法
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//检查索引
rangeCheck(index);
//递增modCount 用于迭代器fail-fast
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;
}
理解了remove方法之后，我们再回到最开始提出的问题：为什么会少删了一个元素？
1.这是我们最开始创建的ArrayList
1
2.接下来我们遍历List元素，当我们到达元素2时，我们将删除它
2
3.在删除元素2之后，ArrayList会将剩下的元素向前移动，注意此时指针指向的位置
3
4.我们将元素2删除之后，数组剩余元素向前移动，此时指针指向了被删除元素后一个元素
4
5.此时i++，指针向前移动，指向元素3，这时便完美错过了一个元素
5
经过上述分析，我们知道了remove方法的原理之后，我们可以通过从后向前遍历的方法避免该情况。
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(1);
list.add(2);
list.add(2);
list.add(3);
list.add(4);
list.add(4);
for (int index = list.size() - 1; index >= 0; index--) {
Integer integer;
if ((integer = list.get(index)).equals(2) || integer.equals(3)) {
list.remove(index);
}
}
System.out.println(list);
}
亦或是使用迭代器删除元素
public static void main(String[] args) {
List<Integer> list = new ArrayList<>();
list.add(1);
list.add(1);
list.add(2);
list.add(2);
list.add(3);
list.add(4);
list.add(4);
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
Integer integer = (Integer) iterator.next();
if (integer.equals(2) || integer.equals(3)) {
iterator.remove();
}
}
System.out.println(list);
}
迭代器
在ArrayList的add和remove方法中都可以见到modCount的身影，modCount是在迭代器中产生作用的，jdk对于modCount进行了解释：
The number of times this list has been <i>structurally modified</i>.
Structural modifications are those that change the size of the
list, or otherwise perturb it in such a fashion that iterations in
progress may yield incorrect results.
大致意思为：当我们对该list产生结构化调整的时候就会递增modCount的值，结构化调整包括改变list中元素个数。
add和remove方法毫无疑问改变了list元素个数，所以需要对modCount值进行递增操作。而modCount最终会在迭代器iterator中起作用，实现fail-fast机制。
fail-fast
fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。
其中，fail-fast机制并不保证在不同步的修改下一定会抛出异常，顺便提一嘴，成员变量modCount并非volatile修饰，不具备可见性，所以可能存在fail-fast机制失效的情况。
了解了fail-fast，接下来看看迭代器是如何工作的。
List的iterator方法可以放回该list对象的Iterator实例
public Iterator<E> iterator() {
return new Itr();
}
其中Itr为ArrayList的内部类，实现了Interator接口
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() {
//检查expectedModCount 和 modCount 的值是否一致
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();
//检查expectedModCount 和 modCount 的值是否一致
checkForComodification();
try {
//调用ArrayList的remove方法 注意：此时modCount将会递增
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
//再次将expectedModCount 和 modCount 的值设置为一致
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
在迭代器迭代或者删除元素时，频繁地调用checkForComodification方法以检查expectedModCount 和 modCount 的值是否一致，若不一致则代表了有其他操作改变了该list对象中的元素，此时迭代器将会抛出ConcurrentModificationException异常使迭代快速失败，即fail-fast。
所以，我们在使用迭代器删除元素时必须调用迭代器的remove方法，不能使用List的remove方法。
fail-safe
前面说到 fail-fast，就随便提一下 fail-safe 吧
fail-safe 机制保证任何对集合结构的修改都会在一个复制的集合上进行，因此不会抛出 java.util.ConcurrentModificationException 异常。与 fail-safe 机制对应的是 fail-fast 机制。
fail-safe机制产生的两个问题：
- 复制集合会产生大量临时对象，增加系统开销
- 无法保证读取的数据是目前原始数据结构中的数据
其中线程安全的List--CopyOnWriteArrayList的迭代器就是所谓fail-safe机制。
CopyOnWriteArrayList的iterator方法
public Iterator<E> iterator() {
return new COWIterator<E>(getArray(), 0);
}
static final class COWIterator<E> implements ListIterator<E> {
/** Snapshot of the array */
private final Object[] snapshot;
/** Index of element to be returned by subsequent call to next. */
private int cursor;
private COWIterator(Object[] elements, int initialCursor) {
cursor = initialCursor;
snapshot = elements;
}
public boolean hasNext() {
return cursor < snapshot.length;
}
...
@SuppressWarnings("unchecked")
public E next() {
if (! hasNext())
throw new NoSuchElementException();
return (E) snapshot[cursor++];
}
...
}
其中，迭代器遍历的只是数组元素的一张快照而已，所以在并发环境下，不管其他线程对该list做了什么操作，迭代器遍历能够做到不受影响。有空再说说并发容器吧！！！
网友评论