您的位置: 首页  >  文章  >  Java源码分析之ArrayList

Java源码分析之ArrayList

分类: 文章 • 2024-04-16 20:21:55

Java源码分析之ArrayList

文章目录

前言

本文内容来自Java ArrayList的API文档，ArrayList源码大概1600多行，其中700多行是各种List操作的实现，其余为RandomAccess、Serializable以及其它祖宗接口的实现代码，其中ArrayList的继承结构如下：
Java源码分析之ArrayList

ArrayList简介

ArrayList是什么

ArrayList是Java提供的一种类似Vector的集合类，但是它是非同步的（个人是很不喜欢这种解释方式的，因为还要去了解Vector是什么，很麻烦的，虽然比喻往往是最容易让人理解的一种方式），支持泛型；它继承自AbstractList，实现了List、RandomAccess、Cloneable、Serializable等接口；

ArrayList是一种实现了所有列表操作并且可以改变大小的数组；它可以包含所有的元素，包括空元素Null；ArrayList内部使用数组存储元素，并且提供了操作该数组容量的方法以实现List接口；

常见方法的时间复杂度概述

size、isEmpty、get、set以及iterator方法的时间复杂度是常数级的；平摊下来的话，add方法所需要的时间也是常数级的——这意味着，插入n个元素的平均时间是O(n)；以上这些方法都可以在线性时间里完成，并且线性因子要比LinkedList（下一篇分析它~）的小；

动态增长概述

每一个ArrayList有一个capacity变量，这个变量是ArrayList内部所使用的数组的长度，它不小于其size变量的值；当元素被添加到ArrayList的时候，capacity会自动增长；

应用程序可以在添加大量元素到ArrayList中之前使用ensureCapacity方法，这样可以减少动态增长的次数；

实际上，ArrayList的自动扩容只发生在add以及ensureCapacity函数中，也就是说在构造ArrayList的时候，并不会做扩容——一些面试题总是会考察这一点，但并不知道有什么意义。

非同步性

还有就是ArrayList被设计为非同步的，所以如果多线程并发访问同一个ArrayList实例，并且至少有一个线程可能会结构性修改list，那么就必须提供外部的同步机制；

所谓结构性修改ArrayList是指添加或者删除一个或者多个元素，或者明确改变内部数组的大小；仅仅设置元素的值并不算是改变了list的结构；

处理ArrayList并发访问的常见做法是对访问ArrayList的对象做同步处理；如果没有这样的对象，ArrayList对象应该使用Collections.synchronizedList进行包装，该动作最好在创建的时候就完成，以避免意外地对该List进行了非同步的访问；

ArrayList使用modCount这一整数变量来跟踪结构性修改的次数；

遍历器

通过iterator方法返回的ArrayList的遍历器方法是快速失效的：在遍历器被创造之后，如果ArrayList被除遍历器自身的remove、add方法之外的方法结构性修改，那么遍历器将抛出异常。所以，对于并发修改，遍历器干净利落地快速失效，而不是在未来某个不确定的时间面对危险的、不确定的行为；

需要注意的是，遍历器快速失效的行为在并发的非同步的修改中不能得到任何硬性保证，遍历器会尽最大的努力抛出异常，但是应用程序不能依赖该异常去保证程序的正确性，该行为只适合于发现Bug。

ArrayList详解

如何存储元素

默认容量

ArrayList内部定义了一个DEFAULT_CAPACITY静态变量，其值为10，该变量在ensureCapacity、newCapacity等方法中被使用，它们是和ArrayList动态扩容相关的两个方法，后面会详解；

/**
 * Default initial capacity.
 */
private static final int DEFAULT_CAPACITY = 10;

最大容量

ArrayList中最多能存储Integer.MaxValue-8个元素，因为一些虚拟机会在数组中保存一些头字段。试图分配更大的数组将导致抛出异常。

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

存储数组

ArrayList有两个默认的空的数组对象：EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA；

private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

EMPTY_ELEMENTDATA是所有空的ArrayList实例对象共享的存储数组；DEFAULTCAPACITY_EMPTY_ELEMENTDATA是所有使用默认大小作为数组容量的实例对象共享的存储数组，ArrayList通过它来和EMPTY_ELEMENTDATA做区别，以便知道当第一个元素被添加到List中的时候，该如何扩展；

而elementData则是ArrayList实际存储元素的数组，如果elementData==DEFAULTCAPACITY_EMPTY_ELEMENTDATA的话，第一个元素被插入ArrayList的时候，其容量（capacity）将被扩展为默认值，10；

size变量指示ArrayList中存储的元素数量；capacity变量指示内部数组elemenData的大小；

构造函数

ArrayList提供三种构造函数，其签名如下：

public ArrayList(int initialCapacity)；
public ArrayList() ；
public ArrayList(Collection<? extends E> c)；

第一种传递初始化容量的构造函数的实现如下：

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

可以看到，如果初始化容量大于0，那么elementData被创建，然后什么都没有干，没有扩容~~~之所以总是考察构造函数中的扩容问题，我想是要和HashMap的构造函数做区别吧。如果初始化容量等于0，那么elementData被赋值为EMPTY_ELEMENTDATA，也就是主动申明容量为0。注意，这里不是DEFAULTCAPACTIY_EMPTY_ELEMENTDATA哦就像前面提到的，这里的区别将在第一次插入元素的时候展现出来（欲知详情，请看下文分解~）

第二种默认构造函数的实现如下：

public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

也就是说，如果不提供初始化容量或者初始化容量为0，elementData实际上都是空的，并没有申请内存空间；

第三种通过实现Collection接口的类来创造一个ArrayList，其实现如下：

public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

这里涉及到Collection接口定义的toArray()方法，因为elementData被赋值为该方法的返回结果，现在还不需要详细了解该方法，但是我们可以知道的是如果实现该接口的类对使用遍历器以返回元素的顺序有要求时，toArray方法返回的对象数组中元素的顺序是符合该要求的；

另外，我们还可以看到，该构造方法对返回的结果做了一次检查，如果返回的结果不是对象数组，就会使用Arrays.copyOf这个方法来构造elementData。当然，如果对象数组的长度为0，elementData则被赋值为EMPTY_ELEMENTDATA；

当然，这里我们还需要了解Arrays.copyOf这个方法，目前我们需要知道的是，它是一种创建对象数组的方法即可；以后会再次深入理解其实现，毕竟这里的主角是ArrayList；

容量函数

trimToSize

首先，ArrayList提供了trimToSize方法以将其内部数组容量缩减为所包含元素的数量，其实现如下：

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

这里再一次出现Arrays.copyOf这个方法~

ensureCapacity

该方法接受一个最小容量参数，函数的结果是内部数组的容量大小不小于该参数，前面也提到，在插入大量元素之前，可以使用该方法扩容，从而避免插入过程中的频繁扩容，接下来我们将看到扩容的真正面目；其实现如下：

public void ensureCapacity(int minCapacity) {
    if (minCapacity > elementData.length
        && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
             && minCapacity <= DEFAULT_CAPACITY)) {
        modCount++;
        grow(minCapacity);
    }
}

扩容的判断条件可以视为两部分：一是minCapacit要大于当前内部数组的长度，这个好理解，否则就没有扩容的必要，第二部分是elementData不是拥有默认容量的对象数组或者elementData是拥有默认容量的空对象数组，但是所需要的容量大于默认容量。只有这两个条件都为真，才会发生扩容；而实际的扩容是在grow函数中完成的；

我们目前看到的是，在默认构造函数里，elementData被赋值为DEFAULTCAPACITY_EMPTY_ELEMENTDATA，但实际上，ArrayList在一定条件下也会将elementData修改为此默认值，而且我们很快就会看到这个方法~

另外，对于逻辑表达式，虽然最后可能会找到等价的表示方法，但是不同的表示的确有不同的含义，我上面的解释是将代码中的否运算分配到括号里的结果，是从“什么时候要扩容”这一角度去看问题；而源代码则是从“什么时候不扩容”这一角度去看问题，然后将这些情况否定，从而殊途同归；

grow

grow函数有两种实现：含参和不含参。其中不含参的形式默认扩展1位；其实现如下：

private Object[] grow(int minCapacity) {
    return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}
private Object[] grow() {
    return grow(size + 1);
}

又见Arrays.copyOf函数！但是也有新面孔：newCapacity。

newCapacity

该函数可以说是ArrayList动态扩容规则的核心了，因为它决定了新容量的大小~

private int newCapacity(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity <= 0) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return minCapacity;
    }
    return (newCapacity - MAX_ARRAY_SIZE <= 0)
        ? newCapacity
        : hugeCapacity(minCapacity);
}

首先会将容量扩展为原来容量的1.5倍得到一个新的容量，如果该容量大于需求的最小容量，那么内部数组的容量将被扩展为新容量；但是，如果新容量小于所要求的最小容量，并且elementData为默认大小的空对象数组，则会返回默认大小和最小容量的较大值；因为，如果初始化为默认容量，此时elementData.length==0，则新容量仍然为0；这种情况下，自然需要返回两者的最大值；

另外，对于newCapacity可能会超出MAX_ARRAY_SIZE这一情况，ArrayList提供了hugeCapacity这一方法；

hugeCapacity

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

函数还是比较规范吧，后面会分析一些具体的情况，以彻底理解这一系列的函数调用路径；

索引函数

ArrayList提供了indexOf系列函数，用以判断某个对象是否在list里面，基本实现是for循环，因为ArrayList中的元素可以为空，而针对空对象，使用==判断，其他则使用equals判断，实现如下：

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

另外，至于lastIndexOf，则是从后往前遍历数组啦，这里不给出实现了~

操作函数

这里的操作函数是指对ArrayList进行查找、插入以及删除等操作的函数。

toArray

该函数有两种重载形式，一种是含参的，会将list中的元素输出到给定的数组中，如果a有足够的空间容纳元素，否则会创建新的a类型的数组；

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;
}
public Object[] toArray() {
    return Arrays.copyOf(elementData, size);
}

关于该函数，需要注意的是，它仍然使用到了我们的老朋友：Arrays.copyOf函数来创造一个新的数组，另外，还用到了System.arraycopy这一函数，实际上，Arrays.copyOf函数内部也是使用了该函数~不过这是后话；

还有一点就是返回数组中，使用null标记了数据的末尾，所以，最好还是不要向list中插入null，这样可能在判断元素末尾的时候出现一些问题；

set And get

public E set(int index, E element) {
    Objects.checkIndex(index, size);
    E oldValue = elementData(index);
    elementData[index] = element;
    return oldValue;
}
public E get(int index) {
    Objects.checkIndex(index, size);
    return elementData(index);
}

常规方法~只是Objects.checkIndex(index,size)会做范围检查；

add

private void add(E e, Object[] elementData, int s) {
    if (s == elementData.length)
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}//默认添加到末尾
public void add(int index, E element) {
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    System.arraycopy(elementData, index,
                     elementData, index + 1,
                     s - index);
    elementData[index] = element;
    size = s + 1;
 }

这里就要划重点了因为出现了grow()而grow将调用grow(size+1)；于是就发生了动态扩容~

然后就是，对外公布的第一个add方法实际上调用了另外一个私有方法，在公有方法里对modCount进行维护；在私有方法里实现动态增长等功能；

在指定插入位置的add方法里，仍然是先判断是否越界，然后判断是否需要扩容，之后使用System.arraycopy函数进行元素的移动；

在set和get方法里，我们使用Objects.checkIndex方法检查是否越界，这里使用rangeCheckForAdd方法，实现也比较简单：

private void rangeCheckForAdd(int index) {
    if (index > size || index < 0)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
    return "Index: "+index+", Size: "+size;
}

removeAll And retainAll

这两个方法接收一个实现了Collection接口的参数c，第一个函数将从list中删去c中存在的元素；第二个函数将从list中删去不在c中的元素；

一个有趣的技巧是这两个函数依赖于同一个函数；

public boolean removeAll(Collection<?> c) {
    return batchRemove(c, false, 0, size);
}
public boolean retainAll(Collection<?> c) {
    return batchRemove(c, true, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement,
                    final int from, final int end) {
    Objects.requireNonNull(c);
    final Object[] es = elementData;
    int r;
    // Optimize for initial run of survivors
    for (r = from;; r++) {
        if (r == end)
            return false;
        if (c.contains(es[r]) != complement)
            break;
    }
    int w = r++;
    try {
        for (Object e; r < end; r++)
            if (c.contains(e = es[r]) == complement)
                es[w++] = e;
    } catch (Throwable ex) {
        // Preserve behavioral compatibility with AbstractCollection,
        // even if c.contains() throws.
        System.arraycopy(es, r, es, w, end - r);
        w += end - r;
        throw ex;
    } finally {
        modCount += end - w;
        shiftTailOverGap(es, w, end);
    }
    return true;
}

另外，这两个函数返回的boolean值表示该函数调用是否对list内部进行了修改；而其底层依赖的函数也值得考究分析~

首先，该函数从下标为from开始，寻找第一个被删去的元素，如果没找到则返回false，表示该操作没有修改list结构；

否则，通过w记录此时的r，并且将r自增，开始下一轮寻找，如果遇到需要保留的元素，则移动该元素到w指示的位置；w实际上指示了from到to这一子序列中保留下来的最后一个元素的位置+1；之后，因为删除了一些数据，并且再删除的过程中移动了区间的数据，故在w和to以后的数据间形成了一个“无人区”，最后通过shiftTailOverGap()函数移动尾部元素；其函数实现如下：

private void shiftTailOverGap(Object[] es, int lo, int hi) {
    System.arraycopy(es, hi, es, lo, size - hi);
    for (int to = size, i = (size -= hi - lo); i < to; i++)
        es[i] = null;
}

这里出现了我们熟悉的朋友：System.arraycopy函数，没错，这是系统提供的一种相对高效的移动数组元素的方法；我们这里不做详细了解，虽然也不是很难，只不过我们会在"Arrays"这一主题里在详细探讨~

后记

到这里，ArrayList作为List这一角色的内容就全部完毕了，这里并没有涉及其对其他接口的实现细节，不是不重要，而是因为不是我们的关注点~

关于ArrayList最常见的问题就是动态扩容了，可是又有什么难度呢？论技巧，我觉得batchRemove更有趣一些可是。。。没有办法啊最后附一张ArrayList从创建到插入的流程图，方便理解动态扩容这一主题吧~
Java源码分析之ArrayList
Java源码分析之ArrayList

相关推荐