源码解析java集合框架，ArrayList源码

忘是亡心i 2022-03-02 01:26 401阅读 0赞

### 一、ArrayList剖析 ###

ArrayList是List接口下的一个实现类，ArrayList是一个动态数组，**底层数据结构为可以动态增长的数组**，相比数组来说，ArrayList可以动态的增加删除元素，有成熟的扩容算法。

![20190319135312319.png][]         0          1             2             3            4           ......          23           24          25

如图，为ArrayList数据结构，是一个内存连续且紧凑的数组。ArrayList访问元素时间复杂度为O(1)，插入、删除需要移动大量元素，时间复杂度为O(n)，ArrayList适合存储及访问数据，不适合操作频繁的数据存储。

ArrayList非线程安全，多线程中不能使用ArrayList，可使用Vector。

### 二、源码解读 ###

**1、构造方法**

**1.1 无参构造方法**

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

无参构造方法，里面只有一个赋值操作，把 DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 赋值给 elementData，我们来看看它们都是什么：

> transient Object\[\] elementData; // non-private to simplify nested class access

> private static final Object\[\] DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA = \{\};

elementData 是一个Object数组，用来存储ArrayList元素，可见，ArrayList底层就是一个动态数组。

DEFAULTCAPACITY\_EMPTY\_ELEMENTDATA 是一个空数组，所以，调用无参构造方式只是新建一个空Object数组。

**1.2 有参构造方法**

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

传入初始容量参数的构造方法，参数为整形，代表初始化Object数组长度。可以看到，当参数为0时，同样给 elementData 赋值了一个空Object数组。当大于0时，新建相应长度的数组。

**2、ArrayList的新增元素方法**

**2.1 public boolean add(E e)**

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

传入需要添加的元素e，elementData\[size++\] = e 把元素放置数组size++位置，紧接在后面。

ensureCapacityInternal(size + 1); 为ArrayList扩容，扩容是ArrayList中尤为重要且相对复杂的部分。

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;
    }
    
    /** Default initial capacity.  */
    private static final int DEFAULT_CAPACITY = 10;

calculateCapacity() 方法传入了新增元素后的容量minCapacity，也就是size++，和当前Object数组elementData。先判断elementData是否为空，如果为空则返回minCapacity与DEFAULT\_CAPACITY中较大者，DEFAULT\_CAPACITY是ArrayList初始化最小的容量，DEFAULT\_CAPACITY值为10，所以，ArrayList的容量最小为10。

再来看ensureExplicitCapacity()方法：

protected transient int modCount = 0;
    
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

ensureExplicitCapacity()方法传入了minCapacity与DEFAULT\_CAPACITY比较之后的值，先是做判断，如果当前数组长度不够，则调用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()方法是ArrayList真正扩容方法，oldCapacity >> 1 位移运算，相当于oldCapacity \* 0.5，所以扩容后新的容量为1.5倍，每次增长0.5倍，最后使用Arrays工具类构建新的容量更大的数组。

**2.2 public void add(int index, E element)**

这个add()方法传入了两个参数，一个是所增加的元素，和新元素插入的位置索引index。

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

首先对index索引位置检验，不能超过数组长度，不能传负数，否则抛异常。

然后以同样的方式1.5倍扩容，再使用本地native方法System.arraycopy()把index后所有元素向后移动1，再把element元素插入到index位置，数组长度加1，相对上一个add()方法多了一个移动元素操作，很大可能需要移动大量元素，时间复杂度增加O(n)。

扩容机制小结

如果ArrayList初始化没指定容量，则最初ArrayList为空的数组，添加元素后初始化容量为10，当容量不够了每次增加0.5倍。

如果初始化指定容量则新建相应长度的数据，再往里添加元素，容量不够再每次增加0.5倍。

**3、ArrayList的获取元素方法get(index)**

public E get(int index) {
    
        rangeCheck(index);
        return elementData(index);
    }

获取元素方法很简单，先对索引位置检验，是否超出数组长度，否则抛异常outofindex。

然后直接返回相应位置的元素，获取操作非常简便，时间复杂度很低，性能高。

**4、ArrayList的移除元素方法remove(index)、remove(object)**

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()大量向前移动元素。

public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }

这个方法传入的是要删除的元素值，思路是根据元素值匹配到元素所在的索引位置index，再向前移动后面的元素。

可见，移除元素同样需要移动大量的元素，时间复杂度大。

> 后语，ArrayList底层就是对象数组，添加和移除元需要移动大量元素，效率低。相反，查询操作效率十分高，只需返回对应索引的元素。
> 
> ArrayList适合存放查询数据，不适合有删减改动的数据。

[20190319135312319.png]: /images/20220302/5c0ee82eb6a64ad7b3acde3d18d9148c.png