删除list集合中特定元素的正确姿势

Myth丶恋晨 2023-01-08 02:07 292阅读 0赞

# 背景 #

如何删除一个集合对象中的特定元素？小问题，但并不简单。

**常见异常：**

ConcurrentModificationException
    java.util.ConcurrentModificationException
    	at java.util.ArrayList$Itr.checkForComodification(ArrayList.java:911)
    	at java.util.ArrayList$Itr.next(ArrayList.java:861)

# 一.单线程情况下 #

## 1.fori正向删除 ##

fori正向删除指的是index从0开始遍历，判断过滤条件，删除元素

@Test
    void testRemove1() throws Exception {
        List<User> list = new ArrayList<User>();
        for (int i = 1; i <= 5; i++) {
            User user = new User();
            user.setAge(i);
            user.setName("老万"+5);
            list.add(user);
        }
    
        //for循环方法  正向删除
        for (int i = 0; i < list.size(); i++) {
            if("老万5".equals(list.get(i).getName())){
                list.remove(i);
            }
        }
    }

输出结果：  
\[User(name=老万5, age=2), User(name=老万5, age=4)\]

list.remove()源码分析

/**
         * 移除list中特定位置的元素
         * 注意：这个方法中有index的越界检测，但是没有list的修改检测，所以不会出现ConcurrentModificationException* 的异常.
         * 每次调用修改次数modCount++
         * @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++;
            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;
        }

说明：  
fori正向循环删除的时候由于删除完一个元素后后面的元素会向前移动，如果有一样的元素，会漏删相邻一样的元素。for循环正向删除，会遗漏连续重复的元素。  
如果只需要删除第一个满足条件的元素，在if逻辑内添加break关键字就可以了。就不会出现漏删的情况。

## 2.fori反向删除 ##

fori反向删除指的是index从最大到0进行遍历，判断过滤条件，删除元素

@Test
    void testRemove1() throws Exception {
        List<User> list = new ArrayList<User>();
        for (int i = 1; i <= 5; i++) {
            User user = new User();
            user.setAge(i);
            user.setName("老万"+5);
            list.add(user);
        }
    
        //for循环方法，反向删除
        for (int i = list.size()-1; i >=0; i--) {
            if("老万5".equals(list.get(i).getName())){
                list.remove(i);
            }
        }
    }

输出结果：  
\[ \]  
分析：  
反向循环删除不会出现漏删情况，这是由于反向遍历中，如果删除了元素，是由已经判断过的元素来进行补位，  
对哪些没有进行判断的元素没有影响。

总结：  
fori反向遍历删除，没有问题

## 3.迭代器Iterable删除 ##

错误写法：  
调用list.remove(user)导致it对象改变，抛出异常ConcurrentModificationException

Iterator it = list.iterator();
    while (it.hasNext()){
        User user = (User)it.next();
        if("老万5".equals(user.getName())){
            list.remove(user);
        }
    }

说明：  
既然采用了迭代器，就不要使用list.remove()来进行删除，而应该采用迭代器的it.remove()方法.

正确写法：

Iterator it = list.iterator();
    while (it.hasNext()){
        User user = (User)it.next();
        if("老万5".equals(user.getName())){
            it.remove();
        }
    }

源码分析：

//list对象的修改次数
    protected transient int modCount = 0;
    
     //检测list是否修改的逻辑：比较修改次数modCount和预期修改次数expectedModCount是否一致
     final void checkForComodification() {
                if (modCount != expectedModCount)
                    throw new ConcurrentModificationException();
            }
    
    //迭代器的next()方法会检测list是否修改
    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];
            }
        
    //核心，迭代器的remove方法，会检测list是否修改，删除元素后，会将expectedModCount=modCount。所以调用迭代器remove方法，不会出现异常ConcurrentModificationException
    public void remove() {
                        if (lastRet < 0)
                            throw new IllegalStateException();
                        checkForComodification();
    
                        try {
                            SubList.this.remove(lastRet);
                            cursor = lastRet;
                            lastRet = -1;
                            expectedModCount = ArrayList.this.modCount;
                        } catch (IndexOutOfBoundsException ex) {
                            throw new ConcurrentModificationException();
                        }
                    }

## 4.增强for循环删除 ##

增强for循环的底层其实也是采用迭代器Iterable循环，改接口定义了iterator迭代器的产生方法，并且forEach就是通过Iterable接口在序列中进行移动，也就是说：在编译的时候，编译器会自动堆for这个关键字的使用转化为目标的迭代器的使用，那么就是3中说的一样了。

for(User user: list){
        if("老万5".equals(user.getName())){
            list.remove(user);
        }
    }

结果：  
抛出异常ConcurrentModificationException

分析：  
本质是在迭代器的循环中，采用了list.remove(index)的删除方法，出现了modCount++的操作。  
导致在next()的checkForComodification()逻辑中出现异常ConcurrentModificationException  
由于删除后ModCount会增加 但expectedModCount不会增加这样在下边方法判断中就会由于这两个参数不相等而抛出异常。

Iterator it = list.iterator();
    while (it.hasNext()){
        User user = (User)it.next();
        if("老万5".equals(user.getName())){
            list.remove(user);
        }
    }

缺点：  
对于数组，不能方便的访问下标值；  
对于集合，与使用Interator相比，不能方便的删除集合中的内容（在内部也是调用Interator）.只能从头到尾的遍历数组或集合，而不能只遍历部分  
除了简单遍历并读取其中的内容外，不建议使用增强的for循环。

**PS：**  
在List 进行remove操作时，要注意：

for循环在删除元素时，会改变你 list.size() 的大小，因此会导致错误，一般解决办法是将需要留下的list元素，放到一个新的 list中，作为遍历删除的结果。  
而通过迭代器的方式，进行 remove() 操作不仅会删除元素，还会对 list 集合的下标进行重新维护，因此，在删除操作时建议使用这种方式。

# 二.多线程情况下 #

**场景举例**：

在使用websocket框架时，想采用一个list集合来保存所有的会话session对象。  
这里的list对象就是一个全局对象，会被多个线程操作新增，删除。

**典型错误：**

直接采用ArrayList对象保存session。

**建议**：涉及到多线程的操作，最好直接采用线程安全的list对象

**方案选择：**

1.  CopyOnWriteArrayList
2.  Collections.synchronizedList

## 1.CopyOnWriteArrayList ##

基本思想  
Copy-On-Write，写入时复制，这个技术，准确的说应该是一种思想，在很多系统设计上都会用到，今天我们来谈一谈Java语言中，JDK运用这种写入时复制的思想的数据结构/容器，CopyOnWriteArrayList只能保证数据的最终一致性。

CopyOnWriteArrayList，是一个写入时复制的容器，它是如何工作的呢？简单来说，就是平时查询的时候，都不需要加锁，随便访问，只有在写入/删除的时候，才会从原来的数据复制一个副本出来，然后修改这个副本，最后把原数据替换成当前的副本。修改操作的同时，读操作不会被阻塞，而是继续读取旧的数据。这点要跟读写锁区分一下。

CopyOnWriteArrayList的add方法源码：

public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        lock.lock();
        try {
            Object[] elements = getArray();
            int len = elements.length;
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            newElements[len] = e;
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }
    
    //修改操作添加了ReentrantLock锁，保证多线程下的线程安全
    public E remove(int index) {
                final ReentrantLock lock = l.lock;
                lock.lock();
                try {
                    rangeCheck(index);
                    checkForComodification();
                    E result = l.remove(index+offset);
                    expectedArray = l.getArray();
                    size--;
                    return result;
                } finally {
                    lock.unlock();
                }
            }

实战：

CopyOnWriteArrayList<User>  list = new CopyOnWriteArrayList<User>();
            for (int i = 1; i <= 5; i++) {
                User user = new User();
                user.setAge(i);
                user.setName("老万"+5);
                list.add(user);
            }
    
         Iterator it = list.iterator();
            while (it.hasNext()){
                User user = (User)it.next();
                if("老万5".equals(user.getName())){
                   // it.remove();   //不支持remove()方法
                    list.remove(user);
                }
            }

首先可以看到CopyOnWriteArrayList中用到了ReentrantLock进行加锁，  
添加元素时，保证同时只有1个线程进行变更，在变更的时候，先拷贝出来一个副本，先操作这个副本，操作完成后，再把现有的数据替换成这个副本。

**优点：**  
对于一些读多写少的数据，这种做法的确很不错，例如配置、黑名单、物流地址等变化非常少的数据，这是一种无锁的实现。可以帮我们实现程序更高的并发。

**缺点：**  
这种实现只是保证数据的最终一致性，在添加到拷贝数据而还没进行替换的时候，读到的仍然是旧数据。如果对象比较大，频繁地进行替换会消耗内存，从而引发Java的GC问题，这个时候，我们应该考虑其他的容器，例如ConcurrentHashMap。

## 2.Collections.synchronizedList ##

简单来说，Collections.synchronizedList方法会对传入的list对象的get，add，remove等方法都添加synchronized锁。  
但是需要注意，其中的listIterator()方法时没有加锁的，也就是不是线程安全的。

看下Collections.synchronizedList的源码：

public static <T> List<T> synchronizedList(List<T> list) {
        return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<>(list) :
                new SynchronizedList<>(list));
    }

这个方法回根据你传入的List是否实现RandomAccess这个接口来返回的SynchronizedRandomAccessList还是SynchronizedList.

再看一下SynchronizedList的源码：

static class SynchronizedList<E>
        extends SynchronizedCollection<E>
        implements List<E> {
        private static final long serialVersionUID = -7754090372962971524L;
    
        final List<E> list;
    
        SynchronizedList(List<E> list) {
            super(list);
            this.list = list;
        }
        SynchronizedList(List<E> list, Object mutex) {
            super(list, mutex);
            this.list = list;
        }
    
        public boolean equals(Object o) {
            if (this == o)
                return true;
            synchronized (mutex) {return list.equals(o);}
        }
        public int hashCode() {
            synchronized (mutex) {return list.hashCode();}
        }
    
        public E get(int index) {
            synchronized (mutex) {return list.get(index);}
        }
        public E set(int index, E element) {
            synchronized (mutex) {return list.set(index, element);}
        }
        public void add(int index, E element) {
            synchronized (mutex) {list.add(index, element);}
        }
        public E remove(int index) {
            synchronized (mutex) {return list.remove(index);}
        }
    
        public int indexOf(Object o) {
            synchronized (mutex) {return list.indexOf(o);}
        }
        public int lastIndexOf(Object o) {
            synchronized (mutex) {return list.lastIndexOf(o);}
        }
    
        public boolean addAll(int index, Collection<? extends E> c) {
            synchronized (mutex) {return list.addAll(index, c);}
        }
    
        public ListIterator<E> listIterator() {
            return list.listIterator(); // Must be manually synched by user
        }
    
        public ListIterator<E> listIterator(int index) {
            return list.listIterator(index); // Must be manually synched by user
        }
    
        public List<E> subList(int fromIndex, int toIndex) {
            synchronized (mutex) {
                return new SynchronizedList<>(list.subList(fromIndex, toIndex),
                                            mutex);
            }
        }
    
        @Override
        public void replaceAll(UnaryOperator<E> operator) {
            synchronized (mutex) {list.replaceAll(operator);}
        }
        @Override
        public void sort(Comparator<? super E> c) {
            synchronized (mutex) {list.sort(c);}
        }
        ... ...
    }

可以看到SynchronizedList类中对add，remove， get等方法都加了synchronized关键字修饰，在保证List相关机制不变的情况下，保证的线程安全

但是可以看到 listIterator（）获取迭代器的相关方法并没有使用synchronized关键字，  
因此在进行迭代遍历的时候，需要加锁.

List<User> list = Collections.synchronizedList(new ArrayList<User>());
        for (int i = 1; i <= 5; i++) {
            User user = new User();
            user.setAge(i);
            user.setName("老万"+5);
            list.add(user);
        }
    
     synchronized (list) {//迭代器遍历读取时添加synchronized关键字，这样就实现了读写时都加锁。
            Iterator it = list.iterator();
            while (it.hasNext()){
                User user = (User)it.next();
                if("老万5".equals(user.getName())){
                    it.remove();
                }
            }
     }

CopyOnWriteArrayList和Collections.synchronizedList对比

CopyOnWriteArrayList和Collections.synchronizedList是实现线程安全的列表的两种方式。

1.性能方面  
其中CopyOnWriteArrayList的写操作性能较差，而多线程的读操作性能较好。而Collections.synchronizedList的写操作性能比CopyOnWriteArrayList在多线程操作的情况下要好很多，而读操作因为是采用了synchronized关键字的方式，其读操作性能并不如CopyOnWriteArrayList。因此在不同的应用场景下，应该选择不同的多线程安全实现类。

2.锁  
CopyOnWriteArrayList采用的是ReentrantLock锁。Collections.synchronizedList采用的是synchronized来加锁。  
Collections.synchronizedList读写时都加锁，能完全保证一致性。  
而CopyOnWriteArrayList只能保证最终一致性。

3.迭代器遍历  
CopyOnWriteArrayList的iterator方法，由于访问的时一个快照，不需要加锁，并且不支持it.remove()方法。  
而Collections.synchronizedList的迭代器需要加锁。

# 总结 #

一.单线程下遍历根据条件删除特定元素，推荐采用迭代器遍历删除。

二.多线程下，最好采用线程安全的list对象CopyOnWriteArrayList和Collections.synchronizedList，  
但需要注意两者在实现原理和使用上的细节区别。

三.除了在使用CopyOnWriteArrayList的情况下需要采用list.remove(index)，其他情况下都推荐采用迭代器的it.remove()来删除元素，  
避免list.size和元素位移引起的一些异常情况。

--------------------

> 参考：https://www.jianshu.com/p/cbc458bc9786