登录 注册

Java 源码之旅——ArrayList

本贴最后更新于 1858 天前，其中的信息可能已经渤澥桑田

先看一眼关系图，有个大概印象。

image.png

ArrayList 整体架构比较简单，底层实现就是一个数组。

建议打开 ArrayList 源码，对照着看。本文仅解析部分核心代码，并未涉及到 ArrayList 的所有代码。

[TOC]

关键类变量

/**
* Default initial capacity.
* 默认初始容量为10，这个值得记住
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* ArrayList中实际负责存储的数组对象
* transient修饰代表该字段不参与序列化
*/
transient Object[] elementData;

/**
* The size of the ArrayList (the number of elements it contains).
* 表示当前数组的大小，类型int,没有使用volatile 修饰，非线程安全的
*/
private int size;

/**
* 统计当前数组被修改的版本次数，数组结构有变动，就会+1
* 定义在AbstractList中
*/
protected transient int modCount = 0;

构造方法

ArrayList 有三个构造方法，分别是无参数直接初始化、指定大小初始化、指定初始数据初始化。

无参数直接初始化

private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

这个没什么好说的，赋值了一个空数组。

指定大小初始化

private static final Object[] EMPTY_ELEMENTDATA = {};

public ArrayList(int initialCapacity) {
  if (initialCapacity > 0) {
    this.elementData = new Object[initialCapacity];
  } else if (initialCapacity == 0) {
    this.elementData = EMPTY_ELEMENTDATA;
  } else {
    throw new IllegalArgumentException("Illegal Capacity: "+
                                       initialCapacity);
  }
}

指定初始数据初始化

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

当给定的集合长度为 0 的时候，初始化为空数组。

当集合长度不为 0 时，如果集合元素类型不是 Object 类型，会转成 Object。这里会有一点问题，ArrayList 初始化之后（ArrayList 元素非 Object 类型），再次调用 toArray 方法，得到 Object 数组，并且往 Object 数组赋值时，会触发此 bug，导致 ArrayStoreException。这一点已经在 Java 9 中被修复。

新增和扩容

从上面我们能看到，ArrayList 真正存储数据的地方其实是 elementData，而 elementData 是一个数组，数组的长度是固定的。当数组装满之后还要再往 ArrayList 中添加元素的时候，就需要进行扩容操作。

所以往数组中新增元素，主要分为两步：

  • 判断是否需要扩容，如果需要，执行扩容操作；
  • 赋值

代码

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 static int calculateCapacity(Object[] elementData, int minCapacity) {
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
    return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

private void ensureExplicitCapacity(int minCapacity) {
  modCount++;	// 每进行一次操作，版本号就会加1

  // overflow-conscious code
  // 如果我们期望的最小容量大于目前数组的长度，那么就扩容
  if (minCapacity - elementData.length > 0)
    // 扩容
    grow(minCapacity);
}

添加这一块，ArrayList 实际上是花了绝大部分精力在扩容上面，在进行真正的扩容操作（grow）之前，已经计算出了需要扩充到的容量。

// 扩容，并把现有数据拷贝到新的数组里面去
private void grow(int minCapacity) {
  // overflow-conscious code
  int oldCapacity = elementData.length;
  // oldCapacity >> 1 是把 oldCapacity 除以 2 的意思
  int newCapacity = oldCapacity + (oldCapacity >> 1);
  // 如果扩容后的值 < 我们的期望值，扩容后的值就等于我们的期望值
  if (newCapacity - minCapacity < 0)
    newCapacity = minCapacity;
  // 如果扩容后的值 > jvm 所能分配的数组的最大值，那么就用 Integer 的最大值
  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);
}

private static int hugeCapacity(int minCapacity) {
  if (minCapacity < 0) // overflow
    throw new OutOfMemoryError();
  return (minCapacity > MAX_ARRAY_SIZE) ?
    Integer.MAX_VALUE :
  MAX_ARRAY_SIZE;
}

MAX_ARRAY_SIZE

/**
* 要分配的数组的最大大小。
* 一些虚拟机在数组中保留一些标题字。
* 尝试分配更大的数组可能会导致
* OutOfMemoryError: Requested array size exceeds VM limit
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

扩容本质 Arrays.copyOf

Arrays.copyOf(elementData, newCapacity);

newCapacity 是我们期望的新数组容量，该行代码会新建一个容量为 newCapacity 的数组，然后将原数组的数据填充到新数组，最后返回这个新数组。该方法底层通过 System.arraycopy 方法进行拷贝，此方法是 native 的方法，源码如下：

/**
 * @param src     被拷贝的数组
 * @param srcPos  从数组那里开始
 * @param dest    目标数组
 * @param destPos 从目标数组那个索引位置开始拷贝
 * @param length  拷贝的长度 
 * 此方法是没有返回值的，通过 dest 的引用进行传值
 */
public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

添加元素到指定索引位置

public void add(int index, E element) {
  // 检查索引合法性
  rangeCheckForAdd(index);

  ensureCapacityInternal(size + 1);  // Increments modCount!!
  System.arraycopy(elementData, index, elementData, index + 1,
                   size - index);
  elementData[index] = element;
  size++;
}

private void rangeCheckForAdd(int index) {
  if (index > size || index < 0)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

流程就是进行扩容检查，该扩容就扩容，之后使用刚刚讲到的 native 方法 System.arraycopy 将原数组中处于 index 位置与之后的所有元素向后移动一格，最后把需要新增的元素放到 index 就好了，非常的简单。

小结

新增的话还有 addAll(Collection<? extends E> c) 等方法，大同小异，有兴趣的朋友可以自行查看。

扩容里面需要注意的几点：

  • 扩容的规则并不是翻倍，是原来容量大小 + 容量大小的一半，直白来说，扩容后的大小是原来容量的 1.5 倍；
  • ArrayList 中的数组的最大值是 Integer.MAX_VALUE，超过这个值，JVM 就不会给数组分配内存空间了。
  • 新增时，并没有对值进行严格的校验，所以 ArrayList 是允许 null 值的。
  • 溢出意识，源码中已经在相应位置标明了 overflow-conscious code。就是说扩容后数组的大小下界不能小于 0，上界不能大于 Integer 的最大值，这种意识我们可以学习。

删除

ArrayList 删除元素有很多种方式，比如根据数组索引删除、根据值删除或批量删除等等，原理和思路都差不多，这里选取根据值删除方式来进行源码解读。

删除这一块我从源码里面没看出来哪里缩容了，1.8 以后 ArrayList 删除操作不缩容了？希望有大佬可以赐教。

代码

public boolean remove(Object o) {
  // 如果要删除的值是 null，找到第一个值是 null 的删除
  if (o == 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++)
      // 这里是根据  equals 来判断值相等的，相等后再根据索引位置进行删除
      if (o.equals(elementData[index])) {
        fastRemove(index);
        return true;
      }
  }
  return false;
}

/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
  modCount++;
  // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去
  // 减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起
  int numMoved = size - index - 1;
  if (numMoved > 0)
    System.arraycopy(elementData, index+1, elementData, index,
                     numMoved);
  elementData[--size] = null; // clear to let GC do its work
}

移除操作通过 fastRemove 实现，该方法借助 native 方法，将 index+1 位置及其后面的元素，依次赋值给前一格。然后将位于 --size 的元素置空，方便 GC。

小结

  • 新增的时候是没有对 null 进行校验的，所以删除的时候也是允许删除 null 值
  • 判断元素是否相等，是通过 equals 来判断的，如果数组元素不是基本类型，需要我们关注 equals 的具体实现。

迭代器

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

这里的 Itr 是 ArrayList 的内部类，该内部类实现了 java.util.Iterator 接口。

Itr 类有如下几个成员变量

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// expectedModCount 表示迭代过程中，期望的版本号；modCount 表示数组实际的版本号。
int expectedModCount = modCount;

迭代器一般来说有四个方法：

  • hasNext 用来判断是否还有值可以迭代
  • next 如果有值可以迭代，迭代的值是多少
  • remove 删除当前迭代的值
  • forEachRemaining 1.8 新增，能够将 Iterator 中迭代剩余的元素传递给一个函数

hasNext

public boolean hasNext() {
  return cursor != size;//cursor 表示下一个元素的位置，size 表示实际大小，如果两者相等，说明已经没有元素可以迭代了，如果不等，说明还可以迭代
}

next

public E next() {
  //迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
  checkForComodification();
  //本次迭代过程中，元素的索引位置
  int i = cursor;
  if (i >= size)
    throw new NoSuchElementException();
  Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length)
    throw new ConcurrentModificationException();
  // 下一次迭代时，元素的位置，为下一次迭代做准备
  cursor = i + 1;
  // 返回元素值
  return (E) elementData[lastRet = i];
}
// 版本号比较
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

next 方法就干了两件事情，第一是检验能不能继续迭代，第二是找到迭代的值，并为下一次迭代做准备（cursor+1）。

remove

public void remove() {
  // 如果上一次操作时，数组的位置已经小于 0 了，说明数组已经被删除完了
  if (lastRet < 0)
    throw new IllegalStateException();
  //迭代过程中，判断版本号有无被修改，有被修改，抛 ConcurrentModificationException 异常
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    // -1 表示元素已经被删除，这里也防止重复删除
    lastRet = -1;
    // 删除元素时 modCount 的值已经发生变化，在此赋值给 expectedModCount
    // 这样下次迭代时，两者的值是一致的了
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

forEachRemaining

public void forEachRemaining(Consumer<? super E> consumer) {
  Objects.requireNonNull(consumer);
  final int size = ArrayList.this.size;
  int i = cursor;
  if (i >= size) {
    return;
  }
  final Object[] elementData = ArrayList.this.elementData;
  if (i >= elementData.length) {
    throw new ConcurrentModificationException();
  }
  while (i != size && modCount == expectedModCount) {
    consumer.accept((E) elementData[i++]);
  }
  // update once at end of iteration to reduce heap write traffic
  // 在迭代结束时更新一次，以减少堆写入流量
  cursor = i;
  lastRet = i - 1;
  checkForComodification();
}

小结

  • lastRet = -1 的操作目的，是防止重复删除操作
  • 删除元素成功，数组当前 modCount 就会发生变化，这里会把 expectedModCount 重新赋值，下次迭代时两者的值就会一致了

时间复杂度

新增（不考虑扩容）

对于新增操作，如果是 add(E e) 方法，那么新元素会被直接添加到数组末尾，时间复杂度为 O(1)；但是 add(int, E) 会需要对 index 后的元素作遍历移动操作，所以时间复杂度为 O(n)。

删除（没找到缩容相关代码）

同样的，从数组尾部删除为 O(1)，从任意索引位置删除为 O(n)。

查找

通过索引 get，时间复杂度为 O(1)；查找元素是否存在，时间复杂度为 O(n)。

线程安全问题

只有当 ArrayList 作为共享变量时，才会有线程安全问题，当 ArrayList 是方法内的局部变量时，没有线程安全问题。

ArrayList 有线程安全问题的本质，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况。

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3190 引用 • 8214 回帖 • 1 关注
  • 代码
    467 引用 • 586 回帖 • 9 关注
上海 位置
1 关注
1 回帖
388 12 60 50 61 27 45 121

相关帖子

1 回帖
Java 源码之旅——ArrayList

欢迎来到这里！

我们正在构建一个小众社区，大家在这里相互信任，以平等 • 自由 • 奔放的价值观进行分享交流。最终，希望大家能够找到与自己志同道合的伙伴，共同成长。

注册 关于
请输入回帖内容 ...
  • wizardforcel •

    这不是我们数据结构课的作业嘛？

lonelyant
念念不忘，必有回响 上海
回帖
2
 帖子
10
 积分
710