ArrayList源码解析

了解ArrayList

在项目中大家肯定经常使用ArrayList，但是你对ArrayList了解多少呢？

• ArrayList实现了List接口
• 底层存储数据使用数组存储
• 内存满时会自动触发扩容机制
• …

ArrayList有很多值得学习的地方，接下来我们更深入的了解ArrayList。

ArrayList中的参数

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] 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 = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access

/**
 * The size of the ArrayList (the number of elements it contains).
 *
 * @serial
 */
private int size;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

创建ArrayList

创建ArrayList的方法非常简单，相信大家都使用过，通常会使用以下两种情况来创建

//调用空参构造器
ArrayList<String> list1 = new ArrayList<>();
//调用有参构造器
ArrayList<String> list2 = new ArrayList<>(10);
1
2
3
4

空参构造器

DEFAULTCAPACITY_EMPTY_ELEMENTDATA是空数组，使用空参构造器创建的ArrayList是一种懒加载的模式

也就是说创建ArrayList时并不设定他的大小，而是在使用的时候设置数组大小

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

有参构造器

而在有参构造器的情况下

如果参数大于0，则是直接将数组的长度定下来

如果等于0，也是一个空数组，相当于空参构造器

如果小于0，则会抛出异常

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);
    }
}
1
2
3
4
5
6
7
8
9
10

ArrayList中的add方法

初始化ArrayList时，size的默认值为0，所以先执行的是ensureCapacityInternal(1);

也就是说我们最先执行的方法是calculateCapacity(elementData, 1)

如果当前数组是空的话，他会将传入的1与DEFAULT_CAPACITY（10）做比较，返回较大的那个，在这个情况下我们会返回10，然后执行ensureExplicitCapacity(10);

modCount是用来记录该集合被修改的次数，这个暂时不需要深入研究

接下来执行判断语句，minCapacity是10，而当前数组是空的，所以必定会触发grow(10)

grow也是我们的扩容方法，这里其实算是触发了扩容，当前的数组长度为0，存入一个数据触发扩容，这套逻辑走下来，newCapaciry为10，也就是会触发elementData = Arrays.copyOf(elementData, 10);

这里介绍一下Arrays.copyOf(array,size)：返回一个新的数组对象，size指的是新数组对象的长度，如果超过了原数组长度，则保留数组默认值，并且将array复制到新的数组

到此我们知道了，调用空参构造器创建的ArrayList是以懒加载的方式执行，并且在第一次add时默认大小为10

ArrayList的扩容

其实在第一次add的方法执行时，就已经进行过一遍ArrayList的扩容，我们不妨在进一步的了解一下它的扩容机制

    public static void main(String[] args) {
        ArrayList<String> list = new ArrayList<>();
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
        list.add("a");
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

ArrayList的默认大小为10，当我们执行第11次add方法时，会自动触发扩容

按照上述add方法执行下来，最终会走到grow方法中，并且参数是11

这里我们注意第二行代码int newCapacity = oldCapacity + (oldCapacity >> 1);，这行代码非常清晰的想我们展示了ArrayList的扩容因子是1.5，也就是说每次扩容都是原数组长度的1.5倍

ArrayList的get方法

get方法的源码非常的简单，一步校验，一步返回

rangeCheck方法作用是判断下标是否越界

直接返回指定下标的数组的元素

ArrayList的remove方法

对于remove(int)方法，ArrayList会先删除数组中该下标的元素，并且让它后面所有的元素都前一一位，将最后一个下标的位置置为null。

介绍一个方法：System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

• src：原数组
• srcPos：原数组要复制的起始位置
• dest：目标数组
• destPos：目标数组放置的起始位置
• length：复制的长度

Vector与ArrayList的区别

相同点

• 初始容量都是10
• 底层都是基于数组实现

不同点

• ArrayList线程不安全，Vector线程安全

• 虽然初始容量都是10，但ArrayList是懒加载，而Vector是直接创建空间

• 默认情况下，ArrayList的扩容因子是1.5，Vector的扩容因子是2

• Vector可以手动设置扩容因子