ArrayList源码阅读分析

独怜发表于 2021-10-13 13:54

本帖最后由独怜于 2021-10-13 14:00 编辑

## ArrayList源码阅读分析

### 1.1 ArrayList介绍

!(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源码

```java
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()

1. 如果没有传入初始容量，则使用空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA
2. 使用这个数组是在添加第一个元素的时候会扩容到默认大小10

```java
/**
*使用 new ArrayList() 创建时默认使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA这个空数
**/
public ArrayList() {
   this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
```

#####(2). ArrayList(int initialCapacity)

```java
public ArrayList(int initialCapacity) {
         //传入的初始容量大于0，初始化elementData数组对应的大小容量
   if (initialCapacity > 0) {
         this.elementData = new Object;
   }
         //传入的初始容量等于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)

```java
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)。

```java
public boolean add(E e) {
         //初始化容量判断
   ensureCapacityInternal(size + 1);// Increments modCount!!
         //将元素插入到最后一位
   elementData = 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)。

```java
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 = element;

// 大小增1
size++;
}
/**
* 检查索引是否越界
**/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
   throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```

##### (3). addAll(Collection<? extends E> c)

两个集合的第一个并集

```java
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)

在指定索引位置位置添加集合元素

两个集合的并集。

```java
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)。

```java
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)。

```java
public boolean remove(Object o) { //如果要删除的元素为null if (o == null) {    // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除    for (int index = 0; index < size; index++)          // 如果要删除的元素为null，则以null进行比较，使用==          if (elementData == null) {             fastRemove(index);             return true;          } } else {       // 遍历整个数组，找到元素第一次出现的位置，并将其快速删除    for (int index = 0; index < size; index++)          // 如果要删除的元素不为null，则进行比较，使用equals()方法          if (o.equals(elementData)) {             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)

从此列表中移除包含在指定集合中的所有元素

```java
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) == complement)             elementData = elementData; } 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 = null;          modCount += size - w;          // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）          size = w;          // 有修改返回true          modified = true;    } } return modified;}
```

##### (4). clear()

清空列表中的元素，但是不修改列表的容量大小

```java
public void clear() { //modCount 为一个全局性变量，记录结构性改变的次数 modCount++; // clear to let GC do its work // 将数组内的元素都置空，等待垃圾收集器收集，不减小数组容量。 for (int i = 0; i < size; i++)    elementData = null; size = 0;}
```

#### 1.2.4 ArrayList修改元素（改）

##### (1) set(int index)

根据索引修改元素

```java
public E set(int index, E element) { // 检查索引是否越界 rangeCheck(index);    // 根据索引取出元素 E oldValue = elementData(index); // 根据索引修改数组元素 elementData = 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)。

```java
//根据索引取出元素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;}
```

##### (2). retainAll(Collection<?> c)

求两个集合的交集

```java
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) == complement)             elementData = elementData; } 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 = null;          modCount += size - w;          // 新大小等于写指针的位置（因为每写一次写指针就加1，所以新大小正好等于写指针的位置）          size = w;          // 有修改返回true          modified = true;    } } return modified;}
```

##### (3). indexOf(Object o)

查找元素在列表中第一次出现的索引位置

```java
public int indexOf(Object o) { // 判断元素是否为null，如果为null则查找null第一次出现在列表中的位置 if (o == null) {    for (int i = 0; i < size; i++)          if (elementData==null)             return i; } else {    // 查找元素在列表中第一次出现的位置    for (int i = 0; i < size; i++)          if (o.equals(elementData))             return i; } // 查找不到该元素则返回-1 return -1;}
```

##### (4). lastIndexOf(Object o)

查找元素在列表中最后一次出现的索引位置

```java
public int lastIndexOf(Object o) { if (o == null) {    // 倒序查找最后一次出现时的位置    for (int i = size-1; i >= 0; i--)          if (elementData==null)             return i; } else {    for (int i = size-1; i >= 0; i--)          if (o.equals(elementData))             return i; } // 查找不到该元素则返回-1 return -1;}
```

##### (5). contains(Object o)

查找列表是否包含该元素

```java
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常见面试题

1. ArrayList是什么？可以用来干嘛？

```
ArrayList就是有序的动态数组列表，主要⽤来装载数据，它的主要底层实现是数组Object[]查询效率高,增删效率低
```

2. 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的空间花费则体现在它的每一个元素都需要消耗相当的空间
```

3. ArrayList 的默认长度

```
默认长度为10当我们第一次向数组中添加数据的时候才会初始化数组,相当于懒加载
```

4. ArrayList是怎么扩容的？

```
再add(E e)添加新数据的时候会进行一个判断,当我们添加的数据超过数组的长度时,数组就会进行扩容这里分为两步: 1.先创建一个原数组长度1.5倍的新数组    1.7: 是原来数组的1.5倍 + 1    1.8: 使用位移运算符向右一位,效率要高很多 2.然后再把旧的数组copy到新的数组
```

5. 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。 (增删慢，查询快)
```

6. ArrayList的遍历和LinkedList遍历性能⽐较如何？

```
ArrayList要比LinkedList快得多，ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
```

7. 为啥线程不安全还使用ArrayList呢？

```
因为在我们正常得使用场景中，都是用来查询的，不会涉及太频繁的增删，如果涉及到频繁的增删，可以使用LinkedList，如果需要线程安全的就是可以使用Vector，CopyOrWriteArrayList
```

8. ArrayList的遍历如何?

```
ArrayList遍历最大的优势在于内存的连续性，CPU的内部缓存结构会缓存连续的内存片段，可以大幅降低读取内存的性能开销。
```

youle999 发表于 2021-10-13 14:28

感谢大神分享。

龙小发表于 2021-10-13 14:29

感谢大佬分享知识

xiaoaiai2468 发表于 2021-10-13 14:48

感谢大佬的分享

momo2021 发表于 2021-10-13 19:38

楼主发篇LinkedList解析的帖子吧

独怜发表于 2021-10-14 14:53

momo2021 发表于 2021-10-13 19:38
楼主发篇LinkedList解析的帖子吧

整理完了就发出来

独怜发表于 2021-10-14 17:48

momo2021 发表于 2021-10-13 19:38
楼主发篇LinkedList解析的帖子吧

LinkedList看下这个哈， https://www.52pojie.cn/forum.php?mod=viewthread&tid=1527949&page=1&extra=#pid40325053

angel_bai 发表于 2021-11-12 09:10

谢谢分享

he183137 发表于 2021-11-12 09:45

很详细，感谢分享

xiaocai66 发表于 2021-11-16 10:48

学习到了，谢谢大佬分享

页: [1]

吾爱破解 - 52pojie.cn's Archiver

ArrayList源码阅读分析