ArrayList扩容原理

ArrayList扩容原理ArrayList扩容原理今天带来的下饭菜是ArrayList的扩容源码解读。相信大家对这盘菜都不陌生,我们经常使用它来定义一个集合,无论日常开发还是自己学习使用的频率是相当的高。而且大家也都一定知道ArrayList集合是通过数组实现的,但是在声明一组数据的时候都会选择ArrayList而不是数组,原因就是由于这组数据的元素的数量不确定,如果使用数组的话,我们还得亲自维护数组的长度,这时你一定会说TMD烦死了;但如果使用了ArrayList,维护数组长度的事情就不用我们操心了,我们只需要对这组数据进

大家好,又见面了,我是你们的朋友全栈君。

今天带来的下饭菜是ArrayList的扩容源码解读。

相信大家对这盘菜都不陌生,我们经常使用它来定义一个集合,无论日常开发还是自己学习使用的频率是相当的高。

而且大家也都一定知道ArrayList集合是通过数组实现的,但是在声明一组数据的时候都会选择ArrayList而不是数组,原因就是由于这组数据的元素的数量不确定,如果使用数组的话,我们还得亲自维护数组的长度,这时你一定会说TMD烦死了;但如果使用了ArrayList,维护数组长度的事情就不用我们操心了,我们只需要对这组数据进行增、删、改、查即可,ArrayList会自动对内部的数组进行扩容,这时你又会说:郑(zhen)爽(shuang),那么ArrayList是怎么做到自动扩容的呢?今天就通过阅读源码带大家一起探讨一下这个问题。

自动扩容涉及的方法 - 思维导图

1、字段属性一览

先看一下ArrayList内部给我们定义了哪些属性,再看扩容的方法就不会很累

/** * 忽略,ArrayList实现了Serializable接口,支持序列化, * 声明这个属性是给jvm使用的 */
private static final long serialVersionUID = 8683452581122892189L;

// 初始化默认容量为10
private static final int DEFAULT_CAPACITY = 10;

// 一个空的对象数组,

private static final Object[] EMPTY_ELEMENTDATA = { 
   };

/** * 一个空的对象数组, * 从命名来看是默认长度的空数组, * 因此我们就认为这个数组长度为10 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = { 
   };

/** * 一个数组对象, * ArrayList底层是通过数组实现的,说的就是这个 * 我们对ArrayList的增删改查其实j就是对这个数组的增删改查 * transient关键字说明在序列化的时候忽略这个字段,与本文无关,不做过多解释 */
transient Object[] elementData;

/** * ArrayList的大小,指的是ArrayList中元素的个数, * 注意:与ArrayList的容量作区分,容量指的是elementData的长度 */
private int size;

2、锁定扩容方法

如果你找不到扩容的方法是哪一个,你可以想一下,什么时候能触发扩容,那必定是在添加元素的时候,容量不够了,所以才要扩容啊,因此我们找一下添加元素的方法

// 在末尾添加一个元素
public boolean add(E e) { 
   
    //size+1表示要添加这个元素,ArrayList的大小就成了size+1
    ensureCapacityInternal(size + 1);
    //element放在数组的最后一个位置,arrayList的元素数量加一
    elementData[size++] = e;
    // ...
}
//在指定位置添加一个元素
public void add(int index, E element) { 
   
    rangeCheckForAdd(index);
    //size+1表示要添加这个元素,ArrayList的容量至少为size+1
    ensureCapacityInternal(size + 1); 
    // element放在数组的最后一个位置
    elementData[index] = element;
    //arrayList的元素数量加一
    size++;
}
//在末尾添加一个集合
public boolean addAll(Collection<? extends E> c) { 
   
    Object[] a = c.toArray();
    int numNew = a.length;
    //size+numNew表示要添加这个集合,ArrayList的容量至少为size+numNew
    ensureCapacityInternal(size + numNew); 
    //...
    //arrayList的元素数量 + c的元素数量
    size += numNew;
    // ...
}
//在指定位置添加一个集合
public boolean addAll(int index, Collection<? extends E> c) { 
   
    rangeCheckForAdd(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    //size+numNew表示要添加这个集合,ArrayList的容量至少为size+numNew
    ensureCapacityInternal(size + numNew);    //...
    //arrayList的元素数量 + c的元素数量
    size += numNew;
    // ...
}

可以看到,添加元素的方法有这么四个,每个方法都会调用一次跟容量相关的方法:ensureCapacityInternal(翻译:内部确定容量),并将当前size+numNew(要添加的元素的数量)作为参数传给此方法。

3、查看ensureCapacityInternal方法,


// minCapacity表示ArrayList至少需要容量的大小
private void ensureCapacityInternal(int minCapacity) { 
   
  // 确定明确的容量 
  ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

在确定明确的容量之前,我们得先调用calculateCapacity方法计算一下当前ArrayList的容量要扩展到多大,因为前面说过,ArrayList的默认容量就已经是10了,如果你现在只需要1的容量,那当然就不需要扩容了对吧。

4、查看calculateCapacity方法

private static int calculateCapacity(Object[] elementData, int minCapacity) { 
   
  // 如果底层数组是默认容量的空数组,那就在默认容量和指定容量中取一个最大值,
  // 当然这就意味着 如果底层数组是默认容量空数组,就保证了我要扩至少为10的容量
  if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
   
      return Math.max(DEFAULT_CAPACITY, minCapacity);
  }
  return minCapacity;
}

如果底层数组是默认容量的空数组,那就在默认容量和指定容量中取一个最大值,当然这就意味着 如果底层数组是默认容量空数组,就保证了要扩展至少为10的容量。
如果底层数组不是默认容量的空数组,那么指定的容量作为计算结果返回,意思就是ArrayList要将容量扩展到minCapacity

5、查看ensureExplicitCapacity方法


private void ensureExplicitCapacity(int minCapacity) { 
   
  // 因为要修改底层数组的结构,将修改次数加一,与扩容无关
  modCount++;

  // overflow-conscious code
  if (minCapacity - elementData.length > 0)
      grow(minCapacity);
}

这里明白人都能看得出来,扩容的逻辑就在grow方法里面了,但扩容的前提是指定的容量必须大于底层数组的长度(即当前容量),因为如果当前容量为15,而指定的容量为12,那当然是不需要扩容的。

6、查看grow方法

private void grow(int minCapacity) { 
   
    // overflow-conscious code
    int oldCapacity = elementData.length;
    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);
}

看到这里才确定了最终扩展后的容量,
首先获取当前容量oldCapacity,将当前容量的二进制数右移1位后再转为十进制(你可以用笔算一下,其实就是当前容量的1.5倍)就是扩展后的容量即新的容量简称新容量(newCapacity)。
如果新容量比指定的容量小,那就将指定容量作为新容量,否则新容量就是当前容量的1.5倍。
如果新容量比最大数组容量(MAX_ARRAY_SIZE,即2的31次方-9)还要大,就需要通过hugeCapacity方法进一步确定新容量了,否则新容量依然是当前容量的1.5倍

6.1、查看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;
}

如果指定容量小于0,就抛一个内存溢出异常;

如果指定容量大于最大数组容量(MAX_ARRAY_SIZE,即2的31次方-9),就返回最大的整数2的31次方减一,否则就返回最大数组容量。

:最大整数为2的31次方-1,最大数组容量为最大整数-8

在ArrayList类中可以看到这样的常量定义

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

为什么最大数组容量要比最大整数相差为8呢?

注释是这么说的:一些VM在数组中保留一些标题字。尝试分配更大的数组可能会导致OutOfMemoryError:请求的数组大小超过VM限制。

看到这里我不禁感叹,太细节了。

6.2、再回到grow方法,查看调用hugeCapacity方法这一行

if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);

如果新容量比最大数组容量(MAX_ARRAY_SIZE,即2的31次方-9)还要大,
而且指定容量minCapacity比最大数组容量大,那么就将最大整数作为新容量;
但如果指定容量minCapacity0和最大数组容量之间,那么就将最大数组容量作为新容量。
我认为这一步的判断是个细节,关于当数组长度到达天花板时长度该如何分配的问题,但很多资料中并未提及。

最终确定好新容量后,就执行
elementData = Arrays.copyOf(elementData, newCapacity);
将底层数组elementData新容量作为参数传给copyOf方法,并以底层数组elementData作为方法的执行结果。那么我们来看接下来是怎么改变底层数组elementData的长度的。

7、查看Arrays.copyOf(elementData, newCapacity)方法

public static <T> T[] copyOf(T[] original, int newLength) { 
   
  return (T[]) copyOf(original, newLength, original.getClass());
}

这个方法就是创建一个类型相同,长度为newLength的数组,并将其返回。
可以看到,Arrays.copyOf(elementData, newCapacity)方法调用了他的重载方法
(T[]) copyOf(original, newLength, original.getClass())

8、查看copyOf(original, newLength, original.getClass())方法

public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) { 
   
    @SuppressWarnings("unchecked")
    T[] copy = ((Object)newType == (Object)Object[].class)
        ? (T[]) new Object[newLength]
        : (T[]) Array.newInstance(newType.getComponentType(), newLength);
    System.arraycopy(original, 0, copy, 0,
                     Math.min(original.length, newLength));
    return copy;
}

这个方法就是根据原数组original返回一个类型为newType,长度为newLength的数组
这个方法参数有点多,所以首先一点要清楚调用该方法时传入的参数是什么:
U[] original 原数组 :底层数组elementData,数组类型为泛型U的数组
int newLength 新数组的长度 :新容量newCapacity
Class<? extends T[]> newType 新数组的类型 :底层数组elementData的类型

其实就是先判断新数组和Object[]是否类型相同
如果相同,就直接定义一个长度为newLengthObject数组T[]
如果不相同,就通过Array.newInstance创建一个长度为newLength、元素类型为T数组T[]
反正就是定义了一个新的长度为newLength的**空数组T[]**呗。

接着调用了System.arraycopy方法,我们再看看他干了些什么

9、查看System.arraycopy方法

public static native void arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length);

大家发现了吗?此方法有一个关键字native,说明该方法是本地方法,并不存在于jdk中,而是JVM提供的使用C语言编写的方法实现,调用native方法就是调用jvm内部的C语言方法,这里不过多讲解,点到为止,如有兴趣,自行百度。

该方法就是从源数组src的第srcPos个位置起,将每个元素依次复制到目的数组dest的第destPos个位置上,复制元素的数量为length

结合代码逻辑我们可以梳理一下:
copyOf(original, newLength, original.getClass())方法中,定义了一个长度为新容量newCapacity、类型为源数组类型数组T[]
再调用System.arraycopy方法,从第0个元素开始,将底层数组elementData中的元素依次复制到新数组T[]中,而且被复制元素的个数=底层数组elementData的元素数量,最后再把新数组T[]返回,并且让底层数组elementData指向此新数组T[]。

以后再通过ArrayList对其元素进行增、删、改、查操作时,底层所操作的数组就是这个新的数组T[]。
接下来就是对ArrayList中的元素数量size进行操作了,回到第二节可以看出,新增单个元素时,size将自增,新增一个集合时,size=size+新增集合的元素个数

通过源码解读,ArrayList的扩容原理你应该明白了吧。


ensureCapacityInternalensureCapacity的区别

不知道小伙伴们在查看源码的时候有没有注意到,其实ArrayList给我们提供了两个扩展容量的方法:

// 第一种
private void ensureCapacityInternal(int minCapacity) { 
   
  ensureExplicitCapacity(calculateCapacity(elementData, 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);
  }
}

这两种方法都是用来扩展容量的,他们之间的区别也是显而易见的。

第一种方法名称翻译过来就是内部确定容量,而且他的访问修饰符是private,也就是说这个方法只能在当前类内部进行调用。

第二种方法名称翻译过来就是确定容量,他的访问修饰符是public,也就是说我们可以在任何地方对ArrayList进行直接扩容。
而且此方法做了更详细的判断,如果我们在声明ArrayList对象的时候指定了他的初始容量,那么扩容后的容量就是我们传入的参数;如果没有指定他的初始容量,那么扩容后的容量至少为10。

总结

1、自动扩容的新容量的大小是原容量的1.5倍
2、一般来讲扩容后的最大容量为最大数组长度,即最大整数-8
3、若ArrayList中元素的数量大于最大数组长度,则扩容后的容量为最大整数
4、扩容将会产生一个新的长度更大的数组
5、我们可以通过直接调用ensureCapacity方法,手动对ArrayList进行扩容。且扩容后的容量至少为10

如果小伙伴感兴趣,不妨打开微信关注公众号,点关注-不迷路
在这里插入图片描述

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136382.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • windows Tasklist命令详解

    windows Tasklist命令详解“Tasklist”命令是一个用来显示运行在本地或远程计算机上的所有进程的命令行工具,带有多个执行参数。作用:结束一个或多个任务或进程。可以根据进程ID或图像名来结束进程。语法格式:TASKLIST[/Ssystem[/Uusername[/P[password]]]][/M[module]|/SVC|/V][/FIfilter][/FOformat][/NH]参数列表:/Ssystem指定连接…

  • 8 款免费的 MySQL 数据库建模工具

    数据库建模和设计是软件开发过程中必不可少的步骤,一个良好的建模工具可以帮助我们简单快速地完成数据库设计,提高工作的效率。因此,今天给大家推荐几款免费的MySQL数据库建模工具,包括MySQLWorkbench、SQLPowerArchitect、PDMan、RISE、GenMyModel、DBDesigner、dbdiagram.io、Freedgo。

  • Python绘制旭日图_sunburst图如何做

    Python绘制旭日图_sunburst图如何做python绘制旭日图

  • CSS3 transition 渐变特效

    CSS3 transition 渐变特效transition的使用需要和hover搭配使用transition:属性持续的时间(s)ease-in/ease(曲线规律)多少秒后开始(s)transition:all持续时间(s)//简易写法<!DOCTYPEhtml><htmllang=”en”><head> <metacharset=”UTF-8″> <title>Document</title> <style> d

  • matlab画圆的命令_matlab画圆命令.doc[通俗易懂]

    matlab画圆的命令_matlab画圆命令.doc[通俗易懂]matlab画圆命令.doc%%圆环面R=6;r=2;symsuv;ezmesh((R+r*cos(u))*cos(v),(R+r*cos(u))*sin(v),r*sin(u));axisequal;%%圆盘R=6;r=2;theta=linspace(0,2*pi,90);ph=linspace(r,R,30);[t,p]=meshgrid(theta,ph);r=t*0;[x,y,z]=p…

  • redis客户端

    redis客户端

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号