最常用聚集 - arraylist详解
ArrayList先容ArrayList实现了List接口，是次序容器，即元素存放的数据与放进去的次序雷同，允许放入null元素，底层通过数组实现。除该类未实现同步外，其余跟Vector大抵雷同。每个ArrayList都有一个容量(capacity)，表示底层数组的实际大小，容器内存储元素的个数不能多于当前容量。当向容器中添加元素时，假如容量不敷，容器会主动增大底层数组的大小。
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404250836769.jpg
ArrayList 在JDK1.8 前后的实现区别：
[*]JDK1.7：像饿汉式，直接创建一个初始容量为10的数组
[*]JDK1.8：像懒汉式，一开始创建一个长度为0的数组，当添加add第一个元素时再创建一个初始容量为10的数组
size(), isEmpty(), get(), set()方法均能在常数时间内完成，add()方法的时间开销跟插入位置有关，addAll()方法的时间开销跟添加元素的个数成正比。其余方法多数是线性时间。
为追求服从，ArrayList没有实现同步(synchronized)，假如需要多个线程并发访问，用户可以手动同步，也可使用Vector替代
底层原理先容
底层数据结构
//集合默认容量10；
private static final int DEFAULT_CAPACITY = 10;
//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认容量的空的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 集合中真实存储数据的数组
transient Object[] elementData; // non-private to simplify nested class access
//集合中元素的个数，注意，这里不是数组的长度
private int size;构造方法
public ArrayList() {
//将属性中默认的空的数组赋值给了 存储数据的变量
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
//等价于this.elementData = {}
}
//有参构造
public ArrayList(int initialCapacity) {
//给定初始容量，就创建一个这个容量大小的数组
if (initialCapacity > 0) {
this.elementData = new Object;
} else if (initialCapacity == 0) {
//如果传递的是0 就将{}赋值给elementData
this.elementData = EMPTY_ELEMENTDATA;
//等价于this.elementData = {}
} else {
//如果传递的是负数，就会抛异常
//java.lang.IllegalArgumentException: Illegal Capacity: -20
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
}
}主动扩容
每当向数组中添加元素时，都要去检查添加后元素的个数是否会超出当前数组的长度，假如超出，数组将会进行扩容，以满足添加数据的需求。
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//动态扩容，扩容为原来的1.5倍，右移一位即原来的一半
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);//数组的复制操作
}扩容方法流程：
[*]起首获取数组长度
[*]将数组新容量扩容为原数组容量的1.5倍取整
[*]将新容量和当前所需最小容量做对比，(最小容量是在add方法中得到的，minCapacity=size+1，即原数组中元素数量加1)，而newCapacity=elementData.length*1.5，一般来说肯定是1.5倍比+1的大。但是这里要思量当数组为空时的情况。数组为空又分为两种情况：①指定了数组容量为0 ②没有显式指定命组大小。
[*]当数组为空时进行插入操作，因为元素个数size为0，数组容量也为0，那么就会进行扩容操作，对于空数组，扩容1.5倍后你的容量还是为0，那么此时就会小于我所需的最小容量（也就是1）,此时会令 newCapacity = minCapacity;
[*]而对于①，传入到grow方法的minCapacity = 1 ，因此它扩容后的容量就是1
[*]对于②，在ensureCapacityInternal方法中，使minCapacity = DEFAULT_CAPACITY（10），因此扩容后的数组长度就是DEFAULT_CAPACITY，也就是10。
[*]缘故原由在于在有参构造方法中使this.elementData = EMPTY_ELEMENTDATA;（无参构造方法中this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;），此时在ensureCapacityInternal方法中会对this.elementData进行判断，因此对于①，传入到grow方法的minCapacity = 1；而对于②，minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity)，即minCapacity = 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//比较大小，此时 minCapacity = 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
[*]最后判断新容量大小是否大于默认数组的最大值（Integer.MAX_VALUE-8），则赋予它整型的最大值
[*]扩容之后，会调用Arrays.copyOf()方法对数组进行拷贝。
实际上，对数组的copy需要创建一个新数组，并对原数组进行复制的操作，这会造成资源消耗。因此在添加大量元素前，建议使用ensureCapacity操作先增加 ArrayList 实例的容量，先进行稍少量数组数据的copy，再添加元素
https://seven97-blog.oss-cn-hangzhou.aliyuncs.com/imgs/202404250836779.jpg
add(), addAll()
add 操作可能会导致capacity不敷，因此在添加元素之前，都需要进行剩余空间检查，假如需要则主动扩容。扩容操作终极是通过grow()方法完成的。
假设使用的是空参构造，第一次添加元素 add(1)
public boolean add(E e) {
//确保内部容量 0 + 1
ensureCapacityInternal(size + 1);// Increments modCount!!
//将要添加的元素添加到数组有数据的下一个位置
elementData = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {//第一次添加： minCapacity = 1
//有参构造的情况：new Object != {}，不会执行if内的语句。即使有参构造给的是0，也不会执行，因为此时elementData = EMPTY_ELEMENTDATA，不等于DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 无参构造的情况下：{} = {} 会执行Math.max语句
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//比较大小，此时 minCapacity = 10
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//明确数组的容量
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//记录当前集合操作的次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);//扩容操作
}addAll()方法能够一次添加多个元素，根据位置不同也有两个版本，
<ul>
在末尾添加的addAll(Collection
页:
[1]