ArrayList 源码分析

Author：空夜
发布时间：January 31, 2020
2606 views
No comments
2623 words
Categories： Java

ArrayList 是最常用的 List 实现类，今天我们从源码角度来分析一下这个类。

## 一、基本结构

首先，我们来看一下 ArrayList 的继承关系，这是一个 UML 图：

![file](http://zfh-public-blog.oss-cn-beijing.aliyuncs.com/image-1580013942597.png)

对于 ArrayList，我们通常是这样使用的：

```java
List<Object> list = new ArrayList<>();
```

下面我们简单看一下接口概要：

```java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
}
```

ArrayList 继承了 AbstractList 这个抽象类，实现了 List，RandomAccess，Cloneable 和序列化接口。

这里需要注意一下 RandomAccess 接口，这个接口没有任何方法，实现这个接口即意味着支持快速随机访问（下标访问）。快速随机访问速度 > 迭代器遍历速度。

快速随机访问的速度是固定的，比如 ArrayList 的 set(i, e), get(i) 等方法，其时间复杂度都是 O(1)

---

## 二、属性

查看 ArrayList 源码，我们看到它主要有如下一些属性，关于这些属性的描述都标注下面了：

```java
// 默认初始化容量
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小空实例的共享空数组实例，与 EMPTY_ELEMENTDATA 的区别在于前者知道当第一个元素插入时该如何扩充数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存储这个 ArrayList 元素的数组。ArrayList 的容量就是这个数组的长度。任何空 ArrayList，如果其 elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则当添加第一个元素时，ArrayList 会扩容到 DEFAULT_CAPACITY 大小。
transient Object[] elementData;
// ArrayList 的大小，指元素的个数
private int size;
// 数组可分配的最大大小
// 某些虚拟机在一个数组里保留了一些标题字。尝试分配更大的数组可能会导致 OutOfMemoryError
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
```

从基本属性可以看出， ArrayList 的底层是基于**数组**的！

即 `Object[] elementData` 这个属性

这里需要注意一点：

- size 是实际元素数量，即 list.size()
- elementData.length 是存储元素的数组的长度，一般是 >= size 的

---

## 三、三个构造器

平时使用 ArrayList，我个人习惯这样构造：

```java
List<Integer> list = new ArrayList<>();
```

实际上，ArrayList 有三个构造器：默认构造器、带初始化容量参数的构造器、带集合参数的构造器

- 默认构造器

```java
  // 使用默认容量 10 构造一个空的 List 
  public ArrayList() {
    // 这里可以看到使用了属性 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  	this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  }
  ```

- 带初始化容量的构造器

```java
  public ArrayList(int initialCapacity) {
          if (initialCapacity > 0) {
              // 构建指定容量的数组
              this.elementData = new Object[initialCapacity];
          } else if (initialCapacity == 0) {
              // 使用 EMPTY_ELEMENTDATA
              this.elementData = EMPTY_ELEMENTDATA;
          } else {
              // 负数，抛出 IllegalArgumentException
              throw new IllegalArgumentException("Illegal Capacity: "+
                                                 initialCapacity);
          }
      }
  ```

- 带集合参数的构造器

```java
  // 构造一个包含指定集合元素的 list，元素顺序按照集合的迭代器返回的顺序
  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;
      }
  }
  ```

**EMPTY_ELEMENTDATA 与 DEFAULT_EMPTY_ELEMENTDATA**

两者的区别在于，使用前者时，当添加第一个元素时，elementData.length = 1；而当使用后者时，会调用 ensureCapacityInternal 方法，使 elmentData.length = DEFAULT_CAPACITY = 10

注意，扩容发生在实际插入元素的时候！使用前两个构造器，elementData 还是空数组。

下面重点总结一下 ArrayList 的扩容机制。

---

## 四、扩容机制

### 4.1 为什么要扩容？

个人理解是，当初始化 ArrayList 时，JVM 并不知道程序会存多少数据进去，而数组又必须在初始化时就声明其容量，这样就造成一个问题，最迟在第一个元素插入时，必须指定数组容量大小、初始化数组以容纳元素。（ArrayList 实际上也正是这么做的！）

那么，程序怎么知道你到底需要多大的容量呢？1 还是 100w ？

最好的办法是可以动态扩容！

ArrayList 就实现了这个扩容功能，我们可以调用方法主动扩容，也可以让 ArrayList 自己扩容。下面来讲一下 ArrayList 的扩容具体是怎么实现的。这个讲解主要是针对源码的分析。

### 4.2 扩容的实现

ArrayList 的扩容是由下面这段代码实现的，我已经加上了注释：

```java
    // 扩容 ArrayList 实例，使其至少能放下 minCapacity 个元素
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            // any size if not default element table
            ? 0
            // larger than default for default empty table. It's already
            // supposed to be at default size.
            : DEFAULT_CAPACITY;

if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

// 确保明确的容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 注意，这里递增了 modCount

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

// 扩容，以确保该 elementData 数组的大小至少能容纳 minCapacity 个元素
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1); // 即扩容到 1.5 倍，等价于 n = o + o/2
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

// 可以扩容的最大容量，当想要扩容的容量大于 MAX_ARRAY_SIZE 时调用
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
```

可以看到，实际扩容方法是：grow(int minCapacity)。最关键的一行代码是：

```java
 int newCapacity = oldCapacity + (oldCapacity >> 1); // 等价于 n = o + o/2
```

这里使用位运算，它的速度非常快！

总结，ArrayList 的扩容是每次扩容到原大小的 **1.5** 倍。

那么，何时进行扩容呢？

### 4.3 何时扩容

从 `public void ensureCapacity(int minCapacity)` 可以看出，我们可以主动调用该方法进行扩容。

此外，在调用 add/addAll 等添加元素的方法时，ArrayList 也会调用内部扩容方法（`ensureCapacityInternal`）来主动扩容。以 add 方法为例：

```java
    // 追加元素 e 到 list 的末尾
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // 我们主要，ensureCapacityInternal 这个方法会调用 ensureExplicitCapacity 这个方法，后者中一行代码 modCount++
        elementData[size++] = e;
        return true;
    }
```

在上面的扩容方法，以及后面会提到的 add 等方法中，都利用了数组的底层方法。毕竟 ArrayList 是基于数组的嘛！下面我们来看一下这个数组的底层方法具体是什么意思？

---

## 五、数组底层方法

我们在 ArrayList 的源码中可以看到出现了两个有关数组复制操作的方法，一个是 Arrays 类中的 Arrays.copyOf 方法，一个是 System.arraycopy 方法，观察源码，前者是基于后者的：

### 5.1 Arrays.copyOf 方法

```java
// 复制指定的数组，截断或填充 null 值使其达到指定长度
// 返回值与 original 数组具有相同的值
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
  			// 调用了 System 类的 arraycopy 方法
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
}
```

### 5.2 System.arraycopy 方法

```java
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
```

详细解释一下：

- 从原数组指定位置，拷贝数据到目标数组。拷贝从原数组的 srcPos 位置开始，拷贝到目标数组的 destPos 位置，拷贝长度为 length，即拷贝从原数组的 srcPos 到 srcPos+length-1，拷贝到目标数组的 destPos 到 destPos+length-1
- 如果原数组和目标数组指向同一个数组对象，则首先拷贝到一个临时数组，然后把临时数组拷贝到原数组中
- 参数：src - 原数组，srcPos - 原数组的拷贝开始位置；dest - 目标数组， destPos - 拷贝到目标数组的开始位置，length - 要拷贝的数组元素的数量

---

## 六、一个问题

看敖冰冰的文章，里面提到了这样一个问题：使用 `public ArrayList(int initialCapacity)` 这个构造器构建 ArrayList 时，何时初始化数组？

通过源码可以看到，在构造器被调用时，就初始化了数组 ！

```java
this.elementData = new Object[initialCapacity];
```

但是，我们需要注意了！这个时候还不能调用 list.get(i) 和 set(i, e) 方法。

嗯？嗯？嗯？！！

原因很简单，list 的 size 此时还是 0 ！

而 ArrayList 添加元素、获取元素的操作都会对数组的边界值（index 和 size 的关系）进行检查。

比如 get(i) 方法：

```java
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
```

rangCheck 方法会检查 index 和 size 之间的关系，如果 index >= size，就会抛出异常：

```java
private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```

比如：

```java
public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10);
        Integer a = list.get(0);
        System.out.println(a);
}
```

运行这段代码，会报以下异常：

```java
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 0, Size: 0
	at java.util.ArrayList.rangeCheck(ArrayList.java:657)
	at java.util.ArrayList.get(ArrayList.java:433)
	at com.aegis.MapTest.main(MapTest.java:13)
```

下面我们来总结一下 ArrayList 里的常用方法：

---

## 七、常用方法

下面是 ArrayList 源码中 public 方法的总结，目前不涉及 JDK 8 相关部分。

### 7.1 基本

**void trimToSize()**

- 修改 ArrayList 实例的容量为当前 list.size()，即当前元素个数。使用这个方法可以使得 ArrayList 容量最小化

```java
public void trimToSize() {
    modCount++;
    if (size < elementData.length) {
        elementData = (size == 0)
          ? EMPTY_ELEMENTDATA
          : Arrays.copyOf(elementData, size);
    }
}
```

**int size()**

- 返回 ArrayList 的大小。指具体元素的大小，而不是 elementData 数组的大小！

```java
public int size() {
	return size;
}
```

**boolean isEmpty()**

- 如果 list 中没有元素，返回 true

```java
public boolean isEmpty() {
    return size == 0;
}
```

**boolean contains(Object o)**

- 判定是否包括某个元素；调用了 indexOf 方法来判定

```java
public boolean contains(Object o) {
        return indexOf(o) >= 0;
}
```

**int indexOf(Object o)**

- 返回指定元素出现的第一个位置 index；如果不存在，则返回 -1

```java
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;
}
```

**int lastIndexOf(Object o)**

- 返回指定元素最后一次出现的位置；如果不存在，就返回 -1 
- 实际上是数组的倒序遍历

```java
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;
}
```

**Object clone()**

- 返回一个数组的浅拷贝
- 这里的浅拷贝不是指 List 本身，而是 List 中的元素。这里的浅拷贝是 Arrays.copyof 方法造成的。

```java
public Object clone() {
        try {
            ArrayList<?> v = (ArrayList<?>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // 这是不应该发生的，因为 ArrayList 实现了 Clone 接口，即 Cloneable 的
            throw new InternalError(e);
        }
    }
```

**public void clear()**

- 从 list 中删除所有元素

```java
public void clear() {
    modCount++;

// clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

size = 0;
}
```

---

### 7.2 toArray

**Object[] toArray()**

- 返回包括这个 list 中所有元素的数组，元素的顺序以 Iterator 返回的顺序为准。
- 这个方法是 array 和 collection 相互转换的桥梁

```java
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
```

**T[] toArray(T[] a)**

- 以指定数组的类型返回包括这个 list 中所有元素的数组
- 如果数组 a 能够容纳这个 list 的元素，则将元素拷贝到这个数组中；否则，拷贝元素到一个新数组，其运行时类型由指定数组确定。
- 如果数组 a 大于 list ，则 a[list.size()] = null

```java
public <T> T[] toArray(T[] a) {
	if (a.length < size)
  	// Make a new array of a's runtime type, but my contents:
    return (T[]) Arrays.copyOf(elementData, size, a.getClass());
  System.arraycopy(elementData, 0, a, 0, size);
  if (a.length > size)
  	a[size] = null;
  return a;
}
```

----

### 7.3 get/set/remove

**E get(int index)**

- 获取 list 中指定位置的元素

```java
public E get(int index) {
  	// 范围检查，如果 index 超出 list 大小，就抛出 IndexOutOfBoundsException
    rangeCheck(index);

return elementData(index);
}
```

**E set(int index, E element)**

- 使用指定元素 element 替换指定位置 index 处的元素
- 返回原来的元素

```java
public E set(int index, E element) {
  	// 检查边界
    rangeCheck(index);

// 旧的元素
    E oldValue = elementData(index);
    // 设置 index 处为新元素 element
  	elementData[index] = element;
    return oldValue;
}
```

**boolean add(E e)**

- 在 list 末尾添加元素。如果成功就返回 true

```java
public boolean add(E e) {
    // 检查容量 - 即是否需要扩容
  	ensureCapacityInternal(size + 1);  // Increments modCount!!
    // 将 size 位置设为
  	elementData[size++] = e;
    return true;
}
```

**void add(int index, E element)**

- 在指定位置插入元素，并将原来的元素和其后的元素全部后移一位（index++）

```java
public void add(int index, E element) {
  			// 检查边界
        rangeCheckForAdd(index);

// 检查容量 - 如需要则扩容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
  			// 将数组中 index 位置开始的数据，拷贝到 index+1 到 size 位置 
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
  			// 将 index 位置设为新元素
        elementData[index] = element;
        size++;
    }
```

**E remove(int index)**

- 移除指定位置的元素，将后面的元素左移一位（index--）
- 返回删除的元素

```java
public E remove(int index) {
  	// 检查边界
    rangeCheck(index);

// 修改 modCount，以便 fail-fast 机制生效
    modCount++;
  	// 获取 index 位置的元素 -- 即要被删除的元素
    E oldValue = elementData(index);

int numMoved = size - index - 1;
    if (numMoved > 0)
      	// 向左移动元素
        System.arraycopy(elementData, index+1, elementData, index,
                         numMoved);
    // 将原先的最后一位设为 null
    elementData[--size] = null; // clear to let GC do its work

return oldValue;
}
```

**boolean remove(Object o)**

```java
public boolean remove(Object o) {
    if (o == null) {
      	// 要删除的对象为 null，则寻找第一个 null 值
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
              	// 调用 fastRemove
                fastRemove(index);
                return true;
            }
    } else {
      	// 
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}
```

---

### 7.4 集合关联操作

**boolean addAll(Collection<? extends E> c)**

- 将集合中所有元素按照迭代器返回的顺序，添加在 list 的末尾
- 如果 list 被改变，就返回 true

```java
public boolean addAll(Collection<? extends E> c) {
    // 集合转数组
    Object[] a = c.toArray();
    int numNew = a.length;
    // 确保容量
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 从数组拷贝元素到 list 中
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}
```

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

- 从指定位置开始插入集合 c 中的元素，这些新元素的位置是按照集合的迭代器的返回顺序，直到所有元素插入完毕。并将之前的元素后移。

```java
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;
}
```

**boolean removeAll(Collection<?> c)**

- 删除集合 c 中在 list 中的相同元素。如果 list 发生改变，就返回 true

```java
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
```

**boolean  retainAll(Collection<?> c)**

- 删除 list 中不包括在集合 c 中的所有元素

```java
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
```

---

### 7.5 迭代器

List 返回的迭代器是 ListIterator 接口，比默认的 Iterator，多出了 hasPrevious 和 previous 方法。

ArrayList 中有两个 ListIterator 的实现类：ListItr 和 Itr。区别就是前者具有修改元素的 set 和 add 方法

**listIterator**

- 返回这个 list 的元素的一个 list 迭代器，元素开始于指定位置。

```java
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
```

- 返回这个 list 的元素的一个 list 迭代器，元素从 0 位置开始

```java
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
```

**iterator**

- 返回这个 list 的迭代器

```java
public Iterator<E> iterator() {
    return new Itr();
}
```

**ListItr 和 Itr 内部类**

- Itr 和 ListItr 的区别就是后者具有修改元素的方法 set 和 add

---

### 7.6 subList

- 返回这个这个 list 的子视图，[fomIndex, toIndex)
- 注意，subList 返回的子 list 和原 ArrayList 指向的是同一个数组。即，对子 list 的操作也会同步映射在原 ArrayList 上，反之亦然。

```java
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
```

---

## 八、总结

- 基于数组，元素有序，支持快速随机访问，即下标访问。

- 实现了动态扩容机制，每次扩容会增大到 1.5 倍
- 元素可以为 null

- 线程不安全。在多线程情况下，请使用 Collections.synchronizedList 方法把 ArrayList 包装为线程安全版本，或直接使用古老的 Vector

---

参考资料：

[Java 集合深入理解之 AbstractList —— CSDN 拭心](https://blog.csdn.net/u011240877/article/details/52834074)

[Java 集合深入理解之 ArrayList —— CSDN 拭心](https://blog.csdn.net/u011240877/article/details/52853989)

[ArrayList 源码解析 —— JavaGuide](https://snailclimb.gitee.io/javaguide/#/docs/java/collection/ArrayList)

[ArrayList 详细介绍 —— skywang12345](https://www.cnblogs.com/skywang12345/p/3308556.html)

[《吊打面试官》系列 - ArrayList —— 敖丙](https://juejin.im/post/5e14b51d5188253a9a213e83)

Last modification：January 31, 2020

请作者喝杯肥宅快乐水吧！

ArrayList 源码分析

空夜 • 2020 年 01 月 31 日

ArrayList 是最常用的 List 实现类，今天我们从源码角度来分析一下这个类。

## 一、基本结构

首先，我们来看一下 ArrayList 的继承关系，这是一个 UML 图：

![file](http://zfh-public-blog.oss-cn-beijing.aliyuncs.com/image-1580013942597.png)

对于 ArrayList，我们通常是这样使用的：

```java
List<Object> list = new ArrayList<>();
```

下面我们简单看一下接口概要：

```java
public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
	// ...
}
```

ArrayList 继承了 AbstractList 这个抽象类，实现了 List，RandomAccess，Cloneable 和序列化接口。

快速随机访问的速度是固定的，比如 ArrayList 的 set(i, e), get(i) 等方法，其时间复杂度都是 O(1)

---

## 二、属性

查看 ArrayList 源码，我们看到它主要有如下一些属性，关于这些属性的描述都标注下面了：

从基本属性可以看出， ArrayList 的底层是基于**数组**的！

即 `Object[] elementData` 这个属性

这里需要注意一点：

- size 是实际元素数量，即 list.size()
- elementData.length 是存储元素的数组的长度，一般是 >= size 的

---

## 三、三个构造器

平时使用 ArrayList，我个人习惯这样构造：

```java
List<Integer> list = new ArrayList<>();
```

实际上，ArrayList 有三个构造器：默认构造器、带初始化容量参数的构造器、带集合参数的构造器

- 默认构造器

- 带初始化容量的构造器

- 带集合参数的构造器

**EMPTY_ELEMENTDATA 与 DEFAULT_EMPTY_ELEMENTDATA**

注意，扩容发生在实际插入元素的时候！使用前两个构造器，elementData 还是空数组。

下面重点总结一下 ArrayList 的扩容机制。

---

## 四、扩容机制

### 4.1 为什么要扩容？

那么，程序怎么知道你到底需要多大的容量呢？1 还是 100w ？

最好的办法是可以动态扩容！

### 4.2 扩容的实现

ArrayList 的扩容是由下面这段代码实现的，我已经加上了注释：

if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

// 确保明确的容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++; // 注意，这里递增了 modCount

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

可以看到，实际扩容方法是：grow(int minCapacity)。最关键的一行代码是：

```java
 int newCapacity = oldCapacity + (oldCapacity >> 1); // 等价于 n = o + o/2
```

这里使用位运算，它的速度非常快！

总结，ArrayList 的扩容是每次扩容到原大小的 **1.5** 倍。

那么，何时进行扩容呢？

### 4.3 何时扩容

从 `public void ensureCapacity(int minCapacity)` 可以看出，我们可以主动调用该方法进行扩容。

此外，在调用 add/addAll 等添加元素的方法时，ArrayList 也会调用内部扩容方法（`ensureCapacityInternal`）来主动扩容。以 add 方法为例：

---

## 五、数组底层方法

### 5.1 Arrays.copyOf 方法

### 5.2 System.arraycopy 方法

```java
public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);
```

详细解释一下：

---

## 六、一个问题

看敖冰冰的文章，里面提到了这样一个问题：使用 `public ArrayList(int initialCapacity)` 这个构造器构建 ArrayList 时，何时初始化数组？

通过源码可以看到，在构造器被调用时，就初始化了数组 ！

```java
this.elementData = new Object[initialCapacity];
```

但是，我们需要注意了！这个时候还不能调用 list.get(i) 和 set(i, e) 方法。

嗯？嗯？嗯？！！

原因很简单，list 的 size 此时还是 0 ！

而 ArrayList 添加元素、获取元素的操作都会对数组的边界值（index 和 size 的关系）进行检查。

比如 get(i) 方法：

```java
public E get(int index) {
    rangeCheck(index);
    return elementData(index);
}
```

rangCheck 方法会检查 index 和 size 之间的关系，如果 index >= size，就会抛出异常：

```java
private void rangeCheck(int index) {
	if (index >= size)
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
```

比如：

```java
public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(10);
        Integer a = list.get(0);
        System.out.println(a);
}
```

运行这段代码，会报以下异常：

下面我们来总结一下 ArrayList 里的常用方法：

---

## 七、常用方法

下面是 ArrayList 源码中 public 方法的总结，目前不涉及 JDK 8 相关部分。

### 7.1 基本

**void trimToSize()**

- 修改 ArrayList 实例的容量为当前 list.size()，即当前元素个数。使用这个方法可以使得 ArrayList 容量最小化

**int size()**

- 返回 ArrayList 的大小。指具体元素的大小，而不是 elementData 数组的大小！

```java
public int size() {
	return size;
}
```

**boolean isEmpty()**

- 如果 list 中没有元素，返回 true

```java
public boolean isEmpty() {
    return size == 0;
}
```

**boolean contains(Object o)**

- 判定是否包括某个元素；调用了 indexOf 方法来判定

```java
public boolean contains(Object o) {
        return indexOf(o) >= 0;
}
```

**int indexOf(Object o)**

- 返回指定元素出现的第一个位置 index；如果不存在，则返回 -1

**int lastIndexOf(Object o)**

- 返回指定元素最后一次出现的位置；如果不存在，就返回 -1 
- 实际上是数组的倒序遍历

**Object clone()**

- 返回一个数组的浅拷贝
- 这里的浅拷贝不是指 List 本身，而是 List 中的元素。这里的浅拷贝是 Arrays.copyof 方法造成的。

**public void clear()**

- 从 list 中删除所有元素

```java
public void clear() {
    modCount++;

// clear to let GC do its work
    for (int i = 0; i < size; i++)
        elementData[i] = null;

size = 0;
}
```

---

### 7.2 toArray

**Object[] toArray()**

- 返回包括这个 list 中所有元素的数组，元素的顺序以 Iterator 返回的顺序为准。
- 这个方法是 array 和 collection 相互转换的桥梁

```java
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}
```

**T[] toArray(T[] a)**

----

### 7.3 get/set/remove

**E get(int index)**

- 获取 list 中指定位置的元素

```java
public E get(int index) {
  	// 范围检查，如果 index 超出 list 大小，就抛出 IndexOutOfBoundsException
    rangeCheck(index);

return elementData(index);
}
```

**E set(int index, E element)**

- 使用指定元素 element 替换指定位置 index 处的元素
- 返回原来的元素

```java
public E set(int index, E element) {
  	// 检查边界
    rangeCheck(index);

// 旧的元素
    E oldValue = elementData(index);
    // 设置 index 处为新元素 element
  	elementData[index] = element;
    return oldValue;
}
```

**boolean add(E e)**

- 在 list 末尾添加元素。如果成功就返回 true

**void add(int index, E element)**

- 在指定位置插入元素，并将原来的元素和其后的元素全部后移一位（index++）

```java
public void add(int index, E element) {
  			// 检查边界
        rangeCheckForAdd(index);

**E remove(int index)**

- 移除指定位置的元素，将后面的元素左移一位（index--）
- 返回删除的元素

```java
public E remove(int index) {
  	// 检查边界
    rangeCheck(index);

// 修改 modCount，以便 fail-fast 机制生效
    modCount++;
  	// 获取 index 位置的元素 -- 即要被删除的元素
    E oldValue = elementData(index);

return oldValue;
}
```

**boolean remove(Object o)**

---

### 7.4 集合关联操作

**boolean addAll(Collection<? extends E> c)**

- 将集合中所有元素按照迭代器返回的顺序，添加在 list 的末尾
- 如果 list 被改变，就返回 true

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

- 从指定位置开始插入集合 c 中的元素，这些新元素的位置是按照集合的迭代器的返回顺序，直到所有元素插入完毕。并将之前的元素后移。

```java
public boolean addAll(int index, Collection<? extends E> c) {
  	// 边界值检查
    rangeCheckForAdd(index);

// 要插入的元素和数量
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount

**boolean removeAll(Collection<?> c)**

- 删除集合 c 中在 list 中的相同元素。如果 list 发生改变，就返回 true

```java
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, false);
}
```

**boolean  retainAll(Collection<?> c)**

- 删除 list 中不包括在集合 c 中的所有元素

```java
public boolean retainAll(Collection<?> c) {
    Objects.requireNonNull(c);
    return batchRemove(c, true);
}
```

---

### 7.5 迭代器

List 返回的迭代器是 ListIterator 接口，比默认的 Iterator，多出了 hasPrevious 和 previous 方法。

ArrayList 中有两个 ListIterator 的实现类：ListItr 和 Itr。区别就是前者具有修改元素的 set 和 add 方法

**listIterator**

- 返回这个 list 的元素的一个 list 迭代器，元素开始于指定位置。

```java
public ListIterator<E> listIterator(int index) {
    if (index < 0 || index > size)
        throw new IndexOutOfBoundsException("Index: "+index);
    return new ListItr(index);
}
```

- 返回这个 list 的元素的一个 list 迭代器，元素从 0 位置开始

```java
public ListIterator<E> listIterator() {
    return new ListItr(0);
}
```

**iterator**

- 返回这个 list 的迭代器

```java
public Iterator<E> iterator() {
    return new Itr();
}
```

**ListItr 和 Itr 内部类**

- Itr 和 ListItr 的区别就是后者具有修改元素的方法 set 和 add

---

### 7.6 subList

```java
public List<E> subList(int fromIndex, int toIndex) {
    subListRangeCheck(fromIndex, toIndex, size);
    return new SubList(this, 0, fromIndex, toIndex);
}
```

---

## 八、总结

- 基于数组，元素有序，支持快速随机访问，即下标访问。

- 实现了动态扩容机制，每次扩容会增大到 1.5 倍
- 元素可以为 null

- 线程不安全。在多线程情况下，请使用 Collections.synchronizedList 方法把 ArrayList 包装为线程安全版本，或直接使用古老的 Vector

---

参考资料：

[Java 集合深入理解之 AbstractList —— CSDN 拭心](https://blog.csdn.net/u011240877/article/details/52834074)

[Java 集合深入理解之 ArrayList —— CSDN 拭心](https://blog.csdn.net/u011240877/article/details/52853989)

[ArrayList 源码解析 —— JavaGuide](https://snailclimb.gitee.io/javaguide/#/docs/java/collection/ArrayList)

[ArrayList 详细介绍 —— skywang12345](https://www.cnblogs.com/skywang12345/p/3308556.html)

[《吊打面试官》系列 - ArrayList —— 敖丙](https://juejin.im/post/5e14b51d5188253a9a213e83)

ArrayList 源码分析

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

idea 激活码2020

Typecho搭建个人博客教程

SpringCloud服务健康监控

Mybatis居然可以连接 ClickHouse?

SpringCloud Nacos 配置中心

IDEA激活码2020-更新2020.10.27

SpringSecurity+OAuth2实现单点登录SSO

SpringCloud War 包部署导致服务未正常注册到 Nacos 问题

SpringBoot整合Redis

SpringCloud服务健康监控

ArrayList 源码分析

Leave a Comment Cancel reply 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

ArrayList 源码分析

Leave a Comment Cancel reply
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款