Java集合之ArrayList扩容机制

Java集合之ArrayList扩容机制ArrayList的构造函数//默认初始容量大小(默认能添加10条数据)privatestaticfinalintDEFAULT_CAPACITY=10;//默认实例化一个空数组privatestaticfinalObject[]DEFAULTCAPACITY_EMPTY_ELEMENTDATA={};//默认构造函数,使用初始容量为10构造一个空列表(无参数构造…

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

ArrayList的构造函数

//默认初始容量大小(默认能添加10条数据)
private static final int DEFAULT_CAPACITY = 10;
//默认实例化一个空数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//默认构造函数,使用初始容量为10构造一个空列表(无参数构造)
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_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);
        }
    }    
//构造包含指定collection元素的列表,这些元素利用该集合的迭代器按照顺序返回,如果指定的集合为空,则抛出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时,实际上初始化赋值的是一个空数组(public ArrayList())。当真正对数组进行添加元素操作时,才真正分配容量。即向数组中添加第一个元素时,数组容量扩为10

一步步分析ArrayList扩容机制

  • 先来看Add方法
/**
*将指定的元素追加到此列表的末尾
*/
public boolean add(E e) {
		//添加元素之前,先调用ensureCapacityInternal方法
        ensureCapacityInternal(size + 1);  // Increments modCount!!(增量modCount)
        //这里看到ArrayList添加元素的实质就相当于为数组赋值
        elementData[size++] = e;
        return true;
    }
  • 再来看看ensureCapacityInternal()方法
    可以看到add()方法首先调用了ensureCapacityInternal(size+1)
//得到最小扩容量
private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        		//获取默认的容量和传入参数的较大值(第一次的较大值是DEFAULT_CAPACITY=10,minCapacity=1)
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

当要add进第一个元素时,minCapacity为1,在Math.max()方法比较后,minCapacity为10

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

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        //调用grow()方法进行扩容,调用此方法代表已经开始扩容了
            grow(minCapacity);
    }

我们来仔细分析一下

  1. 当我们要add进第一个元素到ArrayList时,elementData.length为0(因为还是一个空的list,里面还没有数据,所以没有进行扩容,默认扩容10),因为执行了ensureCapacityInternal()方法,所以minCapacity此时为10。此时,minCapacity – elemetData.length > 0(minCapacity=10,elemetData.length=0)成立,所以会进入==grow(minCapacity)==方法。
  2. 当add第2个元素时,minCapacity为2,此时elementData.length(容量)在添加第一个元素后扩容成10了。此时,minCapacity – elementData.length > 0不成立,所以不会进入(执行)==grow(minCapacity)==方法。
  3. 添加第3、4…到第10个元素时,依然不会执行==grow()==方法,数组容量都为10。
    知道添加第11个元素,minCapacity(为11)比elementData.length(为10)要大。进行grow方法进行扩容
  4. grow方法
private void grow(int minCapacity) {
        // oldCapacity为旧容量,newCapacity为新容量
        int oldCapacity = elementData.length;//(0,10,15)
        //将oldCapacity右移一位,其效果相当于oldCapacity/2;
        // 我们知道位运算的速度远远快于整除运算,整句运算式的结果就是将新容量更新为旧容量的1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        // 然后检查新容量是否大于最小需要容量,若还是小于最小需要容量,那么久把最小需要容量当作数组的新容量
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
            //判断新容量是否大于集合的最大容量(一般大不了)
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 给elementData从新赋值(10,15)
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍!

“>>”(移位运算符):>>1 右移一位相当于除2,右移n位相当于除以 2 的 n 次方。这里 oldCapacity 明显右移了1位所以相当于oldCapacity /2。对于大数据的2进制运算,位移运算符比那些普通运算符的运算要快很多,因为程序仅仅移动一下而已,不去计算,这样提高了效率,节省了资源

通过例子探究一下grow()方法

  • 当add第一个元素时,oldCapacity为0,经比较后第一个if判断成立,newCapacity = minCapacity(为10)。但是第二个if判断不会成立,即newCapacity不比MAX_ARRAY_SIZE大,则不会进入hugeCapacity方法。数组容量为10,add方法中return true,size增为1。
  • 当add第11个元素进入grow方法时,newCapacity为15,比minCapacity(为11)大,第一个if判断不成立。新容量没有大于数组最大size,不会进入hugeCapacity方法。数组容量扩为15,add方法中rerurn,true,size增为11。
  • 以此类推…
    这里补充一点比较重要,但是容易被忽视掉的知识点:
  • java中的length属性是针对数组说的,比如说你声明了一个数组,想知道这个数组的长度则用到了length这个属性。
  • java中的length() 方法是针对字符串说的,如果想看这个字符串的长度则用到 length() 这个方法。
  • java中的size() 方法是针对泛型集合说的,如果想看这个泛型有多少元素,就调用此方法类查看!

System.arraycopy() 方法

// 将指定的元素插入此列表中的指定位置。  
// 如果当前位置有元素,则向右移动当前位于该位置的元素以及所有后续元素(将其索引加1)。  
public void add(int index, E element) {  
   if (index > size || index < 0)  
       throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);  
   // 如果数组长度不足,将进行扩容。  
   ensureCapacity(size+1);  // Increments modCount!!  
   // 将 elementData中从Index位置开始、长度为size-index的元素,  
   // 拷贝到从下标为index+1位置开始的新的elementData数组中。  
   // 即将当前位于该位置的元素以及所有后续元素右移一个位置。  
   // //elementData:源数组;index:源数组中的起始位置;elementData:目标数组;index + 1:目标数组中的起始位置; size - index:要复制的数组元素的数量;
   System.arraycopy(elementData, index, elementData, index + 1, size - index);  
   elementData[index] = element;  
   size++;  
}

插入数据

public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("111");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("555");
    list.add("666");
    list.add("777");
    list.add("888");
    list.add(2, "000");
    System.out.println(list);
}

看到插入的时候,按照指定位置,把从指定位置开始的所有元素利用System.arraycopy方法做一个整体的复制,向后移动一个位置(当然先要用ensureCapacity方法进行判断,加了一个元素之后数组会不会不够大),然后指定位置的元素设置为需要插入的元素,完成了一次插入的操作。用图表示这个过程是这样的
插入数据

在这个方法中最根本的方法就是System.arraycopy()方法,该方法的根本目的就是将index位置空出来以供新数据插入,这里需要进行数组数据的右移,这是非常麻烦和耗时的,所以如果指定的数据集合需要进行大量插入(中间插入)操作,推荐使用LinkedList。

删除数据

public E remove(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

        modCount++;
        E oldValue = (E) elementData[index];

        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

        return oldValue;
    }
public static void main(String[] args)
{
    List<String> list = new ArrayList<String>();
    list.add("111");
    list.add("222");
    list.add("333");
    list.add("444");
    list.add("555");
    list.add("666");
    list.add("777");
    list.add("888");
    list.remove("333");
}

删除数据
1、把指定元素后面位置的所有元素,利用System.arraycopy方法整体向前移动一个位置

2、最后一个位置的元素指定为null,这样让gc可以去回收它

int[]a = new int[10];
        a[0] =0;
        a[1] =1;
        a[2] =2;
        a[3] =3;
        a[4]=4;
        a[5]=5;
        a[6]=6;
        a[7]=7;
        a[8]=8;
        a[9]=9;
       System.arraycopy(a,2,a,3,7);
        for (int i=0;i<a.length;i++){
            System.out.println(i+"****"+a[i]);
        }

从原数组(a)中第2位开始往后面取三位(2.3.4),然后copy到新数组(这里还是a)中,从第3位开始放(3.4.5被替换成原数组的2.3.4)

2019-04-15 17:50:27.658 28361-28361/? I/System.out: 0****0
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 1****1
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 2****2
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 3****2
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 4****3
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 5****4
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 6****5
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 7****6
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 8****7
2019-04-15 17:50:27.658 28361-28361/? I/System.out: 9****8

参考文献

https://juejin.im/post/5ba1a3156fb9a05d1478178b

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

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

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

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

(0)


相关推荐

  • PS套索工具抠图及快捷键[通俗易懂]

    PS套索工具抠图及快捷键[通俗易懂]一、首先打开Photoshop,并打开一张所需的要抠图的文件,并按Ctrl+J复制一层二、套索工具在工具栏的上方,快捷键为L。鼠标点击工具栏选择套索工具,或按快捷键L选择,套索工具有三个子工具菜单,套索,多边形套索和磁性套索1.普通套索工具。这个工具时根据操作者控制鼠标的路径来选取选取的,且精度不易控制,完全靠制作者的手法来控制精度我们只要选择这个工具,然后按着鼠标左键开始跟着鼠标轨迹把选取描绘出来,最后松开鼠标,即可完成2.多边形套索工具。适合选取比较规则的几何图形首先点区图片要扣取的一

  • PLANTINUM_plantuml流程图

    PLANTINUM_plantuml流程图bytotinunsplash1.背景随着工作时间的增长,越发觉得用专业的图形(用例图,时序图,ER图等等)去准确表达想法是很重要的。比如针对某个需求绘制的的用例图,比一段乏味的文字来的更加有意义,也便于别人理解。加之最近在学习源码的时候,发现很多书籍中都会使用类图,时序图等UML语言来描述逻辑关系。于是就在网上找了找绘制UML语言时,业界主流的一些工具都用什么,找了半天,大部分都用了下面…

    2022年10月26日
  • gmt时间和cst时间_时区utc是什么意思

    gmt时间和cst时间_时区utc是什么意思全球24个时区的划分相较于两地时间表,可以显示世界各时区时间和地名的世界时区表(WorldTime),就显得精密与复杂多了,通常世界时区表的表盘上会标示着全球24个时区的城市名称,但究竟这24个时

  • laravel5的Bcrypt加密方式对系统保存密码的小结

    laravel5的Bcrypt加密方式对系统保存密码的小结

    2021年10月24日
  • 写代码有这16个好习惯,可以减少80%非业务的bug[通俗易懂]

    写代码有这16个好习惯,可以减少80%非业务的bug

  • CMS和G1收集器

    CMS和G1收集器转自:https://yuanrengu.com/2020/4c889127.html在开始介绍CMS和G1前,我们可以剧透几点:根据不同分代的特点,收集器可能不同。有些收集器可以同时用于新生代和老年代,而有些时候,则需要分别为新生代或老年代选用合适的收集器。一般来说,新生代收集器的收集频率较高,应选用性能高效的收集器;而老年代收集器收集次数相对较少,对空间较为敏感,应当避免选择基于复制算法的收集器。 在垃圾收集执行的时刻,应用程序需要暂停运行。 可以串行收集,也可以并行收集。 如果能做到并发

发表回复

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

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