栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

ArrayList的扩容(大概)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

ArrayList的扩容(大概)

ArrayList的扩容(大概)

要了解ArrayList的扩容机制就必须要先了解ArrayList的构造以及底层。

一,ArrayList底层数据结构

基本概念:
ArrayList就是动态数组,是List接口的可调整大小的数组实现;除了实现List接口之外,该类还提供了一些方法来操纵内部使用的存储列表的数组大小。它的主要底层实现是数组Object[] elementData。

数组的特点:
遍历查询速度快——数组在内存是连续空间,可以根据地址+索引的方式快速获取对应位置上的元素。
但是它的增删速度慢——每次删除元素,都需要更改数组长度、拷贝以及移动元素位置。


二,ArrayList构造方法

对象表示现实世界中某个具体的事物;
抽象是从特定的实例中抽取共同的性质以形成一般化概念的过程;
类是具有共同属性和行为的对象的抽象;
类也称为模板,因为它们提供了对象的基本框架;
类可以定义为数据和方法的集合;

2.1,无参构造方法

源码中的无参构造:
使用默认的size为10的空数组,在构造方法中没有对数组长度进行设置,会在后续调用add方法的时候进行扩容。


//无参构造方法
//构造一个初始容量为 10 的空列表
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
2.2,参数为指定初始化容量的构造方法

源码中的int型构造方法:

指定初始化容量构造
参数大于0,elementData初始化为initialCapacity大小的数组;参数等于0,elementData初始化为空数组;参数小于0,抛出异常;

//源码中有一个int型的构造方法
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);
     }
 }
2.3,参数为Collection类型的构造方法

Collection类型构造
将一个参数为Collection的集合转变为ArrayList(实际上就是将集合中的元素换为了数组的形式);如果传入的集合为null会抛出空指针异常。c.toArray()可能不会正确地返回一个 Object[]数组,那么使用Arrays.copyof()方法。如果集合转换成数组之后数组长度为0,那就直接使用自己的空成员变量初始化elementData。

//一个参数为Collection的集合
 public ArrayList(Collection c) {
     Object[] a = c.toArray();
     if ((size = a.length) != 0) {
         if (c.getClass() == ArrayList.class) {
             elementData = a;
         } else {
             elementData = Arrays.copyOf(a, size, Object[].class);
         }
     } else {
         // replace with empty array.
         elementData = EMPTY_ELEMENTDATA;
     }
 }

总结:无参构造和初始化容量构造的目的都是初始化底层数组
elementData(this.elementData=XXX);

无参构造方法会将elementData初始化一个空数组,插入元素时,扩容将会按默认值重新初始化数组;有参构造方法会将elementData初始化为参数值大小(>=0)的数组;
如果在构造 ArrayList 实例时,指定初始化值(初始化容量或者集合),那么就会创建指定大小的 Object 数组,并把该数组对象的引用赋值给 elementData;如果不指定初始化值,在第一次添加元素值时会使用默认的容量大小 10 作为 elementData 数组的初始容量,使用 Arrays.conpyOf() 方法创建一个 Object[10] 数组。

一般情况下,我们用默认的构造方法即可。上面说到使用无参构造时会调用add方法并进行扩容

三,添加add()方法分析
//将添加的数据传入给e 
public boolean add(E e) { 
 //调用方法对内部容量进行校验 
 ensureCapacityInternal(size + 1); 
 elementData[size++] = e; 
 return true; 
} 
private void ensureCapacityInternal(int minCapacity) { 
     //判断集合存数据的数组是否等于空容量的数组 
     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
     //通过最小容量和默认容量 出较大值 (用于第一次扩容) 
         minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); 
     } 
     //将if中计算出来的容量传递给下一个方法,继续校验 
     ensureExplicitCapacity(minCapacity); 
 } 

然后是扩容的核心**grow()**方法:

private void grow(int minCapacity) { 
        //记录数组的实际长度,此时由于木有存储元素,长度为0 
        int oldCapacity = elementData.length; 
        //核心扩容算法   原容量的1.5倍 
        int newCapacity = oldCapacity + (oldCapacity >> 1); 
        //判断新容量-最小容量是否小于0, 如果是第一次调用add方法必然小于
        if (newCapacity - minCapacity < 0) 
        //还是将最小容量赋值给新容量 
        newCapacity = minCapacity; 
        //判断新容量-最大数组大小是否>0,如果条件满足就计算出一个超大容量
        if (newCapacity - MAX_ARRAY_SIZE > 0) 
        newCapacity = hugeCapacity(minCapacity); 
        // 调用数组工具类方法,创建一个新数组,将新数组的地址赋值给
        elementData elementData = Arrays.copyOf(elementData, newCapacity); 
}

小总结:
扩容的大小是原先数组的1.5倍;
=========================================================================================== 若值newCapacity比传入值minCapacity还要小,则使用传入minCapacity,若newCapacity比设定的最大容量大,则使用最大整数值;

public ArrayList() //默认构造一个初始容量为10的空列表。
public ArrayList(int initialCapacity)//构造一个具有指定初始容量的空列表。
public ArrayList(Collection c)//构造一个包含指定 collection 的元素的列表

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/986553.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号