美文网首页
ArrayList源码分析

ArrayList源码分析

作者: yaco | 来源:发表于2020-06-06 08:11 被阅读0次

1 ArrayList的成员变量

首先来看一下源码

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

    /**
     * Shared empty array instance used for empty instances.
     */
    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;

这里列举五个典型的成员方法

  • DEFAULT_CAPACITY 属性：此属性创建空参ArrayList的默认数组长度
  • EMPTY_ELEMENTDATA 属性：默认长度为0的空数组
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA 属性：初始化默认长度为10所获得的数组
  • elementData 属性： 这个属性就是我们用来存放数据的底层数组了
  • size 属性： 用于记录当前添加的元素的个数。

2 ArrayList的构造方法

继续看一下源码

    /**
     * 带初始容量参数的构造函数。（用户自己指定容量）
     *
     * @param  initialCapacity  指定初始容量
     * @throws IllegalArgumentException 如果给定的参数是负数，则会抛出IllegalArgumentException
     */
    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);
        }
    }

    /**
     * 默认构造函数，使用初始容量10构造一个空列表(无参数构造)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    /**
     * 构造包含指定collection元素的列表，这些元素利用该集合的迭代器按顺序返回
     *
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException 如果指定的集合为null，throws NullPointerException。 
     */
    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;
        }
    }

可以看到ArrayList默认有三种构造方法：

2.1 带初始容量参数的构造函数

这个构造方法很直观，主要就是根据用户自定义的初始容量大小，给elementData赋予指定长度的数组。

  • 如果给定的初始容量大于0，则直接给elementData new 一个指定长度的Object[]数组即可。

  • 如果给定的初始容量等于0，则将成员变量EMPTY_ELEMENTDATA赋给elementData

  • 如果给定的初始容量小于0，则会抛出异常

2.2 默认无参构造函数

这个构造方法直接将成员变量DEFAULTCAPACITY_EMPTY_ELEMENTDATA赋给elementData即可，值得注意的是，初始化的DEFAULTCAPACITY_EMPTY_ELEMENTDATA为0，只有当添加一个新的元素的时候，才会常见一个长度为10的数组，此方法也称为懒加载机制。

我们可以从下面的代码看出：

// add添加元素的方法
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

// 确保当前的容量
private void ensureCapacityInternal(int minCapacity) {
    // 如果这时第一次添加元素，判断一下当前的数组是不是我们默认无参构造方法创建的
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}

// 确保数组达到指定的容量
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;   // 此元素表示对数组改动次数

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);    // 如果数组没有达到指定容量，那么就要进行扩容了
}

// 真正的扩容在这里
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;   // 如果是第一次添加元素，那么这里就是0
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    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);   // 扩容操作
}

2.3 构造包含指定collection元素的列表

  • 首先会用到一个方法将参数c转化称为数组
  • 如果转化后的数组长度为0，表示初始化的集合为null，则直接将成员变量EMPTY_ELEMENTDATA赋给elementData
  • 如果输入的集合长度不为0，那么剩下的就是将传入的集合对象编程我们设定的对象。

3 ArrayList的扩容机制

在上一节已经介绍过了空参构造方法初始化一个长度为10的数组的详细过程，那么这里再来简单说一下ArrayList的扩容机制。

3.1 从add()方法说起

/**
* 将指定的元素追加到此列表的末尾。 
*/
public boolean add(E e) {
    //添加元素之前，先调用ensureCapacityInternal方法
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    //这里看到ArrayList添加元素的实质就相当于为数组赋值
    elementData[size++] = e;
    return true;
}
  • add一个新的元素的时候，首先会调用一个ensureCapacityInternal(size + 1)方法，他的主要目的就是查看当前新加入一个元素之后，我们的数组是否可以放下了，放不下就扩容，扩容之后再进行添加。
  • 在ensureCapacityInternal(size + 1)方法之后，就是简单的数组添加元素的操作了，这里size指针需要做自增操作
  • add方法有返回值，添加成功则返回true

3.2 ensureCapacityInternal() 方法

//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 获取默认的容量和传入参数的较大值
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }

    ensureExplicitCapacity(minCapacity);
}
  • 可以看到这里方法有一个参数minCapacity,他表示当前数组如果要添加一个新的元素，所需要的最小的容量。
  • 然后会进入一个判断语句，查看当前数组是不是无参构造方法得来的，这步直接体现了ArrayList的懒加载机制，只有当添加元素的时候，才会进行初始化长度为10的数组。
  • 确定了minCapacity的值之后，进入ensureExplicitCapacity()方法，这步主要就是确保数组可以容纳我们所需要的minCapacity

3.3 ensureExplicitCapacity() 方法

//判断是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        //调用grow方法进行扩容，调用此方法代表已经开始扩容了
        grow(minCapacity);
}
  • 首先modCount自增我们可以不看
  • 然后进入一个判断语句，查看当前的数组是否满足我们所需要的最小容量 minCapacity
  • 如果不满足最小容量，则会进行grow()方法进行扩容。
  • 这里举个例子，假设当前的数组长度为默认的10，则添加第1、2、3、4、5、6、7、8、9、10 个元素均不会出发grow（）方法，只有当我们添加第11个元素的时候，出发grow() 方法。

3.4 grow() 方法

/**
* 要分配的最大数组大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

/**
* ArrayList扩容的核心方法。
*/
private void grow(int minCapacity) {
    // oldCapacity为旧容量，newCapacity为新容量
    int oldCapacity = elementData.length;
    //将oldCapacity 右移一位，其效果相当于oldCapacity /2，
    //我们知道位运算的速度远远快于整除运算，整句运算式的结果就是将新容量更新为旧容量的1.5倍，
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    //然后检查新容量是否大于最小需要容量，若还是小于最小需要容量，那么就把最小需要容量当作数组的新容量，
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // 如果新容量大于 MAX_ARRAY_SIZE,进入(执行) `hugeCapacity()` 方法来比较 minCapacity 和 MAX_ARRAY_SIZE，
    //如果minCapacity大于最大容量，则新容量则为`Integer.MAX_VALUE`，否则，新容量大小则为 MAX_ARRAY_SIZE 即为 `Integer.MAX_VALUE - 8`。
    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);
}

真正的扩容出现在这里

  • 首先会确定当前数组的实际长度
  • 然后将当前的数组的长度扩大1.5倍 int newCapacity = oldCapacity + (oldCapacity >> 1);
  • 如果扩大的新数组的量还不满足我们的最小容量的时候，直接扩成最小容量，这步也只有在添加第一个元素，初始化长度为10的默认数组的时候才会发生。
  • 另外如果翻了1.5倍之后长度大于了MAX_ARRAY_SIZE之后，会进入hugeCapacity(minCapacity)方法，确认一下最终要扩大的长度
  • 最后就是使用了Arrays.copyOf()方法进行扩容。

3.5 hugeCapacity(）方法

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    //对minCapacity和MAX_ARRAY_SIZE进行比较
    //若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
    //若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
    //MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}
  • 这里如果minCapacity < 0只有一种可能性，就是储存的元素超过的Int的最大值，产生了溢出。
  • 如果超出了系统的MAX_ARRAY_SIZE,则扩成Integer.MAX_VALUE,否则扩成MAX_ARRAY_SIZE

4 两种复制数组的方式

ArrayList在扩容的时候用到了Arrays.copyOf(elementData, newCapacity)方法，那么还有一个类似的复制数组的方法System.arraycopy(), 他们之间有什么区别和联系尼？

4.1 简单的数组扩容方法 Array.copyof() 方法

    /**
     * Copies the specified array, truncating or padding with zeros (if necessary)
     * so the copy has the specified length.  For all indices that are
     * valid in both the original array and the copy, the two arrays will
     * contain identical values.  For any indices that are valid in the
     * copy but not the original, the copy will contain <tt>0</tt>.
     * Such indices will exist if and only if the specified length
     * is greater than that of the original array.
     *
     * @param original the array to be copied
     * @param newLength the length of the copy to be returned
     * @return a copy of the original array, truncated or padded with zeros
     *     to obtain the specified length
     * @throws NegativeArraySizeException if <tt>newLength</tt> is negative
     * @throws NullPointerException if <tt>original</tt> is null
     * @since 1.6
     */
public static int[] copyOf(int[] original, int newLength) {
    int[] copy = new int[newLength];
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

以上是官方源码，我简单翻译一下它的意思

  • 复制指定的数组，截断或用零填充（如果需要）,所以复制需要有指定的长度。
  • 对于在原始数组和复制数组中都有效的所有索引，这两个数组将包含相同的值。
  • 对于在复制数组中有效但是原数组中无效的所有索引，其位置都用0来补充。
  • 这样的0只有在复制的数组的长度大于原有的数组长度时才会产生

参数的含义

  • original 原数组，数组类型，这里我只截了int[] 类型的复制
  • newLength 返回的复制数组的长度

简单来说，Arrays.copyOf()方法主要是为了给原有数组扩容，测试代码如下：

public class ArrayscopyOfTest {

    public static void main(String[] args) {
        int[] a = new int[3];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        int[] b = Arrays.copyOf(a, 10);
        System.out.println("b.length"+b.length);
    }
}

测试结果为10

4.2 最底层的数组扩容方法System.arraycopy() 方法

这里我称此方法为最底层的数组扩容方法因为可以看到，Array.copyof()方法内部也调用了此处的System.arraycopy() 的方法。

再来看一下源码

/* @param      src      the source array.
    * @param      srcPos   starting position in the source array.
    * @param      dest     the destination array.
    * @param      destPos  starting position in the destination data.
    * @param      length   the number of array elements to be copied.
    * @exception  IndexOutOfBoundsException  if copying would cause access of data           * outside array bounds.
    * @exception  ArrayStoreException  if an element in the <code>src</code>
    * array could not be stored into the <code>dest</code> array because of a type           * mismatch.
    * @exception  NullPointerException if either <code>src</code> or <code>dest</code> is     * <code>null</code>.
    */
public static native void arraycopy(Object src,  int  srcPos, Object dest, int destPos, int length);

这里是个native方法，我们直接分析一下它的参数

  • src : 原数组
  • srcPos ：从原数组复制的起始索引
  • dest ：目标数组
  • destPos ： 目标数组的起始索引
  • length ： 要复制的数组长度

根据这几个参数，我们在来分析一个Arrays.coptof()方法中的引用就异常的简单的了

    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));

可以来出，这个方法就是将original数组复制到copy中去，然后original从索引0开始复制，copy数组从索引0开始接收，复制长度就是newLength.

这里在举一个简单的测试类，出自https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

public class ArraycopyTest {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] a = new int[10];
        a[0] = 0;
        a[1] = 1;
        a[2] = 2;
        a[3] = 3;
        System.arraycopy(a, 2, a, 3, 3);
        a[2]=99;
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }

}

结果如下：

0 1 99 2 3 0 0 0 0 0

4.3 两者联系和区别

联系：

看两者源代码可以发现 Arrays.copyOf() 内部实际调用了 System.arraycopy() 方法

区别：

  • 一个有返回值，一个没有返回值

  • arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组。

5 ArrayList降低多次扩容效率问题的解决方法

从上面的源码分析简单总结一下ArrayList的扩容机制，这里假设不带参数的空参构造方法

  • 首先添加第一个元素，将数组扩容成10；

  • 添加第11个元素，将数组扩容成15；

  • 添加第16个元素，将数组扩容成22；

  • 添加第23个元素，将数组扩容成33；

  • 不停的添加元素，就会不停分扩容

问题分析：

从这里可以看出，在我们添加元素较多的情况下，ArrayList的扩容操作会经常发生，每一次扩容都会带来一次Arrays.copyof()的操作，必会带来大量的时间消耗。

解决方案：

ArrayList类中提供了一个ensureCapacity方法，可以用来估算我们所需要的容量，提前一次性的将数组扩充好，避免多次扩容。

/**
如有必要，增加此 ArrayList 实例的容量，以确保它至少可以容纳由minimum capacity参数指定的元素数。
*
* @param   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);
    }
}

相关文章

网友评论

      本文标题：ArrayList源码分析

      本文链接：https://www.haomeiwen.com/subject/qhaazhtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|ArrayList源码分析|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！