ArrayList底层原理

不要学习计算机，不然会变成xyn

一、简单介绍ArrayList的底层实现

ArrayList底层数据结构为顺序表，使用数组实现，具体表现为：

1.物理内存上连续

2.逻辑上连续

3.大小可以动态扩展

使用它会有如下特性：

1.利用空参构造时，会在底层创建一个默认长度为0的数组

2.添加第一个元素时，底层会创建一个新的长度为10的数组

3.存满时，会扩容1.5倍

4.如果一次性添加多个数据，超出原数组长度的1.5倍，则会按照多出的数据新建数组

二、ArrayList源码分析

重要的字段

1.elementData字段

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

elementData用来存放ArrayList中的内容，可以看作是利用Object数组存储

2.size字段

private int size;

size是element的内容个数，并非elementData的长度

3.DEFAULT_CAPACITY字段

private static final int DEFAULT_CAPACITY = 10;

数组使用无参数构造时，最小默认长度为10

4.EMPTY_ELEMENTDATA、DEFAULTCAPACITY_EMPTY_ELEMENTDATA字段

private static final Object[] EMPTY_ELEMENTDATA = {};

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

使用无参构造时的默认返回，均为长度为0的数组

构造方法

1.无参构造

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

无参构造直接把DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个赋值给elementData来初始化，人话就是创建了一个长度为0的数组

2.参数为int值的构造方法

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

如果给出一个int值的长度，就将其传入elementData，如果长度为0就把EMPTY_ELEMENTDATA赋值给elementData进行初始化

Add方法

当使用如下代码时，你的java虚拟机是这样做的

ArrayList<String> list = new ArrayList<>();
list.add("aaa");

1.空参构造list，传入DEFAULTCAPACITY_EMPTY_ELEMENTDATA，创建一个长度为0的Object数组

2.使用add方法，添加第一个元素

public boolean add(E e) {
        modCount++;
        add(e, elementData, size);
        return true;
    }

将"aaa"传入到形参e里面，并调用add(e, elementData, size)方法，e为当前要添加的元素，即"aaa"，elementData为集合底层的数组名字，size为集合的长度或者当前元素应存入的位置

3.调用add(e, elementData, size)方法

private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

if语句表示检测数组是不是满了，如果满了就调用无参grow()方法，即数组扩容

如果没满，就将元素添加到size指示的位置，并将size+1

4.数组扩容如下

private Object[] grow() {
        return grow(size + 1);
    }

此时会把size+1，并调用有参的grow()方法，此时size为1，也就是minCapacity为1

private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

利用oldCapacity记录老容量，下面根据if语句分为两种情况

当我们第一次添加数据的时候oldCapacity为0，跳转到else语句

代码会比较DEFAULT_CAPACITY（数值为10）与minCapacity的大小，并使用最大的数值调用，其实就是创建一个长度为10的Object数组

在后面需要扩容时，oldCapacity就不为0，跳转到if语句

1.此时minCapacity为11，oldCapacity为10，并调用newlength()方法

public static int newLength(int oldLength, int minGrowth, int prefGrowth) {
        // preconditions not checked because of inlining
        // assert oldLength >= 0
        // assert minGrowth > 0
        int prefLength = oldLength + Math.max(minGrowth, prefGrowth); // might overflow
        if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) {
            return prefLength;
        } else {
            // put code cold in a separate method
            return hugeLength(oldLength, minGrowth);
        }
    }

2.传入的三个参数分别为oldCapacity老长度，minCapacity - oldCapacity理论上应该新增的容量，oldCapacity >> 1老长度除以2，即默认新增容量的大小

int prefLength = oldLength + Math.max(minGrowth, prefGrowth);

3.此时oldLength为10，minGrowth为1，prefGrowth为5，通过比较minGrowth和prefGrowth的大小，选择更大的一方，默认扩容为原长度的1.5倍，但是如果扩容后的理论值超过原长度的1.5倍，就直接使用理论值来新建数组

4.如果preLength数值正常，就默认将preLength赋值给newCapacity，执行下面的语句

return elementData = Arrays.copyOf(elementData, newCapacity);

使用newCapacity的数值创建新的数组，并把elementData中的所有数据，全部拷贝到新数组中，之后将新数组覆盖到elementData中，进行返回，完成扩容操作