java集合-ArrayList

最近在使用java刷leetcode。在刷题期间，经常会用到java的集合类ArrayList，由于担心ArrayList的效率问题，所以看了一下ArrayList的源码，记录下来加深印象。

一、数据结构

从ArrayList的类名不难看出，ArrayList内部是由数组实现的。与之相对的则是LinkedList，后者内部是由链表实现的。根据数组和链表的特性可知，数组在查询时性能优于链表，链表则比较适合删除、插入操作较多的场景。所以需要根据不同的应用场景选择不同的集合类使用。

 transient Object[] elementData;//ArrayList内部用于存储元素的Object数组，transient表示不可序列化

二、内部数组初始容量与扩容机制

1.初始化

ArrayList有三种初始化方式

public ArrayList();

使用默认构造器，内部数组的初始容量为0。

public ArrayList(Collection<? extends E> c)

使用一个集合来初始化，并将该集合的元素加入到ArrayList中。

public ArrayList(int initialCapacity) 

使用指定的大小来初始化内部数组。

ArrayList中还有一个默认容量

private static final int DEFAULT_CAPACITY = 10;

但是这个默认容量并不是初始化时给内部数组指定一个容量，而是在第一次执行add时，如果当前的内部数组为空，则会在扩容时直接将数组容量扩容为10，在下面calculateCapacity方法的源码中可以看出

2.扩容

由于ArrayList可以不断地加入新的对象，所以内部数组的容量不可能是一成不变的。所以ArrayList就必须提供一个扩容机制来保证内部数组容量足以容纳所需加入的元素。

在执行add方法时，会执行ensureCapacityInternal方法，下面是ArrayList实现的两个add方法

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

接下来，我们接着看ensureCapacityInternal的实现

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

显然这个方法所做的工作主要在calculateCapacity和ensureExplicitCapacity两个方法中，所以我们接下来看一下这两个方法的源码

 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);//扩容工作在grow方法中进行
    }

从ensureExplicitCapacity的源码看出，扩容的工作是在grow方法中进行的，下面对grow方法进行分析

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

grow方法中比较重要的一个操作是int newCapacity = oldCapacity + (oldCapacity >> 1);我们可以明显看出，扩容后的新容量等于旧容量+旧容量/2，也就相当于每次扩容1.5倍。