ArrayList 源码分析扩容过程及性能优化

ArrayList 默认初始化过程，初始容量为10的空列表

//首先我们看源码，无参构造函数     /**     * Constructs an empty list with an initial capacity of ten.     */    public ArrayList() {        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;    }            //DEFAULTCAPACITY_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 = {};          //可以再看一下add方法中，调用的ensureCapacityInternal方法中判断elementData == EMPTY_ELEMENTDATA 是否为空，如果为空，minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);,minCapacity设置为其中的大值，在默认是空的时候，初次调用add方法传入的参数是1，也就是这里的minCapacity就是1，现在minCapcity变成了DEFAULT_CAPACITY 也就是10     public boolean add(E e) {        ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }     private void ensureCapacityInternal(int minCapacity) {        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);        }        ensureExplicitCapacity(minCapacity);    }          //默认值     /**     * Default initial capacity.     */    private static final int DEFAULT_CAPACITY = 10;

ArrayList的扩容规律

通过下面的源码发现，如果空间不够，会通过Arrays.copyOf()创建一个新的内存空间，新空间的大小最小为原空间的1.5倍，这里是通过位移运算，效果相当于 oldCapacity/2 = oldCapacity >> 1

/**     * Increases the capacity to ensure that it can hold at least the     * number of elements specified by the minimum capacity argument.     *     * @param minCapacity the desired minimum capacity     */    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);    }

通过以上源码可以看到，ArrayList是非常浪费内存的，当集合太大的时候，很容易出现OOM 那么在知道List长度范围的情况下，在实例化ArrayList的时候带上长度 new ArrayList(256),来 降低内存碎片和内存拷贝次数。 当文本内容或者Excel大量导入场景时，可以考虑先做分段处理，而不是一次导入到内存中

Vector

vector 初始化大小也是10，与ArrayList 不同的是动态策略不同，和加有synchronized关键字确定方法临界区，使线程同步

public Vector() {        this(10);    } private void grow(int minCapacity) {        // overflow-conscious code        int oldCapacity = elementData.length;        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?                                         capacityIncrement : oldCapacity);        if (newCapacity - minCapacity < 0)            newCapacity = minCapacity;        if (newCapacity - MAX_ARRAY_SIZE > 0)            newCapacity = hugeCapacity(minCapacity);        elementData = Arrays.copyOf(elementData, newCapacity);    }public synchronized void setSize(int newSize) {        modCount++;        if (newSize > elementCount) {            ensureCapacityHelper(newSize);        } else {            for (int i = newSize ; i < elementCount ; i++) {                elementData[i] = null;            }        }        elementCount = newSize;    }

LinkedList

LinkedList 的数据结构为双向链表，双向链表与数组的优点为，遍历 删除 元素 都优与动态数组的ArrayList