ArrayList源码分析

510 阅读4分钟

ArrayList是在实际项目中一个非常常用的类,今天我们通过源码来了解一下ArrayList的本质

内部变量说明

	//默认容量
    private static final int DEFAULT_CAPACITY = 10;

	//使用有参构造创建ArrayList的时候,如果size=0那么elementData就会指向这个数组,或者调用trimToSize(0)方法也会指向这个空数组
    private static final Object[] EMPTY_ELEMENTDATA = {};

	//只有使用无参构造的时候才会将elementData指向这个空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

	//内部的元素数组,我们使用get()方法其实就是从其中取出元素
    transient Object[] elementData; // non-private to simplify nested class access

	//ArrayList的长度,默认为0
    private int size;

	//ArrayList的临界值,如果下一次扩容的数值大于这个数值,那么将elementData扩容到数组的最大值也就是0x7fffffff,如果最小需要的容量已经大于0x7fffffff那么则抛出OOM异常
	private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

初始化

ArrayList()

我们要使用ArrayList必定要先new一个出来,现在我们来看看new 到底做了写什么.

ArrayList<Object> arrayList = new ArrayList<>();

在我们调用这样一个空参构造的时候,ArrayList实际上帮我们创建了一个空的数组,口说无凭,可以来看看

	/**
	* 构造一个空list并且初始化容量为10(如果只是单纯的new实际上并没有初始化容量)
     * 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 = {};

是的,他就是一个长度为0的Object的对象数组. 这个是一个 默认的静态被final修饰的的空数组实例,每一个array list实例被new出来一开始都共享这个空数组实例.

ArrayList(int initialCapacity)和ArrayList(Collection<? extends E> c)

当我们调用这两个方法中的其中一个方法的时候,如果 initialCapacity==0或者c.size()==0那么内部的element将会指向EMPTY_ELEMENTDATA

问题:不是已经有了一个空数组(DEFAULTCAPACITY_EMPTY_ELEMENTDATA)了为什么还要有一个空数组(EMPTY_ELEMENTDATA)呢?

用一个场景来解释这个问题

在我们创建ArrayList 的时候,如果使用ArrayList<>(int initialCapacity)指定初始化容量的方式来创建,这时候传参是0那么,ArrayList内部的容器指向的就是这个EMPTY_ELEMENTDATA

在执行add方法的时候,如果是使用无参构造的方式创建的ArrayList 那么就会直接初始化其容量为10.

如果是使用有参构造的方式创建的ArrayList那么就会执行正常的扩容方式

说白了就是,DEFAULTCAPACITY_EMPTY_ELEMENTDATA就是一个标记,用来区分ArrayList是不是无参构造创建的ArrayList

1557540713333

添加元素

void add(E e)

当我们添加元素的时候只需要调用add方法就行了,但是你知道其背后到底执行了哪些动作吗?让我们接着往下看吧!

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

我们来看看流程

流程

看了流程之后,你可能会有诸多问题.

到底是怎么计算扩容的容量的?

添加元素是怎么添加的?

扩容容量是怎么计算的?

此处以**void add(E e)**为例

当我们添加一个元素的时候,如果这个元素是通过无参构造创建的(为了不让思路变得更复杂,此处只针对void add(E e)方法添加元素的容量计算),那么就将其容量初始化为 DEFAULT_CAPACITY,也就是10(还记得开始我们介绍了其内部的变量吗,就是那个DEFAULT_CAPACITY)

看起来这样做就足够了,但是java为了避免溢出,又做了一层处理

新容量= 原来的容量+原来的容量/2 这块有两层判断,

newCapacity-minCapacity<0 newCapacity-MAX_ARRAY_SIZE>0 (同newCapacity-Integer.MAX_VALUE - 8>0 )

第二个其实还想得通当超过最大数组长度的时候就将其扩展到Integer.MAX_VALUE

那第一个新的容量为什么会小于最小的容量呢?

实际上是因为Integer超过最大范围再加会溢出直接变为-2^32.

元素是如何添加的?

重新创建一个新的数组,将其靠拷贝

System.arraycopy()

得到元素

E get(int index)

  • 此方法会先检查index是否是有效的索引
  • 是有效的则会从内部数组elementData中强转并且返回该元素
  • 不是有效的则会抛出IndexOutOfBoundsException异常

结语:

  • ArrayList是基于数组实现的.
  • ArrayList的扩容算法是 oldLength+oldLength>>1,也就是oldLength+oldLength/2
  • ArrayList是扩容是重新分配一片空间,将原来的内容拷贝进去.
  • ArrayList理论上的最大长度是Integer.MAX_VALUE