Java 遍历集合时删除元素快速失败和安全失败

缺乏、安全感 2023-07-14 10:32 19阅读 0赞

### 文章目录 ###

*   *  遍历集合时删除元素
     *   *   *  遍历集合时删除元素的五种操作
             *  方式4分析
             *  方式2和方式3分析
             *  方式5分析
             *  方式1分析
             *  方式5再分析
     *  快速失败和安全失败
     *   *   *  快速失败（fail-fast）
             *  安全失败（fail-safe）
     *  附录

## 遍历集合时删除元素 ##

#### 遍历集合时删除元素的五种操作 ####

import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    public class Test { 
        public static void main(String[] args) { 
            List<String> list = new ArrayList<>();
            list.add("1");
            list.add("2");
            list.add("3");
            list.add("4");
            list.add("5");
            
            // 错误方式方式1 使用for each，但是不会触发ConcurrentModificationException
            System.out.println("--------1----------");
            List<String> list1 = new ArrayList<>(list);
            for (String s : list1) { 
                if("4".equals(s)) { 
                    list1.remove(s);
                }
            }
            System.out.println(list1);
            
            // 错误方式方式2 使用for each，会触发ConcurrentModificationException
            System.out.println("--------2----------");
            List<String> list2 = new ArrayList<>(list);
            try{ 
                for (String s : list2) { 
                    if("2".equals(s)) { 
                        list2.remove(s);
                    }
                }
            }catch (Exception e) { 
                e.printStackTrace();
            }
            System.out.println(list2);
    
            // 错误方式3 使用iterator触发ConcurrentModificationException
            System.out.println("--------3----------");
            List<String> list3 = new ArrayList<>(list);
            try{ 
                Iterator<String> iterator3 = list3.iterator();
                while(iterator3.hasNext()) { 
                    String str = iterator3.next();
                    if("2".equals(str)) { 
                        list3.remove(str);
                    }
                }
            }catch (Exception e) { 
                e.printStackTrace();
            }
            System.out.println(list3);
    
            // 正确方式4 使用for循环
            System.out.println("--------4----------");
            List<String> list4 = new ArrayList<>(list);
            for(int i = 0; i < list4.size(); i++) { 
                if("2".equals(list4.get(i))) { 
                    list4.remove(i);
                    i--;
                }
            }
            System.out.println(list4);
    
            // 正确方式5 使用iterator
            System.out.println("--------5----------");
            List<String> list5 = new ArrayList<>(list);
            Iterator<String> iterator5 = list5.iterator();
            while(iterator5.hasNext()) { 
                String str = iterator5.next();
                if("2".equals(str)) { 
                    iterator5.remove();
                }
            }
            System.out.println(list5);
        }
    }

**运行结果：**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]  
**说明：**

*  前三种方式是错误的，后两种方式是正确的
 *  运行结果中的两个异常分别是方式2和方式3抛出的
 *  其中，for each的方式底层采用的也是迭代器iterator的方式，因此方式2和方式3在底层实现原理类似
 *  方式4采用的是for循环，通过下标访问ArrayList数组，因此不同于其他迭代器方式

ArrayList的Iterator是在父类AbstractList中实现的：

package java.util;
    
    public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 
    
        ...
    
        // AbstractList中唯一的属性
        // 用来记录List修改的次数：每修改一次(添加/删除等操作)，将modCount+1
        protected transient int modCount = 0;
    
        // 返回List对应迭代器。实际上，是返回Itr对象。
        public Iterator<E> iterator() { 
            return new Itr();
        }
    
        // Itr是Iterator(迭代器)的实现类
        private class Itr implements Iterator<E> { 
            int cursor = 0;
    
            int lastRet = -1;
    
            // 修改数的记录值
            // 每次新建Itr()对象时，都会保存新建该对象时对应的modCount；
            // 以后每次遍历List中的元素的时候，都会比较expectedModCount和modCount是否相等；
            // 若不相等，则抛出ConcurrentModificationException异常
            int expectedModCount = modCount;
    
            public boolean hasNext() { 
                return cursor != size();
            }
    
            public E next() { 
                // 获取下一个元素之前，都会判断“新建Itr对象时保存的modCount”和“当前的modCount”是否相等；
                // 若不相等，则抛出ConcurrentModificationException异常
                checkForComodification();
                try { 
                    E next = get(cursor);
                    lastRet = cursor++;
                    return next;
                } catch (IndexOutOfBoundsException e) { 
                    checkForComodification();
                    throw new NoSuchElementException();
                }
            }
    
            public void remove() { 
                if (lastRet == -1)
                    throw new IllegalStateException();
                checkForComodification();
    
                try { 
                    AbstractList.this.remove(lastRet);
                    if (lastRet < cursor)
                        cursor--;
                    lastRet = -1;
                    expectedModCount = modCount;
                } catch (IndexOutOfBoundsException e) { 
                    throw new ConcurrentModificationException();
                }
            }
    
            final void checkForComodification() { 
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
        }
    
        ...
    }

#### 方式4分析 ####

方式4是正确的。ArrayList底层采用数组存储元素，通过下标的方式访问，删除元素后，`i--`操作保证了数组不会越界访问，也不会漏删除元素。比如，数组元素为`[1,2,3,3,4]`，当删除第一个3的时候，此时`i的值为2`，数组变为`[1,2,3,4]`，`i--`操作后，`i的值为1`。下一轮循环，`i的值为2`，再次将第二个3删除。整个过程`i`的值随数组元素的删除而动态变化，因此这种方式是正确的。

#### 方式2和方式3分析 ####

方式2和方式3是错误的。底层都是使用迭代器实现，在遍历元素的时候删除元素触发了ConcurrentModificationException异常。  
迭代器next()的源码：

public E next() { 
        checkForComodification();//ConcurrentModificationException异常在这里抛出
        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];
    }
    
    final void checkForComodification() { 
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
    }

**说明：**

*  modCount是ArrayList的一个变量，该值是在集合的结构发生改变时（如增加、删除等）进行一个自增操作。
 *  expectedModCount是迭代器的一个变量，该值在调用集合的iterator()方法实例化迭代器的时候，会将modCount的值赋值给迭代器的变量 expectedModCount。也就是说，在该迭代器的迭代操作期间，expectedModCount的值在初始化之后便不会进行改变，而modCount的值却可能改变（比如进行了删除操作），这也是每次调用next()方法的时候，为什么要比较下这两个值是否一致。

所以，集合和迭代器中分别有两个变量modCount和expectedModCount，expectedModCount初始值等于modCount，当集合元素发生删除操作时，modCount的值会发生改变，当迭代器的next()方法中，判断到modCount和expectedModCount的值不相等时，就会触发ConcurrentModificationException异常。

#### 方式5分析 ####

方式5是正确的。它使用了迭代器的remove()方法，该方法源码：

public void remove() { 
    	if (lastRet < 0)
    	     throw new IllegalStateException();
    	 // 虽然这里也调用了checkForComodification方法，但是由于这里使用的是
    	 // 迭代器中的remove方法而非集合中的remove方法，对集合元素的移除操作还未发生
    	 // 就调用了checkForComodification方法，因此此时expectedModCount和modCount还是相等的，
    	 // 除非有其他线程修改了集合导致modCount值发生改变
    	 checkForComodification();
    	
    	 try { 
    	     // 在这里才开始调用集合的remove方法
    	     ArrayList.this.remove(lastRet);
    	     cursor = lastRet;
    	     lastRet = -1;
    	     // 重新赋值，使用expectedModCount与modCount的值保持一致
    	     expectedModCount = modCount;
    	 } catch (IndexOutOfBoundsException ex) { 
    	     throw new ConcurrentModificationException();
    	 }
    	}

所以，调用迭代器的remove方法时，还未移除集合元素的时候就判断了modCount和expectedModCount值是否相等，相等时，才调用集合的remove方法移除集合元素，并将修改后的modCount值重写赋值给expectedModCount变量，保证下一次调用next的时候，modCount和expectedModCount值是相等的。

#### 方式1分析 ####

方式1是错误的，但是没有触发ConcurrentModificationException异常，因为方式1移除的是倒数第二个元素。  
方式1的写法换成下面等价的写法来解释：

Iterator<String> iterator1 = list1.iterator();
    while(iterator1.hasNext()) { 
        String str = iterator1.next();
        if("4".equals(str)) { 
            list1.remove(str);
        }
    }

hasNext()的源码：

public boolean hasNext() { 
        return cursor != size;
    }

*  cursor是一个游标，初始值为0，每调用一次next()方法，它的值加1

采用调试的方式，当遍历到第四个元素的时候，cursor的值为4：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]  
当把第四个元素删除的时候，集合的size值变为4：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]  
因此当下一次调用hasNext()的时候，返回的是false，即还未遍历第五个元素，还没有调用next()方法，还没有判断modCount和expectedModCount值是否相等（肯定已经不相等了）时，就退出了循环，因此就不会抛出ConcurrentModificationException异常。可以将集合设置为`[1,2,3,4,4]`来执行下这个操作，可以发现最后一个4并未删除，即最后一个4还未遍历到，while循环就退出了。

#### 方式5再分析 ####

上面提到hasNext()方法是通过判断`cursor != size`来返回true或false，那么，删除了集合中的元素，集合的size肯定会发生变化，方式5是如何保证curosr游标指向正确的位置了。把方式5代码稍作修改后进行调试：

List<String> list5 = new ArrayList<>(list);
            Iterator<String> iterator5 = list5.iterator();
            while(iterator5.hasNext()) { 
                String str = iterator5.next();
                if("2".equals(str) || "4".equals(str)) { 
                    iterator5.remove();
                }
            }

当遍历到第二个元素的时候，注意观察红色框内的四个变量的值：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 3]  
删除第二个元素时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 4]  
当遍历到第四个元素时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 5]  
当删除第四个元素时：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 6]  
总结：

*  modCount的值的确是重新赋值给了expectedModCount变量
 *  lastRet变量初始值为-1，当执行next()后，该变量自增1
 *  cursor变量初始值为0，当执行next()后，该变量自增1
 *  size变量会随着集合元素的移除进行自减1操作
 *  当删除元素的时候，会将lastRet变量的值赋值给cursor变量，使cursor游标指向正确的位置，然后lastRet值重新赋值为-1。

通过这种方式，就保证了cursor游标变量的正确性。

## 快速失败和安全失败 ##

集合中有个modCount变量，当对集合进行删除/增加等操作的时候，这个变量会进行自增操作。迭代器中有个expectedModCount变量，当创建一个集合的迭代器的时候，会将modCount的值赋值给expectedModCount变量。当遍历集合的时候，如果modCount发生改变，当调用迭代器的next()方法时，迭代器检测到modCount和expectedModCount值不相等，会抛出ConcurrentModificationException异常。

> 注意：异常的抛出条件是检测到 modCount！=expectedmodCount 这个条件。如果集合发生变化时修改modCount值刚好又设置为了expectedmodCount值，则异常不会抛出。因此，不能依赖于这个异常是否抛出而进行并发操作的编程，这个异常只建议用于检测并发修改的bug。

#### 快速失败（fail-fast） ####

在用迭代器遍历集合的时候，如果遍历过程中调用了集合的remove()、add()等方法修改集合时，就会抛出ConcurrentModificationException异常。`java.util`包下的所有集合都是快速失败的，快速失败的迭代器会抛出ConcurrentModificationException异常。

快速失败示例：

import java.util.*;
    import java.util.concurrent.*;
    
    public class FastFailTest { 
    
        private static List<String> list = new ArrayList<String>();
        
        public static void main(String[] args) { 
            // 同时启动两个线程对list进行操作
            new ThreadOne().start();
            new ThreadTwo().start();
        }
    
        private static void printAll() { 
            System.out.println("");
    
            String value = null;
            Iterator iter = list.iterator();
            while(iter.hasNext()) { 
                value = (String)iter.next();
                System.out.print(value+", ");
            }
        }
        
        private static class ThreadOne extends Thread { 
            public void run() { 
                int i = 0;
                while (i<6) { 
                    list.add(String.valueOf(i));
                    printAll();
                    i++;
                }
            }
        }
    
        private static class ThreadTwo extends Thread { 
            public void run() { 
                int i = 10;
                while (i<16) { 
                    list.add(String.valueOf(i));
                    printAll();
                    i++;
                }
            }
        }
    }

其中一个运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 7]

#### 安全失败（fail-safe） ####

`java.util.concurrent`包下面的所有的类都是安全失败的，将上列中ArrayList改为`java.util.concurrent`包下的CopyOnWriteArrayList则不会抛出ConcurrentModificationException异常。  
安全失败机制的集合，比如CopyOnWriteArrayList，在遍历的时候不是直接在原集合上遍历，而是先拷贝一份原集合，历操作在这个拷贝的快照中进行，所以当遍历的过程中对原集合进行修改并不会被迭代器检测到。  
CopyOnWriteArrayList部分源码：

package java.util.concurrent;
    import java.util.*;
    import java.util.concurrent.locks.*;
    import sun.misc.Unsafe;
    
    public class CopyOnWriteArrayList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable { 
    
        ...
    
        // 返回集合对应的迭代器
        public Iterator<E> iterator() { 
            return new COWIterator<E>(getArray(), 0);
        }
    
        ...
       
        private static class COWIterator<E> implements ListIterator<E> { 
            private final Object[] snapshot;
    
            private int cursor;
    
            private COWIterator(Object[] elements, int initialCursor) { 
                cursor = initialCursor;
                // 新建COWIterator时，将集合中的元素保存到一个新的拷贝数组中。
                // 这样，当原始集合的数据改变，拷贝数据中的值也不会变化。
                snapshot = elements;
            }
    
            public boolean hasNext() { 
                return cursor < snapshot.length;
            }
    
            public boolean hasPrevious() { 
                return cursor > 0;
            }
    
            public E next() { 
                if (! hasNext())
                    throw new NoSuchElementException();
                return (E) snapshot[cursor++];
            }
    
            public E previous() { 
                if (! hasPrevious())
                    throw new NoSuchElementException();
                return (E) snapshot[--cursor];
            }
    
            public int nextIndex() { 
                return cursor;
            }
    
            public int previousIndex() { 
                return cursor-1;
            }
    
            public void remove() { 
                throw new UnsupportedOperationException();
            }
    
            public void set(E e) { 
                throw new UnsupportedOperationException();
            }
    
            public void add(E e) { 
                throw new UnsupportedOperationException();
            }
        }
      
        ...
    
    }

*  CopyOnWriteArrayList是线程安全的。
 *  它的存储元素的数组使用了volatile修饰，在add()方法中，使用了ReentrantLock锁来保证线程安全。
 *  在有写操作的时候会拷贝一份数据，然后写操作发生在这个副本中，写完之后，再用副本替换掉原来的数据，这样保证了读写操作不受影响。
 *  在使用它的迭代器遍历集合时，会先获取数组的一份拷贝，遍历操作在这个拷贝的快照中进行，所以当遍历的过程中对原集合进行修改并不会被迭代器检测到，所有读取数据不需要加锁就能保证安全性。

## 附录 ##

参考：  
https://blog.csdn.net/x763795151/article/details/84028314  
https://www.cnblogs.com/shamo89/p/6685216.html

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70]: /images/20230529/0dc8a4cf910744cb8cdbb015ecfe2b03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 1]: /images/20230529/c65d384ffa364820a39d24ea368068dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 2]: /images/20230529/5394127a22e74570b75cffee463b5da2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 3]: /images/20230529/3e5da776113e461b9b24e92e184feeff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 4]: /images/20230529/64c6ab185d67400da618ee4216c3c2c5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 5]: /images/20230529/c5fc7bfc4c984c3293b84bc5c0cbaa6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 6]: /images/20230529/003c0ab7eaeb4dcbb58abe407e3d21aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0lUXzEw_size_16_color_FFFFFF_t_70 7]: /images/20230529/fdac6e812f7344ec8f96b967220c74ff.png