要了解ArrayList的扩容机制就必须要先了解ArrayList的构造以及底层。
一,ArrayList底层数据结构基本概念:
ArrayList就是动态数组,是List接口的可调整大小的数组实现;除了实现List接口之外,该类还提供了一些方法来操纵内部使用的存储列表的数组大小。它的主要底层实现是数组Object[] elementData。
数组的特点:
遍历查询速度快——数组在内存是连续空间,可以根据地址+索引的方式快速获取对应位置上的元素。
但是它的增删速度慢——每次删除元素,都需要更改数组长度、拷贝以及移动元素位置。
二,ArrayList构造方法
对象表示现实世界中某个具体的事物;
抽象是从特定的实例中抽取共同的性质以形成一般化概念的过程;
类是具有共同属性和行为的对象的抽象;
类也称为模板,因为它们提供了对象的基本框架;
类可以定义为数据和方法的集合;
源码中的无参构造:
使用默认的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 extends E> 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 extends E> c)//构造一个包含指定 collection 的元素的列表



