ArrayList源码阅读分析
1.1 ArrayList介绍
![image-20211012160617267](https://wangchaoz97.oss-cn-shenzhen.aliyuncs.com/markdown/image/image-20211012160617267.png)
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的内部缓存结构会缓存连续的内存片段,可以大幅降低读取内存的性能开销。