Java ArrayList批量删除算法分析

我们知道 ArrayList 中有一个批量删除的集合的方法：removeAll(Collection<?> c)，该方法中涉及了高效保存两个集合公有元素的算法，这里特地拿出来分析一下，学习源码中的优秀设计思想。
下面先给出批量删除代码的片段：

   /**这里先假设elementData(ArryList内部维护的一个Object[]数组)和
     集合c的交集是A：
     当 complement == true 时，elementData最终只会存储A
     当 complement == false 时，elementData最终删除A。

     在对elementData的元素进行筛选的时候，这里使用了r、w两个游标，
     从而避免从新开辟一个新的数组进行存储。
   **/
 private boolean batchRemove(Collection<?> c, boolean complement) {
        final Object[] elementData = this.elementData;
        int r = 0, w = 0;
        boolean modified = false;
        try {
            for (; r < size; r++)
                //当调用removeAll(Collection<?> c)时，complement == false,
                //此时elementData数组中存储的是去掉A的部分
                if (c.contains(elementData[r]) == complement)
                    elementData[w++] = elementData[r];
        } finally {
            // Preserve behavioral compatibility with AbstractCollection,
            // even if c.contains() throws.
             //出现异常会导致 r !=size , 则将出现异常处后面的数据全部
             //复制覆盖到数组里。
            if (r != size) {
                System.arraycopy(elementData, r,
                                 elementData, w,
                                 size - r);
                w += size - r;
            }
            if (w != size) {
                // clear to let GC do its work
                for (int i = w; i < size; i++)
                    elementData[i] = null;
                modCount += size - w;
                size = w;
                modified = true;
            }
        }
        return modified;
    }

我们先分析正常情况，即 r == size:
注意到只有 elementData和都为空或者c的元素都不在elementData中的情况下，才会出现 w == size,因为都为空或者没有相同元素，所以不存在删除的情况。
所以只用分析 w != size的情况
当 w != size 时，一旦出现elementData中有，但是c中没有的元素的时候，就会存放在elementData[w]中，也就是说0~（w-1）位置一定是
elementData包含但是c中没有的元素，然后将w~（size-1）位置的元素置空，交给GC去回收，这样一来，elementData中就只剩下除去和c中相同元素的数组了，它的size为w。
接下来再说说异常情况：即 r != size：
因为这个时候已经出现了异常，所以把从r位置开始的（size-r）个元素复制到从w开始的到（w+size-r-1）位置，此时 w = size - r，这样就可以保证在出现异常之前已经遍历的c和elementData中的相同元素已经被覆盖了，同时也保证了从r位置开始的（size-r）个元素向左移动了（r-w）位，保证数组元素的完整性。然后在将w~（size-1）位置的元素置空，交给GC去回收。这样即使发生了异常，也不会导致删除错误。
至此，ArrayList的批量删除算法就分析完了，可能看起来有点绕，但是静下心来，用笔在纸上画一画这个过程，你就会豁然开朗。