ArrayList扩容机制以及底层实现

简介

　　来源：博客园作者：吾王彦

　　博客链接：https://www.cnblogs.com/qinjunlin/p/13724987.html

　　ArrayList动态数组，是 java 中比较常用的数据结构。继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。本随笔主要讲述ArrayList的扩容机制以及它的底层实现。如果懒得看整个分析过程，你可以直接查看文章最后的总结。

成员变量

 1    private static final int DEFAULT_CAPACITY = 10;  //默认的初始容量为10

 2

 3     private static final Object[] EMPTY_ELEMENTDATA = {};  //空数组

 4

 5     /**

 6      *与默认的初始容量DEFAULT_CAPACITY区分开来，

 7      *简单来讲就是第一次添加元素时知道该 elementData

 8      *从空的构造函数还是有参构造函数被初始化的。以便确认如何扩容。

 9      **/

10     private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//空数组，与EMPTY_ELEMENTDATA空数组区分

11

12      /**

13     * 存储ArrayList元素的数组缓冲区。

14     * ArrayList的容量是这个数组缓冲区的长度。

15     *任何空的ArrayList 即 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA

16     *当添加第一个元素时，将扩展为DEFAULT_CAPACITY。

17      **/

18     transient Object[] elementData;

19

20     private int size;  //实际元素个数

构造函数

有参构造

1 /**

2      * 构造一个初始容量为10的空ArrayList

3      */

4     public ArrayList() {

5         this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

6     }

这里需要注意，注释（是我翻译后的）是说构造一个容量大小为 10 的空的 list 数组，但这里构造函数了只是给 elementData 赋值了一个空的数组，实际上并未开始扩容，这时候的容量还是0，真正开始扩容其实是在第一次添加元素时才容量扩大至 10 的。

有参构造函数

下面的代码是构造一个大小为 initialCapacity 的 ArrayList

 1 public ArrayList(int initialCapacity) {

 2     if (initialCapacity > 0) {  //当 initialCapacity 大于零时初始化一个大小为 initialCapacity 的 object 数组并赋值给 elementData

 3         this.elementData = new Object[initialCapacity];

 4     } else if (initialCapacity == 0) {  //当 initialCapacity 为零时则是把 空数组EMPTY_ELEMENTDATA 赋值给 elementData

 5         this.elementData = EMPTY_ELEMENTDATA;

 6     } else {

 7         throw new IllegalArgumentException("Illegal Capacity: "+

 8                                        initialCapacity);

 9     }

10 }

使用指定 Collection 来构造 ArrayList 的构造函数。将 Collection 转化为数组并赋值给 elementData。

 1 public ArrayList(Collection<? extends E> c) {

 2     elementData = c.toArray();

 3     if ((size = elementData.length) != 0) {

 4         // c.toArray might (incorrectly) not return Object[] (see 6260652)

 5         if (elementData.getClass() != Object[].class) //判断 elementData 的 class 类型是否为 Object[]，不是的话则做一次转换

 6         elementData = Arrays.copyOf(elementData, size, Object[].class);//

 7     } else {

 8         // size 为零，则将空数组赋给elementData，相当于new ArrayList(0)

 9         this.elementData = EMPTY_ELEMENTDATA;

10     }

11 }

产生扩容的操作

add方法

 1 public boolean add(E e) {

 2     ensureCapacityInternal(size + 1);  //每次添加元素到集合中时都会先确认下集合容量大小

 3     elementData[size++] = e;  //size 自增 +1。

 4     return true;

 5 }

 6

 7 //确认容量大小

 8 private void ensureCapacityInternal(int minCapacity) {

 9     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));

10 }

11

12 //返回容量大小

13 private static int calculateCapacity(Object[] elementData, int minCapacity) {

14     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {

15         return Math.max(DEFAULT_CAPACITY, minCapacity); //这里其实才是真正的开始初始化数组的容量大小为10

16     }

17     return minCapacity;

18 }

19

20 //根据确认的容量的大小判断是否进行扩容

21 private void ensureExplicitCapacity(int minCapacity) {

22     modCount++;  //记录操作次数

23

24     // overflow-conscious code

25     if (minCapacity - elementData.length > 0)

26         grow(minCapacity);  //调用扩容方法

27 }

由上面的源代码可知数组的容量大小的初始化是在第一次添加元素的时候才开始的。calculateCapacity方法中有一个判断elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA ，在第一次添加元素的时候，集合本身就是空的，所以会就取 DEFAULT_CAPACITY 和 minCapacity 的最大值也就是 10。

初始化完容量后，之后的每次添加元素都会走一遍上面代码的流程，就是每次添加元素前都会确认容量，然后根据minCapacity是否大于 elementData 的长度来决定是否对集合进行扩容。

grow扩容

 1 //根据确认的容量的大小判断是否进行扩容

 2 private void ensureExplicitCapacity(int minCapacity) {

 3     modCount++;  //记录操作次数

 4

 5     // overflow-conscious code

 6     if (minCapacity - elementData.length > 0)

 7         grow(minCapacity);  //调用扩容方法

 8 }

 9

10 //扩容函数

11 private void grow(int minCapacity) {

12     // overflow-conscious code

13     int oldCapacity = elementData.length;

14     int newCapacity = oldCapacity + (oldCapacity >> 1);  //这里NewCapacity为原来容量的1.5倍

15     if (newCapacity - minCapacity < 0)

16         newCapacity = minCapacity;

17     if (newCapacity - MAX_ARRAY_SIZE > 0)

18         newCapacity = hugeCapacity(minCapacity);

19     // minCapacity is usually close to size, so this is a win:

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

21 }

1 //扩容过大，或者所需容量过大则调用此方法

2 private static int hugeCapacity(int minCapacity) {

3         if (minCapacity < 0) // overflow

4             throw new OutOfMemoryError();

5         return (minCapacity > MAX_ARRAY_SIZE) ?

6             Integer.MAX_VALUE :

7             MAX_ARRAY_SIZE;

8     }

有代码可知，这里的扩容是扩容至原来容量的 1.5 倍。为什么是1.5倍呢？可以看看下面的这个

以无参构造为例。

int oldCapacity = elementData.length; //原容量为10，二进制表示为1010

int newCapacity = oldCapacity + (oldCapacity >> 1); //此处将原来的1010右移一位，变成101，即10进制的5

所以 newCapacity = 10 + 5，即是15 。所以1.5倍是这样来的。

可以理解“>>”右移符号相当于除以2

其次，扩容1.5并不一定是最终的容量大小。因为还有两个判断。

1、如果1.5倍太小的话，则将我们所需的容量大小赋值给newCapacity

2、1.5倍太大或者我们需要的容量太大，则调用 hugeCapacity方法。

太大究竟是多大？请看下面

hugeCapacity方法。中的参数分析

private static int hugeCapacity(int minCapacity) {

        if (minCapacity < 0) // overflow

            throw new OutOfMemoryError();

        return (minCapacity > MAX_ARRAY_SIZE) ?

            Integer.MAX_VALUE :

            MAX_ARRAY_SIZE;

    }

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; //ArrayList的成员变量
Integer.MAX_VALUE的大小为2的31次-1，即2147483647

所以你说大不大？嘻嘻

总结

　　首先，定义一个ArrayList,常用的有两种方式。一种是使用无参构造，即new ArrayList()；另一种是使用有参构造，new ArrayList(6)，new一个初始容量大小为6的ArrayList。

　　使用无参构造定义的ArrayList,在没有添加元素之前，初始容量为0，只有第一次添加元素的时候才会初始化初始容量为10，每次添加元素前都会确认集合的容量大小

如果容量不够用会进行扩容。一般会扩容至原来的1.5倍，如果所需容量太大，会扩容到2的31次-1，或者（2的31次-1）-8（详细看上面代码分析）。

　　使用有参构造定义ArrayList，初始容量大小就是有参定义的大小，new ArrayList(6) ,初始容量就是6 。扩容机制有参无参构造都是一样的。

　　看到这里，你是否还有个疑问，为什么是设计成扩容1.5倍呢？因为，因为他喜欢啊。哈哈哈哈哈。。。。。。。

JDK1.6 ArrayList无参构造，默认容量是10

JDK1.7 ArrayList无参构造，默认容量才改为是0，只有在add()时才初始化为10

这里讨论的是JDK1.8的版本的

巴特西