Java集合(二一): ArrayList源码剖析
1、ArrayList简介
ArrayList是List接口的大小可变数组的实现；ArrayList允许null元素；ArrayList的容量可以自动增长；ArrayList不是同步的；ArrayList的iterator和listIterator方法返回的迭代器是fail-fast的
ArrayList的iterator和listIterator方法返回的迭代器是快速失败的：在创建迭代器之后，除非通过迭代器自身的remove或add方法从结构上对列表进行修改，否则在任何时间以任何方式对列表进行修改，迭代器都会抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险。
2、ArrayList数据结构
容量：capacity ；
元素个数：size；
ArrayList底层的数据结构就是数组，数组元素类型为Object类型，即可以存放所有类型数据。我们对ArrayList类的实例的所有的操作底层都是基于数组的。
3、ArrayList源码分析
3.1 ArrayList继承结构和层次关系
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable结构图更直观些： 
分析：
1）为什么要先继承AbstractList，而让AbstractList先实现List<E>？而不是让ArrayList直接实现List<E>？
有一个思想，接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁。就继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码。所以一般看到一个类上面还有一个抽象类，应该就是这个作用。
2）ArrayList实现了哪些接口？
**List<E>接口：**我们会出现这样一个疑问，在查看了ArrayList的父类AbstractList也实现了List<E>接口，那为什么子类ArrayList还是去实现一遍呢？
开发这个collection 的作者Josh说：这其实是一个mistake，因为他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在。
**RandomAccess接口：**这个是一个标记性接口，通过查看api文档，它的作用就是用来快速随机存取，有关效率的问题，在实现了该接口的话，那么使用普通的for循环来遍历，性能更高，例如arrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了让我们知道我们用什么样的方式去获取数据性能更好。
**Cloneable接口：**实现了该接口，就可以使用Object.Clone()方法了。
**Serializable接口：**实现该序列化接口，表明该类可以被序列化，什么是序列化？简单的说，就是能够从类变成字节流传输，然后还能从字节流变成原来的类。
3.2、类中属性
// 序列化id
private static final long serialVersionUID = 8683452581122892189L;
//默认初始容量为10
private static final int DEFAULT_CAPACITY = 10;
//构造器中 指定该ArrayList容量为0时，返回该空数组。
private static final Object[] EMPTY_ELEMENTDATA = {};
// 当调用无参构造方法，返回的是该数组。
//它与EMPTY_ELEMENTDATA的区别就是：
//该数组是默认返回的，而EMPTY_ELEMENTDATA是在用户指定容量为0时返回。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList的容量就是该数组的长度。
//该值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时，当第一次添加元素进入ArrayList中时，
//数组将扩容值DEFAULT_CAPACITY。
//被标记为transient，在对象被序列化的时候不会被序列化。
transient Object[] elementData; // non-private to simplify nested class access
//ArrayList的实际大小即数组包含的元素个数，默认为0
private int size;
/**
* 分派给arrays的最大容量，为什么要减去8呢？
* 因为某些JVM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致array容量
大于JVM的limit，最终导致OutOfMemoryError。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//备注：MAX.VALUE为0x7fffffff，转换成十进制就是2147483647，也就是数组的最大长度是2147483639；3.3、构造方法
1）、无参构造
属性中 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 是一个空的Object[]，将elementData初始化，elementData也是个Object[]类型。空的Object[]会给默认容量10。但是这里我们并没有看到数组的容量变为10，那么什么时候会被初始化为10的数组呢？是有元素被加入时(add方法)。当进行第一次add的时候，elementData将会变成默认的长度：10。
//构造一个初始容量为10的空列表
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}2）、带初始容量的构造
构造一个指定容量为capacity的空ArrayList。这是一个带初始容量大小的有参构造函数。
- 初始容量大于0，实例化数组，将自定义的容量大小当成初始化elementData的大小
- 初始容量等于0，将空数组赋给elementData
- 初始容量小于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);
}
}3）、带集合参数的构造
构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
- 将collection对象转换成数组，然后将数组的地址的赋给elementData
- 如果数组的元素个数等于0，将空数组EMPTY_ELEMENTDATA赋值给elementData
- 如果size的值大于0，则执行Arrays.copy方法，把collection对象的内容（可以理解为深拷贝）copy到elementData中。
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//每个集合的toarray()的实现方法不一样，所以需要判断一下，
//如果不是Object[].class类型，那么就需要使用ArrayList中的方法去改造一下。
if (elementData.getClass() != Object[].class)
//copyOf(要复制的数组,要返回的副本的长度,要返回的副本的类)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}**总结：**arrayList的构造方法就做一件事情，就是初始化一下储存数据的容器，其实本质上就是一个数组，在其中就叫elementData。
3.4、核心方法
3.4.1、add()方法（有四个）
boolean add(E)；//默认直接在末尾添加元素
当容量不足时，是如何实现动态扩容的?
下面就通过add方法来说明这些问题。(add方法是list接口中声明的通用方法)。
size是当前集合拥有的元素个数(未算进准备新增的e元素)，从源码看出，调用了ensureCapacityInternal来保证容量问题，传进去的参数是size+1，来保证新增元素后容量满足要求。
接下来进入 ensureCapacityInternal方法查看其实现：
可以看到代码段：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}通过这一步来判断，当前 elementData是否为空数组(即初始化容量为0或者调用了无参构造函数后的结果)，如果是，则使用 Math.max(DEFAULT_CAPACITY, minCapacity)进行选择一个较大的，其中，DEFAULT_CAPACITY是ArrayList定义的静态常量10：
可以看出，这里如果minCapacity小于10的话(如果elementData为空的话，size+1即minCapacity一般为1)，返回的是10，所以如果没有指定大小的话，默认是初始化一个容量为10的数组。然后在调用 ensureExplicitCapacity方法：
在这个方法里进行判断，新增元素后的大小minCapacity是否超过当前集合的容量elementData.length，如果超过，则调用 grow方法进行扩容。我们进入该方法进行查看:
在这里可以很清楚的看到扩容容量的计算:int newCapacity = oldCapacity + (oldCapacity >> 1)，其中oldCapacity是原来的容量大小，oldCapacity >> 1 为位运算的右移操作，右移一位相当于除以2，所以这句代码就等于int newCapacity = oldCapacity + oldCapacity / 2；即容量扩大为原来的1.5倍(注意我这里使用的是jdk1.8），获取newCapacity后再对newCapacity的大小进行判断，如果仍然小于minCapacity，则直接让newCapacity 等于minCapacity，而不再计算1.5倍的扩容。然后还要再进行一步判断，即判断当前新容量是否超过最大的容量 if (newCapacity - MAX_ARRAY_SIZE > 0)，如果超过，则调用hugeCapacity方法，传进去的是minCapacity，即新增元素后需要的最小容量：
如果minCapacity大于MAX_ARRAY_SIZE，则返回Integer的最大值。否则返回MAX_ARRAY_SIZE。
然后回到grow方法，调用Arrays.copyof方法，即复制原数组内容到一个新容量的大数组里。这里Arrays.copyof方法实际是调用System.arraycopy方法。
**个人理解：对于grow()，**minCapacity表示新增元素后需要的最小容量，newCapacity表示扩容1.5倍后的容量，如果newCapacity<minCapacity表示扩容后还放不下元素，则直接扩容为minCapacity；此时如果newCapacity>max_array_size，则需要根据minCapacity与max_array_size关系决定最终扩容为max_value还是max_array_size。
3.4.2、void add(int，E)
在特定位置添加元素，也就是插入元素
public void add(int index, E element) {
rangeCheckForAdd(index);//检查index也就是插入的位置是否合理。
//跟上面的分析一样，具体看上面
ensureCapacityInternal(size + 1); // Increments modCount!!
//这个方法就是用来在插入元素之后，要将index之后的元素都往后移一位，
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在目标位置上存放元素
elementData[index] = element;
size++;//size增加1
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0) //插入的位置肯定不能大于size 和小于0
//如果是，就报这个越界异常
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}3.4.3、remove()方法
1）remove(int)：通过删除指定位置上的元素
public E remove(int index) {
rangeCheck(index);//检查index的合理性
modCount++;//这个作用很多，比如用来检测快速失败的一种标志。
E oldValue = elementData(index);//通过索引直接找到该元素
int numMoved = size - index - 1;//计算要移动的位数。
if (numMoved > 0)
//这个方法也已经解释过了，就是用来移动元素的。
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//将--size上的位置赋值为null，让gc(垃圾回收机制)更快的回收它。
elementData[--size] = null; // clear to let GC do its work
//返回删除的元素。
return oldValue;
}2）remove(Object)：这个方法可以看出来，arrayList是可以存放null值。
通过元素来删除该元素，就依次遍历，如果有这个元素，就将该元素的索引传给fastRemobe(index)，使用这个方法来删除该元素。public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}3）clear()：将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉，所以叫clear
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}总结：remove函数用户移除指定下标的元素，此时会把指定下标到数组末尾的元素向前移动一个单位，并且会把数组最后一个元素设置为null，这样是为了方便之后将整个数组不被使用时，会被GC，可以作为小的技巧使用。
3.4.4、set(index，element)方法
public E set(int index, E element) {
// 检验索引是否合法
rangeCheck(index);
// 旧值
E oldValue = elementData(index);
// 赋新值
elementData[index] = element;
// 返回旧值
return oldValue;
}确保set的位置小于当前数组的长度（size）并且大于0，获取指定位置（index）元素，然后放到oldValue存放，将需要设置的元素放到指定的位置（index）上，然后将原来位置上的元素oldValue返回给用户。
3.4.5、get(index)
public E get(int index) {
// 检验索引是否合法
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}说明：get函数会检查索引值是否合法（只检查是否大于size，而没有检查是否小于0），值得注意的是，在get函数中存在element函数，element函数用于返回具体的元素。
说明：返回的值都经过了向下转型（Object -> E），这些是对我们应用程序屏蔽的小细节。
3.4.6 indexOf()和lastIndexOf()方法
返回此列表中指定元素的第一个出现项的索引，如果该列表不包含该元素，则返回-1。
public int indexOf(Object o) {
if (o == null) { // 查找的元素为空
for (int i = 0; i < size; i++) //遍历数组，找到第一个为空的元素，返回下标
if (elementData[i]==null)
return i;
} else { // 查找的元素不为空
// 遍历数组，找到第一个和指定元素相等的元素，返回下标
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}返回此列表中指定元素的最后一次出现的索引，如果该列表不包含该元素，则返回-1。
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}四、总结
1）arrayList可以存放null。
2）arrayList本质上就是一个elementData数组。
3）arrayList区别于数组的地方在于能够自动扩展大小，其中关键的方法就是gorw()方法。
4）arrayList中removeAll(collection c)和clear()的区别就是removeAll可以删除批量指定的元素，而clear是全是删除集合中的元素。
5）arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果
6）arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环
五、补充说明
1、问题1：c.toArray might (incorrectly) not return Object[] (see 6260652)官方Bug
在ArrayList或者CopyOnWriteArrayList等源码中，以Collection为参数的构造方法中为什么会出现红框中的判断呢，难道c.toArray()返回的还不一定是Object类型的数组？
原因：不是所有Collection的实现类的 toArray方法都返回 Object[] 类型
是所有Collection的实现类的 toArray方法都返回 Object[] 类型
例如Arrays.asList() 所返回的实现类的toArray()方法返回的就不是真正的Object[] （可以去看它的源码，它返回的是泛型类型，就是你指定的类型） 那这样会导致什么问题呢？
会导致无法插入Object类型。这时候如果有
// 抛出异常 java.lang.ArrayStoreException: java.lang.Object
objects2[0] = new Object();存不进去。也就是说，我们不能光根据声明时的类型来填充数据。例如
Object[] array = new Integer[3];
array[0] = 1;
//Exception in thread "main" java.lang.ArrayStoreException: java.lang.Object
array[1] = new Object();
//Exception in thread "main" java.lang.ArrayStoreException: java.lang.String
array[2] = "a";这个数组就存不进去 Object类型的数据，所以他不是个真正能放Object的数组。
而ArrayList源码中的elementData数组一定要是Object[]类型的，所以这里才需要判断一下，如果不是，则用Arrays.copy转换一下。
2、快速报错机制ConcurrentModificationException
Java容器有一种保护机制，能够防止多个进程同时修改同一个容器的内容。如果你在迭代遍历某个容器的过程中，另一个进程介入其中，并且插入，删除或修改此容器的某个对象，就会立刻抛出ConcurrentModificationException。
迭代遍历指的就是使用迭代器Iterator(ListIterator)或者forEach语法，实际上一个类要使用forEach就必须实现Iterable接口并且重写它的Iterator方法所以forEach本质上还是使用Iterator。
从下面方法可以看到在迭代遍历的过程中都调用了方法checkForComodification来判断当前ArrayList是否是同步的。
举例：
假设你往一个Integer类型的ArrayList插入了10条数据，那么每操作一次modCount（继承自父类AbstractList）就加一所以就变成10。
当你对这个集合进行遍历的时候就把modCount传到expectedModCount这个变量里，然后ArrayList在checkForComodification中通过判断两个变量是否相等来确认当前集合是否是同步的，如果不相等，则不同步就抛出ConcurrentModificationException。
所谓的不同步指的就是，如果你在遍历的过程中对ArrayList集合本身进行add,remove等操作时候就会发生。当然如果你用的是Iterator那么使用它的remove是允许的因为此时你直接操作的不是ArrayList集合而是它的Iterator对象。在代码后面将贴出前面提到的三种情况。此外在多线程也会存在这种情况，但是如果你在多线程中使用CopyOnWriteArrayList就可以避免了。
public Iterator<E> iterator() {
return new Itr();
}
private class Itr implements Iterator<E> {
int cursor; // 下一个要返回的索引
int lastRet = -1; // 返回最后一个元素的索引
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
//防止篇幅过长省去了其中代码
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
//防止篇幅过长省去其中代码
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}第一种情况使用Iterator：
第二种情况使用forEach：
第三种情况使用Iterator自身删除数据：
参考：java1.8源码之ArrayList源码解读_技术探求-CSDN博客_arraylist源码
ArrayList构造函数 c.toArray might (incorrectly) not return Object[] (see 6260652)_一颗小小的石头.的博客-CSDN博客
版权说明 : 本文为转载文章, 版权归原作者所有 版权申明
原文链接 : https://blog.csdn.net/mingyuli/article/details/120385077
内容来源于网络，如有侵权，请联系作者删除！
相关文章
热门标签
更多最新文章
更多- 浏览(705) 发布于 5个月前
- 浏览(254) 发布于 5个月前
- 浏览(244) 发布于 5个月前
- 浏览(247) 发布于 5个月前
- 浏览(247) 发布于 5个月前