八股文之浅谈ArrayList扩容机制篇(jdk1.8)

迷南。 2024-03-30 13:12 138阅读 0赞

目录

前言：

1.ArrayList属性介绍

2.ArrayList三个构造器

3.ArrayList扩容机制

3.1 add(E e)方法

3.2 ensureCapacity方法

4.System.arraycopy() 与 Arrays.copyOf()

前言：

本文主要介绍ArrayList的扩容机制，详细说明底层在什么时候实现扩容的、是如何实现扩容的，篇幅较长，耐心看完哦~~

1.ArrayList属性介绍

默认的容量大小

  1. /**
  2.  * Default initial capacity.
  3.  */
  4. private static final int DEFAULT_CAPACITY = 10;

这个是数组变量，用来表示一个数组为空，由于被final修饰，所以指向是不可以改变的。它起到一个标识的作用，用于判断数组是否为空；

  1. /**
  2.  * Shared empty array instance used for empty instances.
  3.  */
  4. private static final Object[] EMPTY_ELEMENTDATA = {};

与它起到相似作用的是：

  1. /**
  2.  * Shared empty array instance used for default sized empty instances. We
  3.  * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
  4.  * first element is added.
  5.  */
  6. private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

它们两个都是指向了空数组，但是所代表的意义不一样

  • EMPTY_ELEMENTDATA 代表的意义：是表示一个数组本质为空，原生长度就是为0
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA代表的意义是：一个数组虽然为空，但是能被扩容，未来的长度可以改变

（具体可以阅读官方注释）

用于存储数据的数组

  1. /**
  2.  * The array buffer into which the elements of the ArrayList are stored.
  3.  * The capacity of the ArrayList is the length of this array buffer. Any
  4.  * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
  5.  * will be expanded to DEFAULT_CAPACITY when the first element is added.
  6.  */
  7. transient Object[] elementData;

2.ArrayList三个构造器

API文档：

a269360ceddb43f689b48e4de1594026.png

❀ ArrayList()

  1. /**
  2. * Constructs an empty list with an initial capacity of ten.
  3. */
  4. public ArrayList() {
  5.     this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
  6. }

在无参构造器中，elementData的初始化指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA 而不是EMPTY_ELEMENTDATA，所以在这里也能看出这两个变量的代表意义是不一样的。

❀ArrayList(int initalCapacity)

  1. /**
  2.  * Constructs an empty list with the specified initial capacity.
  3.  *
  4.  * @param  initialCapacity  the initial capacity of the list
  5.  * @throws IllegalArgumentException if the specified initial capacity
  6.  *         is negative
  7.  */
  8. public ArrayList(int initialCapacity) {
  9.     if (initialCapacity > 0) {
  10.         this.elementData = new Object[initialCapacity];
  11.     } else if (initialCapacity == 0) {
  12.         this.elementData = EMPTY_ELEMENTDATA;
  13.     } else {
  14.         throw new IllegalArgumentException("Illegal Capacity: "+
  15.                                                initialCapacity);
  16.     }
  17. }

这个带参比无参稍微复杂一点，参数的意义是初始化容量大小 ，

内部判断执行任务：

  • 参数 > 0，会将elementData初始化为参数指定的容量大小
  • 参数==0，会将elementData初始化为EMPTY_ELEMENTDATA（参数为0，说明为数组原生长度为0，为空数组，符合EMPTY_ELEMENTDATA的定义）
  • 假如输入的参数不合法，报出异常
  1. ❀**ArrayList(Collection<? extends E> c)**
  3. /**
  4. * Constructs a list containing the elements of the specified
  5. * collection, in the order they are returned by the collection's
  6. * iterator.
  7. *
  8. * @param c the collection whose elements are to be placed into this list
  9. * @throws NullPointerException if the specified collection is null
  10. */
  11. public ArrayList(Collection<? extends E> c) {
  12.     Object[] a = c.toArray();
  13.     if ((size = a.length) != 0) {
  14.         if (c.getClass() == ArrayList.class) {
  15.              elementData = a;
  16.         } else {
  17.              elementData = Arrays.copyOf(a, size, Object[].class);
  18.         }
  19.     } else {
  20.         // replace with empty array.
  21.         elementData = EMPTY_ELEMENTDATA;
  22.     }
  23. }

这个构造器是用于将集合类转化为ArrayList ，例如：LinkekList转化为ArrayList

内部判断执行任务:

  • 先获取到【c】的数组形式【a】，

  • a.length != 0

    • c.getClass == ArrayList.class，【a】引用交付给elementData，
    • c.getClass != ArrayList.class，Arrays.sort对a进行拷贝操作,返回拷贝后的数组引用

  • a.length == 0

    • 说明原来的Collection 长度就为0，符合EMPTY_ELEMENT的定义，element=EMPTY_ELEMENTDATA

3.ArrayList扩容机制

3.1 add(E e)方法

  1. /**
  2.  * Appends the specified element to the end of this list.
  3.  *
  4.  * @param e element to be appended to this list
  5.  * @return <tt>true</tt> (as specified by {@link Collection#add})
  6.  */
  7. public boolean add(E e) {
  8.    ensureCapacityInternal(size + 1);  // Increments modCount!!
  9.    elementData[size++] = e;
  10.    return true;
  11. }

在add方法内部，他会调用一个叫做 ensureCapacityInternal的方法，我们来看看这个方法内部细节：

  1. private void ensureCapacityInternal(int minCapacity) {
  2.     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
  3. }

然后发现他又调用到了 calculateCapacity和ensureExplicitCapacity两个不同的方法，我们在来看内部实现代码：

  1. private static int calculateCapacity(Object[] elementData, int minCapacity) {
  2.         if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
  3.             return Math.max(DEFAULT_CAPACITY, minCapacity);
  4.         }
  5.         return minCapacity;
  6.     }
  8. private void ensureExplicitCapacity(int minCapacity) {
  9.         modCount++;
  11.         // overflow-conscious code
  12.         if (minCapacity - elementData.length > 0)
  13.             grow(minCapacity);
  14.     }

内部又再次调用grow方法，这个grow方法才是真正的扩容方法，内部代码如下：

  1. private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
  3.     /**
  4.      * Increases the capacity to ensure that it can hold at least the
  5.      * number of elements specified by the minimum capacity argument.
  6.      *
  7.      * @param minCapacity the desired minimum capacity
  8.      */
  9.     private void grow(int minCapacity) {
  10.         // overflow-conscious code
  11.         int oldCapacity = elementData.length;
  12.         int newCapacity = oldCapacity + (oldCapacity >> 1);
  13.         if (newCapacity - minCapacity < 0)
  14.             newCapacity = minCapacity;
  15.         if (newCapacity - MAX_ARRAY_SIZE > 0)
  16.             newCapacity = hugeCapacity(minCapacity);
  17.         // minCapacity is usually close to size, so this is a win:
  18.         elementData = Arrays.copyOf(elementData, newCapacity);
  19.     }
  21.     private static int hugeCapacity(int minCapacity) {
  22.         if (minCapacity < 0) // overflow
  23.             throw new OutOfMemoryError();
  24.         return (minCapacity > MAX_ARRAY_SIZE) ?
  25.             Integer.MAX_VALUE :
  26.             MAX_ARRAY_SIZE;
  27.     }

由此可见，简单的add方法是通过层层调用才最终实现扩容的，接下来我们具体分析一下，每一层的调用都发送了说明事情！！！大致流程如下：

4e75034a3b0943528fd13aac80439544.png

简要流程概述：在进入add方法后，会先执行ensureCapacityInternal方法检查elementData数组是否还有容量，这个方法为计算这个容量去调用calculateCapacity方法，将计算后的值交给ensureExplicitCapacity来判断当前容量需不需要扩容，假如需要扩容着会调用grow 函数，然后grow函数会执行相关的扩容操作，最后执行回到，add方法中，此时不管elementData数组有没有被扩容，结果都是add都能顺利将数据添加到elementData数组中。

细节流程概述：由上面代码我们可以看到ensureCapacityInternal的第二给参数便是容量大小，而add传的便是size+1，所以这个时候，ensureCapacityInternal要做的就算，计算返回容量最大的那个值，假如此时elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，那么就把默认的DEFAULT_CAPACITY返回就好，这也是为什么有说法：无参初始化为0，而只有在add的时候才初始化为10大小的数组。假如elementData不为空了，那么就直接返回minCapacity实际上这个值等于size+1，然后来到ensureExplicitCapacity，在这个方法拿到minCapacity的值后，就拿这个值和element的实际长度来想减（minCapacity - elementData.length），假如值小于0，说明还有容量，不用扩容，直接添加元素即可，假如值大于0，说明容量不够大需要扩容，继而调用grow方法

  1. int oldCapacity = elementData.length;
  2. int newCapacity = oldCapacity + (oldCapacity >> 1);

由上面的代码可以看出，在grow方法内部扩容的大小：为之前的1.5倍

  1. if (newCapacity - minCapacity < 0){
  2.       newCapacity = minCapacity;
  3. }
  4. //等价于
  5. //Math.max(newCapacity,minCapacity)

之后便将newCapticity拿到最大值

  1. if (newCapacity - MAX_ARRAY_SIZE > 0){
  2.       newCapacity = hugeCapacity(minCapacity);
  3. }

之后又判断这个值是否大于数组的最大容量也就是整型数据的最大值-8（Integer.MAX_VALUE-8），至于为什么-8，注释中没有详细说明，但是问题不大的，在hugeCapcity方法中，会返回最合适的那个值

  1. return (minCapacity > MAX_ARRAY_SIZE) ?Integer.MAX_VALUE : MAX_ARRAY_SIZE;

到这里，grow方法就结束了，然后就回到add方法中，执行添加元素操作！！！

以上就i是add方法中的扩容机制，其他的add方法也是如此，大同小异感兴趣的可以自去分析操作一下

3.2 ensureCapacity方法

比较贴心的是，官方提供了一个方法来给我们手动扩容（扩容流程参考上面介绍）

  1. /**
  2.      * Increases the capacity of this <tt>ArrayList</tt> instance, if
  3.      * necessary, to ensure that it can hold at least the number of elements
  4.      * specified by the minimum capacity argument.
  5.      *
  6.      * @param   minCapacity   the desired minimum capacity
  7.      */
  8.     public void ensureCapacity(int minCapacity) {
  9.         int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
  10.             // any size if not default element table
  11.             ? 0
  12.             // larger than default for default empty table. It's already
  13.             // supposed to be at default size.
  14.             : DEFAULT_CAPACITY;
  16.         if (minCapacity > minExpand) {
  17.             ensureExplicitCapacity(minCapacity);
  18.         }
  19.     }

所以为了避免扩容高频发生，在我们事先指定大小的时候，可以提前扩容到指定大小，然后进行添加操作，这样就导致扩容只发生了一次，性能得到了提升

4.System.arraycopy() 与 Arrays.copyOf()

System.arraycopy()

  1. * @param      src      the source array.
  2.      * @param      srcPos   starting position in the source array.
  3.      * @param      dest     the destination array.
  4.      * @param      destPos  starting position in the destination data.
  5.      * @param      length   the number of array elements to be copied.
  6.      * @exception  IndexOutOfBoundsException  if copying would cause
  7.      *               access of data outside array bounds.
  8.      * @exception  ArrayStoreException  if an element in the <code>src</code>
  9.      *               array could not be stored into the <code>dest</code> array
  10.      *               because of a type mismatch.
  11.      * @exception  NullPointerException if either <code>src</code> or
  12.      *               <code>dest</code> is <code>null</code>.
  13.      */
  14. public static native void arraycopy(Object src,  int  srcPos,
  15.                                         Object dest, int destPos,
  16.                                         int length);

Arrays.copyOf()

  1. @param original the array to be copied
  2.      * @param newLength the length of the copy to be returned
  3.      * @return a copy of the original array, truncated or padded with zeros
  4.      *     to obtain the specified length
  5. public static <T> T[] copyOf(T[] original, int newLength)

两个方法在ArrayList出现都挺频繁的，前者是系统调用的拷贝，后者是用户代码调用的拷贝，

前者将源数据拷贝到指定数组中，可以指定源数组开始拷贝为位置和目标数组开始拷贝位置和拷贝长度，后者将拷贝original数组中指定长度的内容到一个数组中，将这个数组返回

以上是个人对ArrayList扩容机制的拙见

感谢阅读owo

发表评论

表情：
评论列表 （有 0 条评论，138人围观）

还没有评论，来说两句吧...

相关阅读

    相关 ArrayList扩容机制

    ArrayList简介： ArrayList实现了List接口它是一个可调整大小的数组可以用来存放各种形式的数据。并提供了包括CRUD在内的多种方法可以对数据进行操作但是

    桃扇骨桃扇骨/ 0 赞/ 82 阅读