ArrayList分析3 : 删除元素

转载请注明出处：https://www.cnblogs.com/funnyzpc/p/16421743.html

对于集合类删除元素是常有的需求，非常常见；如果是惯常的删除方式就没有写本篇博客的必要了，本篇博客不光分析删除可能导致的问题，也会从源码层面分析为何需要借用迭代器删除，同时也会给出不同业务形态下的删除方式等，有兴趣的往下看看囖?

一.循环与非循环内删除

这是两种不同的业务形态，如果是确定待删除元素的索引位置或元素值且只删除一个元素的情况下，一般是直接调用ArrayList下的remove删除方法，但这不是本篇重点

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        System.out.println(arr);
        arr.remove("c");// remove c
        arr.remove(3);// remove d
        System.out.println(arr);
    }

还一种情况是删除多个元素，一般不能确定待删除元素的索引位置，这样就需要在循环内删除了;

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(int i=0;i<arr.size();i++){
            if("d".equals(arr.get(i))){
                arr.remove("d");
            }
        }
        System.out.println(arr);
    }

二.删除的错误用法

(错误用法一)

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(Object item:arr){
            if("d".equals(item)){
                arr.remove(item);
            }
        }
    }

(错误用法二)

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        arr.forEach(item->{
            if("d".equals(item)){
                arr.remove("d");
            }
        });
    }

虽然均为删除，但是简化版的for循环还有函数式循环下就不能删除呢？往下看...

三.普通删除做了什么

这是ArrayList的remove源码：

    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  明确让GC做它的工作（也就是缩一个位置并置为null，切断引用了自然会被gc掉）
        return oldValue;
    }

这是迭代器remove源码：

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

对于ArrayList的remove，其实重要的一点是 --size ,而对于迭代器的remove不仅仅是调用ArrayList的删除还需要更新游标(cursor)以及当前元素索引位置(lastRet), 这时灵感就来了，是不是简化版for循环以及函数式forEach循环下的size变成了常数了呢？对，其实也就是这样，如果我将循环删除逻辑改成这样就好理解了：

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        for(int i=0;i<6;i++){
            if( i==(arr.size()-1) ){
                break;
            }
            if(arr.get(i).equals("d")){
                arr.remove(i);
            }
        }
        System.out.println(arr);
    }

所以每次进入循环后均要检视下数组的size是否发生了变化，否则越界，所以不管是哪种方式的删除均要获取到最新的 size这样才能保证安全删除

四.不同需求下删除逻辑

如果需要保证完全的安全删除，建议您使用迭代器 iterator 或 listIterator：

public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        Iterator itr = arr.iterator();
        while(itr.hasNext()){
            Object item = itr.next();
            if("d".equals(item)){
                itr.remove();
            }
        }
        System.out.println(arr);
    }

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        ListIterator itr = arr.listIterator();
        while(itr.hasNext()){
            Object item = itr.next();
            if("d".equals(item)){
                itr.remove();
            }
        }
        System.out.println(arr);
    }

如果需要在迭代器内获取当前迭代元素的索引或者

public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        ListIterator lst_itr = arr.listIterator();
        while(lst_itr.hasNext()){
            int idx = lst_itr.nextIndex();
            Object item = lst_itr.next();
            System.out.println(idx+"->"+item);
            if("d".equals(item)){
                lst_itr.remove();
            }
        }
        System.out.println(arr);
    }

当然啰，如果既想用迭代器又想获取当前循环元素的索引位置，又想获取原数组(未删除前的)的索引位置，可以尝试这样：

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        int i = 0;
        for(ListIterator lst_itr = arr.listIterator();lst_itr.hasNext();i++){
            int idx = lst_itr.nextIndex();
            Object item = lst_itr.next();
            System.out.println(i+" -> "+idx+":"+item);
            if("d".equals(item)){
                lst_itr.remove();
            }
        }
        System.out.println(arr);
    }

五.简化的删除方式

    public static void main(String[] args) {
        ArrayList arr  = new ArrayList();
        arr.add("a");
        arr.add("b");
        arr.add("c");
        arr.add("d");
        arr.add("e");
        arr.add("d");
        System.out.println(arr);
        arr.removeIf(item->"d".equals(item));
        System.out.println(arr);
    }

简化删除方式内部源码：

    @Override
    public boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        // figure out which elements are to be removed
        // any exception thrown from the filter predicate at this stage
        // will leave the collection unmodified
        int removeCount = 0;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        final int size = this.size;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }

        // shift surviving elements left over the spaces left by removed elements
        // 将剩余的元素移到被移除的元素留下的空间上 ，也即数组瘦身
        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;  // Let gc do its work
            }
            this.size = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

哈哈，是不是超复杂，内部不仅仅要维护removeCount还需要维护版本，同时元素的位置也采用特殊的方式移动，这样一来效率就似乎就不是那么高了，所以看似简单的用法内部一点儿也不简单。。。