ArrayList源码阅读分析
1.1 ArrayList介绍
ArrayList一个数组队列，相当于 动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。
ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供<span style="color:red;font-weight:bold"><u>快速访问功能</u></span>的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。
ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
和Vector不同，ArrayList中的操作不是线程安全的！所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
1.2 ArrayList源码
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.
* 默认容量 10
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 空数组，如果传入的容量为0时使用
*/
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.1 ArrayList构造方法
(1).ArrayList()
- 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
- 使用这个数组是在添加第一个元素的时候会扩容到默认大小10
/**
* 使用 new ArrayList() 创建时默认使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数
**/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
(2). ArrayList(int initialCapacity)
public ArrayList(int initialCapacity) {
//传入的初始容量大于0，初始化elementData数组对应的大小容量
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
}
//传入的初始容量等于0，使用一个空数组 EMPTY_ELEMENTDATA
else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
// 如果传入的初始容量小于0，抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
(3). ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) {
// 将集合先转换成数组
Object[] a = c.toArray();
// 将size赋值为转换后数组的长度且判断转换后数组的长度是否等于0
if ((size = a.length) != 0) {
//判断传入的元素是否为ArratList类型，如果是，则直接将elementData赋值为传入的集合转换后的数组
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
// 如果传入的是不是ArrayList类型，重新拷贝成Object[].class类型
elementData = Arrays.copyOf(a, size, Object[].class);
}
} else {
// 传入的集合为一个空集合，初始化一个空数组 EMPTY_ELEMENTDATA
elementData = EMPTY_ELEMENTDATA;
}
}
1.2.2 ArrayList添加元素（增）
(1). add(E e)
添加元素到末尾，平均时间复杂度为O(1)。
public boolean add(E e) {
//初始化容量判断
ensureCapacityInternal(size + 1); // Increments modCount!!
//将元素插入到最后一位
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
//modCount 为一个全局性变量，记录结构性改变的次数
modCount++;
//当数组大小大于此时数组中元素个数，进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//判断是否是第一次添加数据，如果为第一次，则初始化默认大小10，反之则返回当前数组下标
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA，就初始化为默认大小10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//ArrayList 扩容机制
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//每次扩容为之前容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量发现比需要的容量还小，则以需要的容量为准
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 如果新容量已经超过最大容量了，则使用最大容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 以新容量拷贝出来一个新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
(2). add(int index, E element)
添加元素到指定位置，平均时间复杂度为O(n)。
public void add(int index, E element) {
// 检查索引是否越界
rangeCheckForAdd(index);
//初始化容量判断
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将inex及其之后的元素往后挪一位，则index位置处就空出来了
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将元素插入到index的位置
elementData[index] = element;
// 大小增1
size++;
}
/**
* 检查索引是否越界
**/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
(3). addAll(Collection<? extends E> c)
两个集合的第一个并集
public boolean addAll(Collection<? extends E> c) {
// 将集合先转换成数组
Object[] a = c.toArray();
// 获取集合转换成数组的长度
int numNew = a.length;
// 检查是否需要扩容 （可跟踪查看add(E e)方法）
ensureCapacityInternal(size + numNew); // Increments modCount
// 将c中元素全部拷贝到数组的最后
System.arraycopy(a, 0, elementData, size, numNew);
// 大小增加c的大小
size += numNew;
// 如果c不为空就返回true，否则返回false
return numNew != 0;
}
(4). addAll(int index, Collection<? extends E> c)
在指定索引位置位置添加集合元素
两个集合的并集。
public boolean addAll(int index, Collection<? extends E> c) {
// 检查索引是否越界
rangeCheckForAdd(index);
// 将集合先转换成数组
Object[] a = c.toArray();
// 获取集合转换成数组的长度
int numNew = a.length;
// 检查是否需要扩容 （可跟踪查看add(E e)方法）
ensureCapacityInternal(size + numNew); // Increments modCount
// 如果index不是最后一位，则将index之后的元素往后挪numNew个位置，将从numMoved的位置空出放入传入的元素
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 将c中元素全部拷贝到数组
System.arraycopy(a, 0, elementData, index, numNew);
// 大小增加c的大小
size += numNew;
// 如果c不为空就返回true，否则返回false
return numNew != 0;
}
// 判断索引是否越界
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
1.2.3 ArrayList删除元素（删）
(1). remove(int index)
删除指定索引位置的元素，时间复杂度为O(n)。
public E remove(int index) { //检查索引是否越界 rangeCheck(index); //modCount 为一个全局性变量，记录结构性改变的次数 modCount++; //获取索引位置元素 E oldValue = elementData(index); // 如果index不是最后一位，则将index之后的元素往前挪一位 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index,numMoved); // 将最后一个元素删除，帮助GC elementData[--size] = null; // clear to let GC do its work // 返回删除的旧元素 return oldValue;}
(2). remove(Object value)
删除指定元素值的元素，时间复杂度为O(n)。
public boolean remove(Object o) { //如果要删除的元素为null if (o == null) { // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除 for (int index = 0; index < size; index++) // 如果要删除的元素为null，则以null进行比较，使用== if (elementData[index] == null) { fastRemove(index); return true; } } else { // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除 for (int index = 0; index < size; index++) // 如果要删除的元素不为null，则进行比较，使用equals()方法 if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false;}// 快速删除private void fastRemove(int index) { //modCount 为一个全局性变量，记录结构性改变的次数 modCount++; // 如果index不是最后一位，则将index之后的元素往前挪一位 int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); // 将最后一个元素删除，帮助GC elementData[--size] = null; // clear to let GC do its work}
(3). removeAll(Collection<?> c)
从此列表中移除包含在指定集合中的所有元素
public boolean removeAll(Collection<?> c) { //在运行时对对象做非null检查 Objects.requireNonNull(c); //批量删除 return batchRemove(c, false);}/** * 批量删除元素 * complement为true表示删除c中不包含的元素 * complement为false表示删除c中包含的元素*/private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; // 使用读写两个指针同时遍历数组 // 读指针每次自增1，写指针放入元素的时候才加1 // 这样不需要额外的空间，只需要在原有的数组上操作就可以了 int r = 0, w = 0; boolean modified = false; try { // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准） for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 正常来说r最后是等于size的，除非c.contains()抛出了异常 if (r != size) { // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 将写指针之后的元素置为空，帮助GC // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置） size = w; // 有修改返回true modified = true; } } return modified;}
(4). clear()
清空列表中的元素，但是不修改列表的容量大小
public void clear() { //modCount 为一个全局性变量，记录结构性改变的次数 modCount++; // clear to let GC do its work // 将数组内的元素都置空，等待垃圾收集器收集，不减小数组容量。 for (int i = 0; i < size; i++) elementData[i] = null; size = 0;}
1.2.4 ArrayList修改元素（改）
(1) set(int index)
根据索引修改元素
public E set(int index, E element) { // 检查索引是否越界 rangeCheck(index); // 根据索引取出元素 E oldValue = elementData(index); // 根据索引修改数组元素 elementData[index] = element; // 返回修改之前的值 return oldValue;}//检查索引是否越界 private void rangeCheck(int index) { if (index < 0 || index >= this.size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}
1.2.5 ArrayList取出元素（查）
(1). get(int index)
获取指定索引位置的元素，时间复杂度为O(1)。
//根据索引取出元素public E get(int index) { //(1) 检查索引是否越界 rangeCheck(index); //（2）返回索引位置处的元素； return elementData(index);}// 判断索引是否越界//（1）检查索引是否越界，这里只检查是否越上界，如果越上界抛出IndexOutOfBoundsException异常，如果越下界抛出的是ArrayIndexOutOfBoundsException异常。private void rangeCheck(int index) { if (index >= size) throw new IndexOutOfBoundsException(outOfBoundsMsg(index));}//根据索引返回元素E elementData(int index) { return (E) elementData[index];}
(2). retainAll(Collection<?> c)
求两个集合的交集
public boolean retainAll(Collection<?> c) { //在运行时对对象做非null检查 Objects.requireNonNull(c); // 调用批量删除方法，这时complement传入true，表示删除不包含在c中的元素 return batchRemove(c, true);}/** * 批量删除元素 * complement为true表示删除c中不包含的元素 * complement为false表示删除c中包含的元素*/private boolean batchRemove(Collection<?> c, boolean complement) { final Object[] elementData = this.elementData; // 使用读写两个指针同时遍历数组 // 读指针每次自增1，写指针放入元素的时候才加1 // 这样不需要额外的空间，只需要在原有的数组上操作就可以了 int r = 0, w = 0; boolean modified = false; try { // 遍历整个数组，如果c中包含该元素，则把该元素放到写指针的位置（以complement为准） for (; r < size; r++) if (c.contains(elementData[r]) == complement) elementData[w++] = elementData[r]; } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. // 正常来说r最后是等于size的，除非c.contains()抛出了异常 if (r != size) { // 如果c.contains()抛出了异常，则把未读的元素都拷贝到写指针之后 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 将写指针之后的元素置为空，帮助GC // clear to let GC do its work for (int i = w; i < size; i++) elementData[i] = null; modCount += size - w; // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置） size = w; // 有修改返回true modified = true; } } return modified;}
(3). indexOf(Object o)
查找元素在列表中第一次出现的索引位置
public int indexOf(Object o) { // 判断元素是否为null，如果为null则查找null第一次出现在列表中的位置 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; } // 查找不到该元素则返回-1 return -1;}
(4). lastIndexOf(Object o)
查找元素在列表中最后一次出现的索引位置
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; } // 查找不到该元素则返回-1 return -1;}
(5). contains(Object o)
查找列表是否包含该元素
public boolean contains(Object o) { // 列表中存在该元素则返回该元素第一次出现的索引，否则返回-1 return indexOf(o) >= 0;}
1.3 ArrayList总结
（1）ArrayList内部使用数组存储元素，当数组长度不够时进行扩容，每次加一半的空间，ArrayList不会进行缩容；
（2）ArrayList支持随机访问，通过索引访问元素极快，时间复杂度为O(1)；
（3）ArrayList添加元素到尾部极快，平均时间复杂度为O(1)；
（4）ArrayList添加元素到中间比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（5）ArrayList从尾部删除元素极快，时间复杂度为O(1)；
（6）ArrayList从中间删除元素比较慢，因为要搬移元素，平均时间复杂度为O(n)；
（7）ArrayList支持求并集，调用addAll(Collection<? extends E> c)方法即可；
（8）ArrayList支持求交集，调用retainAll(Collection<? extends E> c)方法即可；
（7）ArrayList支持求单向差集，调用removeAll(Collection<? extends E> c)方法即可；
1.4 ArrayList常见面试题
-
ArrayList是什么？可以用来干嘛？
ArrayList就是有序的动态数组列表，主要⽤来装载数据，它的主要底层实现是数组Object[]查询效率高,增删效率低
-
ArrayList与LinkedList的区别？
1、ArrayList基于动态数组实现的非线程安全的集合；LinkedList基于链表实现的非线程安全的集合。2、对于随机index访问的get和set方法，一般ArrayList的速度要优于LinkedList。因为ArrayList直接通过数组下标直接找到元素；LinkedList要移动指针遍历每个元素直到找到为止。3、新增和删除元素，一般LinkedList的速度要优于ArrayList。因为ArrayList在新增和删除元素时，可能扩容和复制数组；LinkedList实例化对象需要时间外，只需要修改指针即可。4、LinkedList集合不支持 高效的随机随机访问（RandomAccess）5、ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间（扩容），而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
-
ArrayList 的默认长度
默认长度为10当我们第一次向数组中添加数据的时候才会初始化数组,相当于懒加载
-
ArrayList是怎么扩容的？
再add(E e)添加新数据的时候会进行一个判断,当我们添加的数据超过数组的长度时,数组就会进行扩容这里分为两步: 1.先创建一个原数组长度1.5倍的新数组 1.7: 是原来数组的1.5倍 + 1 1.8: 使用位移运算符向右一位,效率要高很多 2.然后再把旧的数组copy到新的数组
-
ArrayList插入、删除、查询元素的时间复杂度各是多少？
add(E e)方法添加元素到末尾，平均时间复杂度为O(1)。add(int index, E element)方法添加元素到指定位置，平均时间复杂度为O(n)。remove(int index)方法删除指定索引位置的元素，时间复杂度为O(n)。remove(Object o)方法删除指定元素值的元素，时间复杂度为O(n)。get(int index)方法获取指定索引位置的元素，时间复杂度为O(1)。总结：总的来说，不论是删除还是新增，其实本质上都是移动位置，当指定位置新增的时候，新增的索空出，后面向后移一位，然后赋值，当删除时，也是一样，将要删除的索引下标的值置为null。 (增删慢，查询快)
-
ArrayList的遍历和LinkedList遍历性能⽐较如何？
ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
-
为啥线程不安全还使用ArrayList呢？
因为在我们正常得使用场景中，都是用来查询的，不会涉及太频繁的增删，如果涉及到频繁的增删，可以使用LinkedList，如果需要线程安全的就是可以使用Vector，CopyOrWriteArrayList
-
ArrayList的遍历如何?
ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
发表于 2021-10-13 13:54
|
发表于 2021-10-14 14:53
