写点什么

女朋友跟我吐槽 Java 中 ArrayList 遍历时删除元素的各种姿势

用户头像
NotFound9
关注
发布于: 2020 年 06 月 03 日
女朋友跟我吐槽Java中ArrayList遍历时删除元素的各种姿势

> 本文已收录到 1.1K Star 数开源学习指南——《大厂面试指北》,如果想要了解更多大厂面试相关的内容及获取《大厂面试指北》离线 PDF 版,可以扫码进下面群领取


简介

我们在项目开发过程中,经常会有需求需要删除 ArrayList 中的某个元素,而使用不正确的删除方式,就有可能抛出异常。以及在面试中,经常会遇到面试官询问 ArrayList 遍历时如何正确删除元素。所以在本篇文章中,我们会对几种删除元素的方式进行测试,并对原理进行研究,希望可以帮助到大家!


ArrayList 遍历时删除元素的几种姿势

首先结论如下:


第 1 种方法 - 普通 for 循环正序删除(结果:会漏掉元素判断)


第 2 种方法 - 普通 for 循环倒序删除(结果:正确删除)


第 3 种方法 - for-each 循环删除(结果:抛出异常)


第 4 种方法 - Iterator 遍历,使用 ArrayList.remove()删除元素(结果:抛出异常)


第 5 种方法 - Iterator 遍历,使用 Iterator 的 remove 删除元素(结果:正确删除)


下面让我们来详细探究一下原因吧!


首先初始化一个数组 arrayList,假设我们要删除等于 3 的元素。

   public static void main(String[] args) {        ArrayList<Integer> arrayList = new ArrayList();        arrayList.add(1);        arrayList.add(2);        arrayList.add(3);        arrayList.add(3);        arrayList.add(4);        arrayList.add(5);        removeWayOne(arrayList);    }
复制代码


第 1 种方法 - 普通 for 循环正序删除(结果:会漏掉元素判断)


for (int i = 0; i < arrayList.size(); i++) {	if (arrayList.get(i) == 3) {//3是要删除的元素		arrayList.remove(i);		//解决方案: 加一行代码i = i - 1; 删除元素后,下标减1	}    System.out.println("当前arrayList是"+arrayList.toString());}//原ArrayList是[1, 2, 3, 3, 4, 5]//删除后是[1, 2, 3, 4, 5]
复制代码

输出结果:

当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]
复制代码

可以看到少删除了一个 3,


原因在于调用 remove 删除元素时,remove 方法调用 System.arraycopy()方法将后面的元素移动到前面的位置,也就是第二个 3 会移动到数组下标为 2 的位置,而在下一次循环时,i+1 之后,i 会为 3,不会对数组下标为 2 这个位置进行判断,所以这种写法,在删除元素时,被删除元素 a 的后一个元素 b 会移动 a 的位置,而 i 已经加 1,会忽略对元素 b 的判断,所以如果是连续的重复元素,会导致少删除。


解决方案


可以在删除元素后,执行 i=i-1,使得下次循环时再次对该数组下标进行判断。


第 2 种方法 - 普通 for 循环倒序删除(结果:正确删除)


 for (int i = arrayList.size() -1 ; i>=0; i--) {    if (arrayList.get(i).equals(3)) {        arrayList.remove(i);    }    System.out.println("当前arrayList是"+arrayList.toString());}
复制代码

输出结果:

当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]当前arrayList是[1, 2, 4, 5]当前arrayList是[1, 2, 4, 5]当前arrayList是[1, 2, 4, 5]
复制代码


这种方法可以正确删除元素,因为调用 remove 删除元素时,remove 方法调用 System.arraycopy()将被删除元素 a 后面的元素向前移动,而不会影响元素 a 之前的元素,所以倒序遍历可以正常删除元素。


第 3 种方法 - for-each 循环删除(结果:抛出异常)


public static void removeWayThree(ArrayList<Integer> arrayList) {    for (Integer value : arrayList) {        if (value.equals(3)) {//3是要删除的元素            arrayList.remove(value);        }    System.out.println("当前arrayList是"+arrayList.toString());    }}
复制代码

输出结果:

当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]Exception in thread "main" java.util.ConcurrentModificationException	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)	at java.util.ArrayList$Itr.next(ArrayList.java:851)	at com.test.ArrayListTest1.removeWayThree(ArrayListTest1.java:50)	at com.test.ArrayListTest1.main(ArrayListTest1.java:24)
复制代码


会抛出 ConcurrentModificationException 异常,主要在于 for-each 的底层实现是使用 ArrayList.iterator 的 hasNext()方法和 next()方法实现的,我们可以使用反编译进行验证,对包含上面的方法的类使用以下命令反编译验证


javac ArrayTest.java//生成ArrayTest.class文件javap -c ArrayListTest.class//对class文件反编译
复制代码


得到 removeWayThree 方法的反编译代码如下:


 public static void removeWayThree(java.util.ArrayList<java.lang.Integer>);    Code:       0: aload_0       1: invokevirtual #12   // Method java/util/ArrayList.iterator:()Ljava/util/Iterator;       4: astore_1       5: aload_1       6: invokeinterface #13,  1 // InterfaceMethod java/util/Iterator.hasNext:()Z   调用Iterator.hasNext()方法      11: ifeq          44      14: aload_1      15: invokeinterface #14,  1 // InterfaceMethod java/util/Iterator.next:()Ljava/lang/Object;调用Iterator.next()方法      20: checkcast     #9                  // class java/lang/Integer      23: astore_2      24: aload_2      25: iconst_3      26: invokestatic  #4                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;      29: invokevirtual #10                 // Method java/lang/Integer.equals:(Ljava/lang/Object;)Z       32: ifeq          41      35: aload_0      36: aload_2      37: invokevirtual #15                 // Method java/util/ArrayList.remove:(Ljava/lang/Object;)Z      40: pop      41: goto          5      44: return
复制代码


可以很清楚得看到 Iterator.hasNext()来判断是否还有下一个元素,和 Iterator.next()方法来获取下一个元素。而因为在删除元素时,remove()方法会调用 fastRemove()方法,其中会对 modCount+1,代表对数组进行了修改,将修改次数+1。


 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}

复制代码


而当删除完元素后,进行下一次循环时,会调用下面源码中 Itr.next()方法获取下一个元素,会调用 checkForComodification()方法对 ArrayList 进行校验,判断在遍历 ArrayList 是否已经被修改,由于之前对 modCount+1,而 expectedModCount 还是初始化时 ArrayList.Itr 对象时赋的值,所以会不相等,然后抛出 ConcurrentModificationException 异常。


那么有什么办法可以让 expectedModCount 及时更新呢?


可以看到下面 Itr 的源码中,在 Itr.remove()方法中删除元素后会对 expectedModCount 更新,所以我们在使用删除元素时使用 Itr.remove()方法来删除元素就可以保证 expectedModCount 的更新了,具体看第 5 种方法。


private class Itr implements Iterator<E> {        int cursor;       // 游标        int lastRet = -1; // index of last element returned; -1 if no such        int expectedModCount = modCount;//期待的modCount值
public boolean hasNext() { return cursor != size; }
@SuppressWarnings("unchecked") public E next() { checkForComodification();//判断expectedModCount与当前的modCount是否一致 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;//更新expectedModCount } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } }
final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }
复制代码


第 4 种方法 - Iterator 遍历,使用 ArrayList.remove()删除元素(结果:抛出异常)


Iterator<Integer> iterator = arrayList.iterator();while (iterator.hasNext()) {    Integer value = iterator.next();    if (value.equals(3)) {//3是要删除的元素    		arrayList.remove(value);    }    System.out.println("当前arrayList是"+arrayList.toString());}
复制代码

输出结果:

当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]Exception in thread "main" java.util.ConcurrentModificationException	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)	at java.util.ArrayList$Itr.next(ArrayList.java:851)	at com.test.ArrayListTest1.removeWayFour(ArrayListTest1.java:61)	at com.test.ArrayListTest1.main(ArrayListTest1.java:25)
复制代码


第 3 种方法在编译后的代码,其实是跟第 4 种是一样的,所以第四种写法也会抛出 ConcurrentModificationException 异常。这种需要注意的是,每次调用 iterator 的 next()方法,会导致游标向右移动,从而达到遍历的目的。所以在单次循环中不能多次调用 next()方法,不然会导致每次循环时跳过一些元素,我在一些博客里面看到了一些错误的写法,比如这一篇《在ArrayList的循环中删除元素,会不会出现问题?》文章中:



先调用 iterator.next()获取元素,与 elem 进行比较,如果相等,再调用 list.remove(iterator.next());来移除元素,这个时候的 iterator.next()其实已经不是与 elem 相等的元素了,而是后一个元素了,我们可以写个 demo 来测试一下


ArrayList<Integer> arrayList = new ArrayList();arrayList.add(1);arrayList.add(2);arrayList.add(3);arrayList.add(4);arrayList.add(5);arrayList.add(6);arrayList.add(7);
Integer elem = 3;Iterator iterator = arrayList.iterator();while (iterator.hasNext()) { System.out.println(arrayList); if(iterator.next().equals(elem)) { arrayList.remove(iterator.next()); }}
复制代码


输出结果如下:


[1, 2, 3, 4, 5, 6, 7][1, 2, 3, 4, 5, 6, 7][1, 2, 3, 4, 5, 6, 7][1, 2, 3, 5, 6, 7]Exception in thread "main" java.util.ConcurrentModificationException	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:901)	at java.util.ArrayList$Itr.next(ArrayList.java:851)	at com.test.ArrayListTest1.main(ArrayListTest1.java:29)
复制代码


可以看到移除的元素其实不是 3,而是 3 之后的元素,因为调用了两次 next()方法,导致游标多移动了。所以应该使用 Integer value = iterator.next();将元素取出进行判断。


第 5 种方法 - Iterator 遍历,使用 Iterator 的 remove 删除元素(结果:正确删除)


Iterator<Integer> iterator = arrayList.iterator();while (iterator.hasNext()) {    Integer value = iterator.next();    if (value.equals(3)) {//3是需要删除的元素        iterator.remove();    }}
复制代码

输出结果:

当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 3, 4, 5]当前arrayList是[1, 2, 3, 4, 5]当前arrayList是[1, 2, 4, 5]当前arrayList是[1, 2, 4, 5]当前arrayList是[1, 2, 4, 5]
复制代码

可以正确删除元素。


跟第 3 种和第 4 种方法的区别在于是使用 iterator.remove();来移除元素,而在 remove()方法中会对 iterator 的 expectedModCount 变量进行更新,所以在下次循环调用 iterator.next()方法时,expectedModCount 与 modCount 相等,不会抛出异常。


HashMap 遍历时删除元素的几种姿势

首先结论如下:


第 1 种方法 - for-each 遍历 HashMap.entrySet,使用 HashMap.remove()删除(结果:抛出异常)。


第 2 种方法-for-each 遍历 HashMap.keySet,使用 HashMap.remove()删除(结果:抛出异常)。


第 3 种方法-使用 HashMap.entrySet().iterator()遍历删除(结果:正确删除)。


下面让我们来详细探究一下原因吧!


HashMap 的遍历删除方法与 ArrayList 的大同小异,只是 api 的调用方式不同。首先初始化一个 HashMap,我们要删除 key 包含"3"字符串的键值对。

HashMap<String,Integer> hashMap = new HashMap<String,Integer>();hashMap.put("key1",1);hashMap.put("key2",2);hashMap.put("key3",3);hashMap.put("key4",4);hashMap.put("key5",5);hashMap.put("key6",6);
复制代码

第 1 种方法 - for-each 遍历 HashMap.entrySet,使用 HashMap.remove()删除(结果:抛出异常)

for (Map.Entry<String,Integer> entry: hashMap.entrySet()) {        String key = entry.getKey();        if(key.contains("3")){            hashMap.remove(entry.getKey());        }     System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);
}
复制代码

输出结果:

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key1=1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key2=2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key5=5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前entry是key6=6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是key3=3Exception in thread "main" java.util.ConcurrentModificationException	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)	at java.util.HashMap$EntryIterator.next(HashMap.java:1463)	at java.util.HashMap$EntryIterator.next(HashMap.java:1461)	at com.test.HashMapTest.removeWayOne(HashMapTest.java:29)	at com.test.HashMapTest.main(HashMapTest.java:22)
复制代码


第 2 种方法-for-each 遍历 HashMap.keySet,使用 HashMap.remove()删除(结果:抛出异常)

Set<String> keySet = hashMap.keySet();for(String key : keySet){    if(key.contains("3")){        keySet.remove(key);    }    System.out.println("当前HashMap是"+hashMap+" 当前key是"+key);}
复制代码

输出结果如下:

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key3=3, key4=4} 当前key是key6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前key是key3Exception in thread "main" java.util.ConcurrentModificationException	at java.util.HashMap$HashIterator.nextNode(HashMap.java:1429)	at java.util.HashMap$KeyIterator.next(HashMap.java:1453)	at com.test.HashMapTest.removeWayTwo(HashMapTest.java:40)	at com.test.HashMapTest.main(HashMapTest.java:23)
复制代码

第 3 种方法-使用 HashMap.entrySet().iterator()遍历删除(结果:正确删除)

Iterator<Map.Entry<String, Integer>> iterator  = hashMap.entrySet().iterator();while (iterator.hasNext()) {    Map.Entry<String, Integer> entry = iterator.next();    if(entry.getKey().contains("3")){        iterator.remove();    }    System.out.println("当前HashMap是"+hashMap+" 当前entry是"+entry);}
复制代码

输出结果:

当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key1=1当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key2=2当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key5=5当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key6=6当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4, deletekey=3} 当前entry是key4=4当前HashMap是{key1=1, key2=2, key5=5, key6=6, key4=4} 当前entry是deletekey=3
复制代码

第 1 种方法和第 2 种方法抛出 ConcurrentModificationException 异常与上面 ArrayList 错误遍历-删除方法的原因一致,HashIterator 也有一个 expectedModCount,在遍历时获取下一个元素时,会调用 next()方法,然后对

expectedModCount 和 modCount 进行判断,不一致就抛出 ConcurrentModificationException 异常。

abstract class HashIterator {    Node<K,V> next;        // next entry to return    Node<K,V> current;     // current entry    int expectedModCount;  // for fast-fail    int index;             // current slot
HashIterator() { expectedModCount = modCount; Node<K,V>[] t = table; current = next = null; index = 0; if (t != null && size > 0) { // advance to first entry do {} while (index < t.length && (next = t[index++]) == null); } }
public final boolean hasNext() { return next != null; }
final Node<K,V> nextNode() { Node<K,V>[] t; Node<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); if ((next = (current = e).next) == null && (t = table) != null) { do {} while (index < t.length && (next = t[index++]) == null); } return e; }
public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; }}
复制代码


PS:ConcurrentModificationException 是什么?


根据 ConcurrentModificationException 的文档介绍,一些对象不允许并发修改,当这些修改行为被检测到时,就会抛出这个异常。(例如一些集合不允许一个线程一边遍历时,另一个线程去修改这个集合)。


一些集合(例如 Collection, Vector, ArrayList,LinkedList, HashSet, Hashtable, TreeMap, AbstractList, Serialized Form)的 Iterator 实现中,如果提供这种并发修改异常检测,那么这些 Iterator 可以称为是"fail-fast Iterator",意思是快速失败迭代器,就是检测到并发修改时,直接抛出异常,而不是继续执行,等到获取到一些错误值时在抛出异常。


异常检测主要是通过 modCount 和 expectedModCount 两个变量来实现的,


  • modCount

集合被修改的次数,一般是被集合(ArrayList 之类的)持有,每次调用 add(),remove()方法会导致 modCount+1


  • expectedModCount

期待的 modCount,一般是被 Iterator(ArrayList.iterator()方法返回的 iterator 对象)持有,一般在 Iterator 初始化时会赋初始值,在调用 Iterator 的 remove()方法时会对 expectedModCount 进行更新。(可以看看上面的 ArrayList.Itr 源码)


然后在 Iterator 调用 next()遍历元素时,会调用 checkForComodification()方法比较 modCount 和 expectedModCount,不一致就抛出 ConcurrentModificationException。


单线程操作 Iterator 不当时也会抛出 ConcurrentModificationException 异常。(上面的例子就是)

WechatIMG4995.jpeg

总结

因为 ArrayList 和 HashMap 的 Iterator 都是上面所说的“fail-fast Iterator”,Iterator 在获取下一个元素,删除元素时,都会比较 expectedModCount 和 modCount,不一致就会抛出异常。


所以当使用 Iterator 遍历元素(for-each 遍历底层实现也是 Iterator)时,需要删除元素,一定需要使用 Iterator 的 remove()方法 来删除,而不是直接调用 ArrayList 或 HashMap 自身的 remove()方法,否则会导致 Iterator 中的 expectedModCount 没有及时更新,之后获取下一个元素或者删除元素时,expectedModCount 和 modCount 不一致,然后抛出 ConcurrentModificationException 异常。


最后

本文已收录到 1.1K Star 数开源学习指南——《大厂面试指北》,获取《大厂面试指北》离线 PDF 版,请扫描下方二维码关注公众号“大厂面试”



发布于: 2020 年 06 月 03 日阅读数: 713
用户头像

NotFound9

关注

infoQ特邀作者,某大厂高级开发工程师 2018.05.06 加入

Github 1.2K+ Star数的开源项目interviewGuide作者 《大厂面试指北》Github主页:https://github.com/NotFound9/interviewGuide

评论 (1 条评论)

发布
用户头像
解决问题的前提是有个女朋友,感谢分享,InfoQ首页推荐。
2020 年 06 月 04 日 09:26
回复
没有更多了
女朋友跟我吐槽Java中ArrayList遍历时删除元素的各种姿势