ArrayList源码解析

小管
源码

发布于：Apr 21, 2021
次浏览

3k words

13 min
0  

ArrayList的特性

ArrayList内部使用数组作为存储结构,ArrayList可以理解为数组的扩展对象,封装了常用和非常用的操作数组的方法.以及当数组长度不足时,自动扩容数组.ArrayList的特点如下:

  • 根据索引查询数据的时间复杂度为O(1);
  • 在数组中间部分根据索引写入或删除元素效率低;
  • 写入数组时若数组长度不足则会出发扩容;
  • ArrayList允许保存NULL值;
  • ArrayList是非线程安全的设计;

源码

重要成员变量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//ArrayList默认的容量长度
private static final int DEFAULT_CAPACITY = 10;

//定义一个空数组对象
private static final Object[] EMPTY_ELEMENTDATA = {};

//当ArrayList中没有任何对象时，使用该变量赋值，是一个默认的缺省空数组对象
//用于无参构造函数为elementData赋值，或判断数组是否是缺省值
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

//ArrayList中真正保存数据的数组
transient Object[] elementData; // non-private to simplify nested class access


//数组中保存的对象的个数
private int size;
  • elementData:ArrayList中真正储存数据的对象,也证明ArrayList内部是由数组实现的;
  • DEFAULT_CAPACITY:它表示数组在一般情况下,初次扩容的长度;

ArrayList默认初始化的长度并不是0;

构造函数

无参构造函数

1
2
3
4
5
public ArrayList() {
  // 用缺省的DEFAULTCAPACITY_EMPTY_ELEMENTDATA来赋值给elementData数组
  // 变量定义：static final DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

这说明通过ArrayList list = new ArrayList()创建一个ArrayList时，初始化长度是0，而不是10。

根据指定容量创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// initialCapacity是new ArrayList(5)时传递的指定容量
public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    // 根据initialCapacity实例化elementData对象
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    // 如果传进来的是0，那么则用EMPTY_ELEMENTDATA初始化，这里要跟DEFAULTCAPACITY_EMPTY_ELEMENTDATA做好区分
    // 变量定义：static final EMPTY_ELEMENTDATA = {}
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  }
}

根据其他类型集合来初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// Collection是多种集合（List,Set,Queue）的的顶级接口
// 也就是说，实现Collection接口的对象都可以用来初始化ArrayList
public ArrayList(Collection<? extends E> c) {
  elementData = c.toArray();
  if ((size = elementData.length) != 0) {
    // c.toArray might (incorrectly) not return Object[] (see 6260652)
    // 调用Arrays.copyOf为elementData赋值
    if (elementData.getClass() != Object[].class)
      elementData = Arrays.copyOf(elementData, size, Object[].class);
  } else {
    // 如果参数长度为0，则用EMPTY_ELEMENTDATA赋值elementData
    this.elementData = EMPTY_ELEMENTDATA;
  }
}

数组扩容

主动扩容

1
2
3
4
5
6
7
8
public void ensureCapacity(int minCapacity) {
  // 获取最小的扩容长度，0或者10
  int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
  // 当主动扩容传入的参数大于最小扩容长度时进行扩容，否则不进行扩容
  if (minCapacity > minExpand) {
    ensureExplicitCapacity(minCapacity);
  }
}

上述代码为主动扩容,可以通过list.ensureCapacity(参数)由使用者进行主动扩容.

因为扩容涉及到数组的拷贝,所以源码中加入了判断,当要扩容的长度小于最小扩容长度,则不进行扩容.

自动扩容

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
private void ensureCapacityInternal(int minCapacity) {
  // 先调用calculateCapacity方法，获取要扩容的长度
  // 后调用ensureExplicitCapacity方法，进行扩容
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

private static int calculateCapacity(Object[] elementData, int minCapacity) {
  // 如果数组是初始化数组，则取DEFAULT_CAPACITY和minCapacity中较大的数作为扩容长度
  // 也就是说，初始化数组的长度是0，如果第一次添加对象，那么minCapacity将是1，数组会扩容到10
  // 所以可以认为，数组初始化是0，当添加第一个对象时，扩容到10
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  // 记录数组的修改次数，这个变量在AbstractList类中，是ArrayList的父类
  modCount++;

  // 确认是否进行扩容，也就是说数组elementData的长度不足以存放对象了
  // 调用grow进行真正的扩容
  if (minCapacity - elementData.length > 0)
    grow(minCapacity);
}

// elementData的最大长度
// 是一个Integer的最大值-8的长度
// 之所以减8是因为一些虚拟机对数组的实现，需要用减掉的这个8来保存一些头信息
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
  // 获取旧的容量
  int oldCapacity = elementData.length;
  // 将容量扩大1.5倍, >>1效率更高
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 做一些逻辑判断，若要扩容的长度小于最小扩容长度，也就是比传入的参数小，则扩容长度取传入的参数
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  // 若要扩容的长度大于Integer.MAX -8,这种极端形况下调用hugeCapacity进行处理
  if (newCapacity - MAX_ARRAY_SIZE > 0)
    newCapacity = hugeCapacity(minCapacity);
  // 扩容！调用Arrays.copyOf方法
  elementData = Arrays.copyOf(elementData, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
  // 如果minCapacity等于负数，有可能是内存溢出了，则抛出OOM异常
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  // 否则如果确实是大于了Integer.MAX - 8，但在Integer.MAX内，则返回Integer.MAX
  // 但能否扩容成功，要根据JVM虚拟机的实现来看了
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}
  • 自动扩容为原数组长度的1.5倍,用>>1效率更高;
  • 扩容的最大长度,理想状态下应该是Integer.MAX-8的长度,以为一些JVM实现数组需要保存头信息,会占用数组的长度;
  • 当极端情况下超过了Integer.MAX-8,则扩容到Integer.MAX;

常用方法

get方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public E get(int index) {
  // 检测索引是否越界
  rangeCheck(index);
  // 从数组中找到数据并返回，时间复杂度的O(1)
  return elementData(index);
}

private void rangeCheck(int index) {
  // 检测索引是否越界，如果越界则抛出异常
  if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

private String outOfBoundsMsg(int index) {
  return "Index: "+index+", Size: "+size;
}

E elementData(int index) {
  // 返回数组中制定索引的数据
  return (E) elementData[index];
}

get方法的时间复杂度为$\mathrm O(1)$

set方法

1
2
3
4
5
6
7
8
public E set(int index, E element) {
        // 检测索引越界
        rangeCheck(index);
        // 获取索引对应的值，将索引位置的值设置成element，然后返回旧值，时间复杂度是O(1)
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

set方法的时间复杂度为$\mathrm O(1)$

add方法

1
2
3
4
5
6
7
8
9
10
11
public boolean add(E e) {
  // 将ArrayList长度+1，然后调用内部扩容函数
  // 若数组还有空间则不会进行扩容
  ensureCapacityInternal(size + 1);
  // 保存到数组最后面
  elementData[size++] = e;
  return true;
}

if (minCapacity - elementData.length > 0)
    grow(minCapacity);

如果elementData.length的长度小于minCapacity(也就是size+1),那么会将数组扩容1.5倍.

不触发扩容的情况下add(E e)的时间复杂度是O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public void add(int index, E element) {
  // 判断索引是否越界
  rangeCheckForAdd(index);
  // 触发扩容
  ensureCapacityInternal(size + 1);
  // 将index位置后的元素统一向后移动
  System.arraycopy(elementData, index, elementData, index + 1,
                   size - index);
  // 将数组保存到索引位置，并将长度+1
  elementData[index] = element;
  size++;
}

private void rangeCheckForAdd(int index) {
  // 索引不能大于ArrayList的size，并且不能小于0
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

调用add(int index, E element)效率并不高，每次add一个元素，都要移动该元素后面的所有元素。最坏的情况下时间复杂度是O(n)

remove方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public E remove(int index) {
  // 检查索引越界
  rangeCheck(index);
  // 记录修改次数
  modCount++;
  // 获取要被删除的元素，准备在方法结束时返回给调用者
  E oldValue = elementData(index);
  // 这里做了一个判断，如果删除的不是最后一个元素，则需要将index后的元素向前移动
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  // 将最后一个元素位置置为null，便于GC回收
  elementData[--size] = null; // clear to let GC do its work
  return oldValue;
}

与add(int index, E element)类似，如果从中间删除时，数组会将index后的元素统一向前移动。

从数组中间位置删除元素效率低的原因就在于此，最坏的情况下时间复杂度是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public boolean remove(Object o) {
  if (o == null) {
    // 如果对象是null，则找到第一个null元素的索引，并从数组中删除，查找方式是从前到后
    for (int index = 0; index < size; index++)
      if (elementData[index] == null) {
        fastRemove(index);
        return true;
      }
  } else {
    // 如果对象不是null，则找到对象的索引，从数组中删除，查找方式也是从前到后
    for (int index = 0; index < size; index++)
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

private void fastRemove(int index) {
  // 记录数组操作次数
  modCount++;
  // 如果删除的元素不在数组尾部，则需要向前移动数组
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  // 最后以为元素设置为null，便于GC回收
  elementData[--size] = null; // clear to let GC do its work
}

remove(Object o)的做法是先循环找到o对应的index，然后跟remove(int index)执行差不多逻辑，将index后面的数据向前移动。

remove(Object o)，从前向后查找元素，并将后面的元素向前移动，所以它的时间复杂度是是O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public boolean removeAll(Collection<?> c) {
  // c不能为null
  Objects.requireNonNull(c);
  // 核心方法在这里，传入false代表删除elementData和c中重复的元素
  return batchRemove(c, false);
}

public boolean retainAll(Collection<?> c) {
  // c不能为null
  Objects.requireNonNull(c);
  // 核心方法在这里，传入true代表保留elementData和c中重复的元素，删除不通的元素，可以理解为取交集
  return batchRemove(c, true);
}

private boolean batchRemove(Collection<?> c, boolean complement) {
  final Object[] elementData = this.elementData;
  int r = 0, w = 0;
  boolean modified = false;
  // 使用try-finally结构，支持快速失败
  try {
    // 将两个数组中重复的元素，被后一个元素前移，替换掉
    for (; r < size; r++)
      if (c.contains(elementData[r]) == complement)
        elementData[w++] = elementData[r];
  } finally {
    // 删除数组尾部无用的元素
    if (r != size) {
      System.arraycopy(elementData, r,
                       elementData, w,
                       size - r);
      w += size - r;
    }
    if (w != size) {
      // clear to let GC do its work
      for (int i = w; i < size; i++)
        elementData[i] = null;
      modCount += size - w;
      size = w;
      modified = true;
    }
  }
  return modified;
}
  • removeAll方法是用来删除两个数组中都存在的数据；
  • retainAll方法是用来删除两个数组中不一致的数据；

核心方法是batchRemove方法中，确保时间复杂度的一个不确定因素是c.contains方法，如果该方法的时间复杂度是O(1)，那么整个batchRemove的时间复杂度将会是O(n)。

其他方法

1
2
3
4
5
6
7
public int size() {
  return size;
}

public boolean isEmpty() {
  return size == 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
}

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

indexOf和lastIndexOf的时间复杂度都是O(n)

1
2
3
4
public boolean contains(Object o) {
  // 调用indexOf来判断是否存在
  return indexOf(o) >= 0;
}

这里就验证了batchRemove方法中c.contains会确定该方法的时间复杂度的说法。如果removeAll传入的参数也是一个ArrayList，那么removeAll方法是时间复杂度将会是$\mathrm O(\mathrm n\hat{}2)$

trimToSize

1
2
3
4
5
6
7
8
9
public void trimToSize() {
  modCount++;
  // 如果elementData的长度大于ArrayList的size，则说明有剩余空间，可以进行裁剪
  if (size < elementData.length) {
    elementData = (size == 0)
      ? EMPTY_ELEMENTDATA
      : Arrays.copyOf(elementData, size);
  }
}

虽然ArrayList没有自动缩容的功能,但提供了方法,可以让使用者主动调用,进行空间的释放.

总结

  • ArrayList内部是由数组实现的；
  • ArrayList在创建时候可以指定数组容量；
  • ArrayList的get和set方法的时间复杂度是O(1)，添加元素到尾部的时间复杂度是O(1)；
  • ArrayList内部数组容量不足时会自动扩容，扩容比例是1.5倍；
  • ArrayList从数组中间删除或添加元素性能不高；

所以，ArrayList的适用与顺序添加元素到数组中，并可以通过索引检索数据的场景，如果可以确定元素个数还可以减少扩容次数。

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gleaming.cn/ArrayList-source-code/

更新于：Jul 28, 2022

评论




Blog content follows the Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0) License

载入天数...载入时分秒... Use Volantis as theme

Copyright © 2019-2022 XXX

鲁ICP备20003069号