ArrayList集合底层原理

ArrayList集合底层原理

1.介绍

​ ArrayList是List接口的可变数组的实现。实现了所有可选列表操作，并允许包括 null 在 内的所有元素。 每个 ArrayList 实例都有一个容量，该容量是指用来存储列表元素的数组的大小。它是至少等于列表的大小。随着向 ArrayList 中不断添加元素，其容量也自动增长。自动增长会带来数据向新数组的重新拷贝，因此，如果可预知数据量的多少，可在构造 ArrayList 时 指定其容量。

ArrayList集合特点为什么是增删慢、查询快

2.底层实现

底层使用数组实现
transient Object[] elementData;

3.构造方法

​ ArrayList 提供了三种方式的构造器，可以构造一个默认初始容量为 10 的空列表、构造 一个指定初始容量的空列表以及构造一个包含指定 collection 的元素的列表，这些元素按照 该 collection 的迭代器返回它们的顺序排列的。

// 空参构造
ArrayList<String> list1 = new ArrayList<>(); 
// 源码
public ArrayList() {/*DEFAULTCAPACITY_EMPTY_ELEMENTDATA: 指向private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};空数组.注意:默认长度是在第一次添加元素时赋值的数组*/this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}// 指定初始长度
ArrayList<String> list2 = new ArrayList<>(100);
// 源码
public ArrayList(int initialCapacity) {// 判断传入的长度大小if (initialCapacity > 0) {// 根据长度创建数组this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {// 如果等于0,返回默认长度数组// EMPTY_ELEMENTDATAprivate: 指向static final Object[] EMPTY_ELEMENTDATA = {};this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}
}
// 包含指定 collection 的元素的列表
List<String> list = new ArrayList<>();
ArrayList<String> list3 = new ArrayList<>(list);
// 源码
public ArrayList(Collection<? extends E> c) {// 先把传入的集合转成数组elementData = c.toArray();// 判断集合的长度是否等于0if ((size = elementData.length) != 0) {// 判断数组字节码类型 为什么要判断,因为c.toArray()有可能转变的不是Object数组if (elementData.getClass() != Object[].class)// copyOf把参数集合的元素拷贝到定义数组// elementData:要复制的数组// size:长度// Object[].class:要返回的新数组elementData = Arrays.copyOf(elementData, size, Object[].class);} else {//EMPTY_ELEMENTDATA:指向:private static final Object[] EMPTY_ELEMENTDATA = {};this.elementData = EMPTY_ELEMENTDATA;}
}

3.1集合的属性

//默认容量的大小
private static final int DEFAULT_CAPACITY = 10;//空数组常量
private static final Object[] EMPTY_ELEMENTDATA = {};//默认的空数组常量
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};//存放元素的数组，从这可以发现 ArrayList 的底层实现就是一个 Object数组
transient Object[] elementData;//数组中包含的元素个数
private int size;//数组的最大上限
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

4.扩容机制

​ 图解:

​ 扩容源码:

public boolean add(E e) {// 计数器,返回实时增加的元素个数,比如调用size()方法返回的集合元素个数modCount++;/*1.e:表示现在要添加的元素2.elementData集合底层数组名3.size本次要添加的索引位置,第一次添加size的值为0*/add(e, elementData, size);return true;
}private void add(E e, Object[] elementData, int s) {// 判断存入的位置索引if (s == elementData.length)// 调用grow方法进行扩容elementData = grow();// 索引位置小于数组长度正常存入elementData[s] = e;size = s + 1;
}private Object[] grow() {// 第一次存入元素size默认为0,进行长度加1return grow(size + 1);
}private Object[] grow(int minCapacity) {/*创建一个新的数组长度为10把原来数组元素拷贝进去minCapacity:传入的容量*/return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity));
}private int newCapacity(int minCapacity) {// overflow-conscious code// 旧容量int oldCapacity = elementData.length;// 新容量 = 旧容量 * 1.5int newCapacity = oldCapacity + (oldCapacity >> 1);// 拿新的容量 - 传入的大小 如果结果小于0,if (newCapacity - minCapacity <= 0) {// 第一次扩容// 判断数组是否是同一个数组if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)// DEFAULT_CAPACITY默认容量=10// 比较默认容量与传入容量大小,把最大返回return Math.max(DEFAULT_CAPACITY, minCapacity);if (minCapacity < 0) // overflow 内存溢出throw new OutOfMemoryError();return minCapacity;}// 返回新的长度return (newCapacity - MAX_ARRAY_SIZE <= 0)? newCapacity: hugeCapacity(minCapacity);
}ArrayList的add方法，在插入元素之前，它会先检查是否需要扩容，然后再把元素添加到数组中最后一个元素的后面。
在 newCapacity 方法中，我们可以看见，如果当 elementData 为空数组时，它会使用默认的大小去扩容。所以说，
通过无参构造方法来创建 ArrayList 时，它的大小其实是为 0 的，只有在使用到的时候，才会通过 grow 方法去创建
一个大小为 10 的数组。第一个 add 方法的复杂度为 O(1)，虽然有时候会涉及到扩容的操作，但是扩容的次数是非常
少的，所以这一部分的时间可以忽略不计。如果使用的是带指定下标的 add方法，则复杂度为 O(n)，因为涉及到
对数组中元素的移动，这一操作是非常耗时的。

5.其他方法

// 修改方法
public E set(int index, E element) {// 判断是否会发生异常Objects.checkIndex(index, size);// 根据索引获取元素E oldValue = elementData(index);// 把传入的元素替换原来的元素elementData[index] = element;// 返回原来的元素return oldValue;
}// 指定索引处添加,如果当前有元素,则向右移动当前位与该位置的元素以及所有后续元素
public void add(int index, E element) {// 判断是否发生异常rangeCheckForAdd(index);// 记录修改次数, 一般研究线程安全性问题,关注这个变量modCount++;final int s;Object[] elementData;/*(s = size):数组长度,下面拷贝使用了(elementData = this.elementData):当前数组,下面有用到判断元素个数是否与数组长度相同*/if ((s = size) == (elementData = this.elementData).length)// 数组扩容前面已经讲解elementData = grow();// 将elementData中从index位置开始,长度为s-index的元素// 拷贝到从下标为index+1位置开始的新的elementData数组中// 也就是当前位于该位置的元素以及后面的元素向后移动一位System.arraycopy(elementData, index,elementData, index + 1,s - index);// 把元素赋值到指定索引处elementData[index] = element;// 长度加一size = s + 1;
}// 返回此列表中指定位置上的元素。
public E get(int index) {// 判断异常Objects.checkIndex(index, size);// 返回元素return elementData(index);
}// 移除指定索引处元素
public E remove(int index) {// 判断异常Objects.checkIndex(index, size);// 临时变量数组赋值final Object[] es = elementData;// 拿到指定索引处的元素@SuppressWarnings("unchecked") E oldValue = (E) es[index];fastRemove(es, index);return oldValue;
}
private void fastRemove(Object[] es, int i) {// 记录修改次数, 一般研究线程安全性问题,关注这个变量modCount++;// 定义临时变量final int newSize;// 判断数组长度-1,是否大于变量索引if ((newSize = size - 1) > i)/*将es中从索引i+1位置开始,长度为newSize - i的元素拷贝到从下表i + 1位置开始的新的es数组中也就是当前位于该位置的元素以及后面的元素向前一定一位*/System.arraycopy(es, i + 1, es, i, newSize - i);// 临时变量在赋值为nulles[size = newSize] = null;
}
// 移除指定元素
public boolean remove(Object o) {// 定义临时数组,并赋值final Object[] es = elementData;// 定义临时长度变量,并赋值final int size = this.size;int i = 0;// found标识,发现指定元素found: {if (o == null) {for (; i < size; i++)if (es[i] == null)break found;} else {for (; i < size; i++)if (o.equals(es[i]))break found;}return false;}// 移除元素并移动fastRemove(es, i);return true;
}

6.总结

从上述代码中可以看出，数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的 1.5 倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造 ArrayList 实例时，就指定其容量，以避免数组扩容的发生。或者根据实际需求，通过调用 ensureCapacity 方法来手动增加 ArrayList 实例的容量。