ArrayList应该怎么用

ArrayList应该怎么用

ArrayList是JDK提供的一个集合工具类，也是最常用的工具类之一。

ArrayList特点

1. 底层数据结构为数组，查询快增删慢

2. 元素可重复，值可为null

3. 线程不安全

经典面试题

**问题一：**既然ArrayList底层的数据结构是数据，那么它的初始长度是多少，当数据增加时数组长度又是怎么增长的呢？

从JDK源码我们看到ArrayList有两个构造函数：

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

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

第一个无参构造函数直接将一个静态空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋值给了内部数组elementData，所以它初始化对象的内部数组长度是0。

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

第二个构造函数会初始化一个指定大小的内部数组。

那么这个数组后面怎么增长的呢？我们看以下源码，ArrayList.add方法会调用ensureCapacityInternal，minCapacity的值为size+1（size的初始值为0）。

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return 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);
}

当调用无参构造函数后第一次调用add方法时，minCapacity=1，calculateCapacity返回DEFAULT_CAPACITY（默认值10），传入ensureExplicitCapacity的参数minCapacity值为10，最终elementData变成了长度为10的数组，后续数组长度增长参考以上22行代码，最终的长度增长趋势为：0->10->15->22->33…

同理，当调用带参构造函数后（假设传入16），内部数组elementData长度的增长趋势为：16->24->36->54->81…

**结论一：**无参构造函数创建的ArrayList对象，初始内部数组长度为0，第一次调用add后长度变为10，后续当数组内元素超过数组长度后，长度增长是当前数组长度的0.5倍

**结论二：**带参构造函数创建的ArrayList对象，初始内部数组长度为0，第一次调用add后长度变为10，后续当数组内元素超过数组长度后，长度增长是当前数组长度的0.5倍

**问题二：**ArrayList查询快这个都能理解，增删 *** 作一定慢吗？

要回答这个问题我们同样看下相关源码：

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

public void add(int index, E element) {
        rangeCheckForAdd(index);

        ensureCapacityInternal(size + 1);  // Increments modCount!!
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        elementData[index] = element;
        size++;
}

第一个方法是在ArrayList的尾部添加元素，这是如果内部数组的长度足够，唯一的 *** 作就是赋值即可，只有在内部数组长度不够的情况下才会扩容到当前长度的1.5倍，所以在这种情况下它的性能并不比其他List差。

第二个方法是将元素插入到指定的位置，这是需要把index后面的元素通过System.arraycopy一次性复制到内部数组的后一位，index越小需要复制的元素就越多，所以这种情况下它的性能是很低的。

同理我们可以看下删除 *** 作的源码。

**结论一：**在ArrayList的尾部增加或删除元素时，性能其实还不错，和其他的List（例如linkedList）差不多。

**结论二：**当不在ArrayList的尾部增加或删除元素时，性能比较低，在首部增删元素时性能达到最低。

同时还可以关注公众号“小西学JAVA”获取更多精彩文章。