ArrayList源代码中的两个显着问题

1. 删除泥水拖拉

测试代码:

package com.demo;
import java.util.ArrayList;
public class TestArrayList {
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<String> arylist = new ArrayList<String>();
        arylist.add("aa");
        arylist.add("bb");
        arylist.add("bb");
        arylist.add("cc");
//        arylist.add("aa");
//        arylist.add("bb");
//        arylist.add("cc");
//        arylist.add("bb");
        String target = "bb";
        for (int i = 0; i < arylist.size(); i++) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
            }
        }
        for(String value:arylist){
            System.out.println(value);
        }
    }
}

此代码的目的是通过遍历数组的每个项目，并在相等的条件下删除它们，删除动态数组arylist中元素与目标相等的元素. 如果数组中的所有元素都是唯一的，则不会有问题，并且相应的元素将被正确删除；如果数组中的元素重复，则可以认为所有重复元素也应删除，这是理所当然的，因为似乎每个项目都是遍历元素. 但是实际结果可能并非您所想. 运行上面的代码以获取输出:

aa
bb
cc

应该删除元素“ bb”，但不能删除.

但是，如果您调整动态数组（例如注释的代码）中重复元素“ bb”的位置: {“ aa”qc全能模块源码，“ bb”，“ cc”，“ bb”}，则结果为两个““ bb”已被删除.

这里的重点是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
        return oldValue;
    }

从上述删除的处理逻辑可以看出，删除操作主要调用System.arraycopy（）方法，该方法在System类中定义为:

    public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

此方法的功能是从srcPos位置启动源数组src，将长度元素的数量复制到目标数组dest，目标数组从destPos位置开始并进行填充.

由此可见，remove方法中的remove方法是从index + 1位置复制elementData数组，然后将numMoved元素复制到index位置. 简单地说，将从索引+1位置开始的元素依次向前移动一个位置，因为无论如何都将删除索引位置上的元素，它将直接覆盖它，最后在elementData结束时无用元素和更新大小.

此方法的问题在于，如果在白名单中位置i和i +1处的元素是重复的，并且碰巧是需要删除的元素，则在删除一轮之后，第二个元素将占据第一个元素，但i ++已增加，第二个元素已跳过，尚未遍历，删除实际上是不完整的. 实际上，只要要删除的元素彼此相邻存在，就会发生这种不完全删除.

remove（对象o）和fastRemove（int索引）基于类似的实现.

正确的措词可以在必要时手动更正计数器i的值，但是这种实现实际上不是很优雅:

        for (int i = 0; i < arylist.size(); i++) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
                i--;
            }
        }

一个更好的实现是通过反向遍历删除:

        for (int i = arylist.size()-1; i >= 0; i--) {
            if (arylist.get(i).equals(target)) {
                arylist.remove(i);
            }
        }

2. 不同的初始化

ArrayList基于对象数组.

在JDK1.8版本中

几个常用的成员变量是:

默认初始化容量: DEFAULT_CAPACITY

两个空的对象数组变量: EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA

实际存储元素的对象数组变量: elementData

大小: 大小

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

    transient Object[] elementData; // non-private to simplify nested class access
    private int size;

源代码的实现者专门使用两个空对象数组来区分参数化的实例化和无参数的实例化，以满足不同条件下的使用.

对应的构造函数如下:

    public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

因此，在通过以下两种方式实例化之后，对象数组实际上是一个空数组，但是它是一个不同的空数组.

        ArrayList<String> list = new ArrayList<String>(0);
        ArrayList<String> list1 = new ArrayList<String>();

通过实例化获得的第一个空数组是EMPTY_ELEMENTDATA，通过实例化获得的第二个空数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA.

但是在第一个add元素之后会有所不同.

    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

add（）方法调用sureCapacityInternal（）方法.

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        ensureExplicitCapacity(minCapacity);
    }
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

The

ensureCapacityInternal（）方法处理两个都为空的对象数组:

如果对象数组是DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则第一个add元素直接从10开始分配的容量，然后直到大小为10，add元素将不调用grow（）方法.

如果对象数组为EMPTY_ELEMENTDATA，则首次添加元素时分配的容量为1，并且随后的几次添加将更频繁地调用grow（），这种增加取决于太小，但仅受限制到最前面经过几次添加操作，在后面的阶段中，第一种方法基本上保持相同的速度.

为什么在这里这么细微的区别对待？我不太了解，但总的来说，我想作者想传达这样的实现意图:

如果程序员使用ArrayList list = new ArrayList （0）;要实例化，那么他应该非常清楚，并且需要一个空的动态数组而不存储任何元素，即使它们需要存储元素也是如此. 它还是一两个非常少的元素，不会被频繁添加，因此不应有10个容量在第一次添加操作中分配，这可能会造成浪费.

如果程序员ArrayList list1 = new ArrayList （）;要实例化qc全能模块源码，那么他需要这个动态数组来存储元素，因此应该为第一个加法器10分配适当的容量.

结束~~~

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/ruanjian/article-185448-1.html