Java集合框架-浅析ArrayList的源码实现

写在前面

  以前,一直认为任何东西的源码都是很高深的,不管是JDK的源码,还是Spring的源码,以我的水平,肯定看不懂。可是,最近看好多面试经验都好像问到了集合框架的源码以及其它框架的源码,为了找到一个喜欢的工作,只能硬着头皮去看了。网上查了一些资料,根据别人的经验去读,理解了之后,发现Java的集合框架并没有想象的那么难。写这篇文章,主要是想自己试着去分析一下Java集合框架中ArrayList的源码实现,并记录下来。


源码版本

  • JDK:JDK 8u131

关于ArrayList

  ArrayList是继承了AbstractList类,实现了List、RandomAccess、Cloneable、java.io.Serializable接口,是顺序容器,允许放入null元素。其底层是通过数组实现,准确的来说是一个动态Object数组。至于,为什么是Object数组,是因为所有的类都是Object的子类,这样ArrayList就可以支持所有的类了。JDK 1.5之后更是引入了泛型的概念,使得我们直接在使用ArrayList的时候,标明我们要存放的数据类型就可以了。


重要属性

1
2
3
4
5
6
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  1. 底层数组默认容量
  2. 空的Object数组,ArrayList中如果有需要将底层数组设置为空的时候,通常会指向它
  3. 默认空的Object数组,直接new一个ArrayList时,无参数的构造方法会默认将底层数组指向它
  4. 底层的数组,没什么好说的
  5. ArrayList中元素的个数,是逻辑长度,表示存放了多少个元素
  6. 底层数组最大容量,该变量上面注释大概的意思是一些虚拟机限制,如果超过会报内存溢出错误。我查到的资料是说,最大容量还是Integer.MAX_VALUE,至于-8是为了降低出错的几率

方法浅析

ArrayList(int initialCapacity)

  传入一个整型参数的构造方法,通过传入的初始化值来创建底层数组,底层数组的容量就为initialCapacity。当然如果初始化值等于0,则直接将底层数组指向EMPTY_ELEMENTDATA,也就是上面提到的空的Object数组。如果初始化值小于0,则抛出非法容量异常。

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

ArrayList(Collection<? extends E> c)

  传入一个集合参数的构造方法,将传入的集合转为数组,并赋值给底层数组。下面将底层数组的长度赋值给size,并判断是否为空数组,如果为空,则指向EMPTY_ELEMENTDATA,否则判断该数组的类型是不是Object数组,如果不是,则通过数组复制方法,将类型转为Object数组并赋值到底层数组。

1
2
3
4
5
6
7
8
9
10
11
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

ArrayList()

  无参构造方法,使用最普遍的构造方法。该方法的实现只有一行,就是直接将底层数组指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个默认的空Object数组。这个地方我要特别说一下:之前,看的一些面试题,面试官会问ArrayList的默认长度(可能用长度表示不太准确,但是我看的几个都是说默认长度)是多少?回答都统一说是10,可是,我怎么看源码也是直接指向一个空数组啊,就算上面定义了默认容量是10,可是这个时候也没有使用它啊,只有在使用add等方法的时候才会创建出这个容量为10的底层数组。抱着疑惑,再一次找到面试题,看了看时间,发现是几年前,我就想是不是版本的原因。然后,下载了JDK 7,发现和之前情况是一样的,又下载了JDK 6,恍然大悟。原来JDK 6中ArrayList的无参构造方法,直接调用了this(10),这才发现了问题的关键。原来,JDK的开发人员,在某一个版本开始,使用了“懒”操作,首先将底层数组指向空数组,新增元素或者其它相关操作时才创建默认容量为10的数组。至于哪一个版本,我也不知道,我只看了6、7和8的版本,各个大版本之间又有好多小版本。

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

get(int index)

  通过传入的下标获取底层数组中的元素,返回时需要强制类型转换。

1
2
3
4
5
public E get(int index) {
rangeCheck(index); // 下标越界检查

return elementData(index); // 获取指定下标的元素,该方法主要代码就一行:(E) elementData[index]
}

set(int index, E element)

  向指定下标插入元素,并将该下标对应的原来的元素返回。

1
2
3
4
5
6
7
public E set(int index, E element) {
rangeCheck(index); // 下标越界检查

E oldValue = elementData(index); // (E) elementData[index],同上
elementData[index] = element;
return oldValue;
}

add(E e)

  在ArrayList尾添加元素。

1
2
3
4
5
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 如果容量不够动态扩容数组,详细的后面进行记录
elementData[size++] = e;
return true;
}

add(int index, E element)

  在指定下标插入元素。

1
2
3
4
5
6
7
8
9
public void add(int index, E element) {
rangeCheckForAdd(index); //检查下标是否合法

ensureCapacityInternal(size + 1); // 如果容量不够动态扩容数组,详细的后面进行记录
System.arraycopy(elementData, index, elementData, index + 1,
size - index); //相当于将index后的元素都向后移动一位,给要插入的元素空出位置
elementData[index] = element;
size++;
}

addAll(Collection<? extends E> c)

  在ArrayList尾添加一个集合,一般是添加另一个ArrayList。

1
2
3
4
5
6
7
8
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // 如果容量不够动态扩容数组,详细的后面进行记录
System.arraycopy(a, 0, elementData, size, numNew); //将数组a的数据复制到底层数组的后面
size += numNew;
return numNew != 0; //如果传入的参数长度为0,则返回false
}

addAll(int index, Collection<? extends E> c)

  在指定下标开始插入集合,和add(int index, E element)类似。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);

Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount

int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);

System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}

remove(int index)

  删除指定下标的元素,返回被删除的元素。需要注意的是,Java的垃圾回收不是万能的,我们删除的那个元素,如果不将其在底层数组中对应的下标赋值为null的话,它们之间就还存在引用,GC就不会回收,所以,最后将其赋值为null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

数组扩容

  ArrayList的底层是通过数组实现的,我们也知道数组一旦定义,容量就是定死的,那么,在ArrayList怎么实现动态扩容呢?

ensureCapacityInternal(int minCapacity)

  该方法中,判断如果底层数组指向的是默认空数组的话,就从默认容量和传入的最小容量中取最大的,来定义数组。如果不是,则调用ensureExplicitCapacity

1
2
3
4
5
6
7
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}

ensureExplicitCapacity(int minCapacity)

  该方法中主要是判断传入的最小容量是否大于当前底层数组的容量或者说当前底层数组的长度,如果大于,则表示需要扩容,所以调用grow方法。

1
2
3
4
5
6
7
private void ensureExplicitCapacity(int minCapacity) {
modCount++; //查了下这个好像涉及到fail-fast机制

// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

grow(int minCapacity)

  在该方法中,主要是将数组长度先扩容到原来的1.5倍,1.5倍能保证在这之后还能进行多次的添加操作而无需进行耗资源的扩容操作。

1
2
3
4
5
6
7
8
9
10
11
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0) //addAll()方法可能添加很多,所以判断,如果小于传入的最小容量,
newCapacity = minCapacity; //则使用最小容量作为新数组的长度
if (newCapacity - MAX_ARRAY_SIZE > 0) //如果大于所限制的最大容量,则在方法hugeCapacity()中
newCapacity = hugeCapacity(minCapacity); //判断取哪个值
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}

小结

  这篇文章写了近四个小时,虽然写完很有成就感,但是在这个关键时刻,不应该这么浪费时间啊。写完这篇,等以后有时间了再记录其它集合框架相关的内容吧。


参考资料

Author: HowieLi
Link: https://www.howieli.cn/posts/java-collections-arraylist.html
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.