ArrayList源码分析
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
ArrayList是Java集合框架中的一个重要的类是我们日常开发中最常见的集合之一。
它继承于AbstractList实现了List接口是一个长度可变的集合提供了增删改查的功能。
集合中允许null的存在。ArrayList类还是实现了RandomAccess接口可以对元素进行快速访问。
实现了Serializable接口说明ArrayList可以被序列化还有Cloneable接口可以被复制。
和Vector不同的是ArrayList不是线程安全的。
1、构造函数
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// 默认初始容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 数组缓冲区数组列表的元素被存储在其中。数组列表的容量就是这个数组缓冲区的长度。当添加第一个元素时任何带有elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA的空数组列表将被扩展为DEFAULT_CAPACITY。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 存放元素的容器
transient Object[] elementData;
// 当前存放元素的个数并不代表数组大小
private int size;
//...
}为什么ArrayList是实现了Serializable接口的是可序列化的但存放元素的elementData数组是不被序列化的
ArrayList在被序列化的时候会调用writeObject()方法把sizeelementData写入到ObjectOutputStream在反序列化的时候再调用readObject()方法从ObjectOutputStream中获取sizeelementData再恢复到elementData中
这么做的原因是因为elementData是一个缓存数组它会预留一些容量等容量不足的时候再扩充容量那么这个数组可能有些空间根本就没有存储元素使用上面的序列化方式就可以保证只序列化实际存储的元素而不是数组本身从而节省空间时间。
// 如果我们预先知道一个集合元素的容纳的个数的时候推荐使用这个构造方法避免使用ArrayList默认的扩容机制而带来额外的开销。 看实例1
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//指定的容量大于0直接构建该大小的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//容量等于0构建一个空数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
//容量为负数不合法抛出异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
// 构造一个初始容量为10的空列表,为10的操作在add的时候设置的
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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 {
//容量等于0构建一个空数组.
elementData = EMPTY_ELEMENTDATA;
}
}实例1
//创建集合对象
List<String> list = new ArrayList<String>();
//添加元素
list.add("hello");
list.add("PHP");
list.add("Java");
long startTime = System.currentTimeMillis();
//需求:还需要添加100W条数据
for (int i = 0; i < 1000000; i++) {
list.add(i + "");
}
long endTime = System.currentTimeMillis();
System.out.println("未指定容量: " + (endTime - startTime));
//创建集合的时候指定足够大的容量
List<String> list1 = new ArrayList<String>(1000000);
startTime = System.currentTimeMillis();
for (int i = 0; i < 100000; i++) {
list1.add(i + "");
}
endTime = System.currentTimeMillis();
System.out.println("指定容量: " + (endTime - startTime));未指定容量: 378
指定容量: 11
可以看到性能相差很多
2、添加元素扩容机制
2.1、添加元素到末尾
public boolean add(E e) {
// 判断是否需要扩容
ensureCapacityInternal(size + 1);
// 添加元素到末尾
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 如果是用ArrayList无参构造方法初始化,那么数组指向的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA.第一次add()元素会进入if内部, 且minCapacity为1,那么最后minCapacity肯定是10,所以ArrayList无参构造方法上面的默认用量为10就是在这里实现的
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 记录被修改的次数,用于保证线程安全,如果在迭代的时候该值意外被修改,那么会报ConcurrentModificationException错这就是为什么在遍历的时候不能增删改元素会报错的原因
protected transient int modCount = 0;
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果添加完元素后长度大于当前数组的长度则执行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// 当前长度
int oldCapacity = elementData.length;
// 扩容1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容1.5倍后还不够则使用该大小只添加一个元素的情况下触发扩容1.5倍肯定是够的只是有时还可以添加集合的情况看2.3节
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
/// 如果新数组容量比最大值还大,那么交给hugeCapacity()去处理
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 复制数组底层是system.arraycopy(),将elementData复制到大小为newCapacity的新数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0)
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}2.2、插入元素到指定位置
public void add(int index, E element) {
// 下标合法性校验
rangeCheckForAdd(index);
// 判断是否需要扩容
ensureCapacityInternal(size + 1);
// 复制元素将 elementData从index处开始复制size-index个元素到index+1位置大白话就是将下标index处开始的后续元素都往后移一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 成功复制后赋值
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}2.3、插入集合到末尾
public boolean addAll(Collection<? extends E> c) {
// 新集合转数组
Object[] a = c.toArray();
// 数组大小
int numNew = a.length;
// 判断是够需要扩容
ensureCapacityInternal(size + numNew);
// 复制数组元素
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}2.4、添加集合到指定位置
public boolean addAll(int index, Collection<? extends E> c) {
// 下标合法性校验
rangeCheckForAdd(index);
//转数组
Object[] a = c.toArray();
int numNew = a.length;
//判断是否需要扩容
ensureCapacityInternal(size + numNew); // Increments modCount
// 需要后移的元素个数
int numMoved = size - index;
// 移动元素将elementData数组从下标index处开始移动numMoved个元素到index+newNew处
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
//复制a数组全部元素到elementData数组的下标index处
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}3、移除元素
3.1、移除指定位置元素
public E remove(int index) {
// 下标合法性校验
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//将elementData数组从下标index+1处开始移动numMoved个元素到index处
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将数组末尾处的元素置为null方便gc回收
elementData[--size] = null;
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}3.2、移除指定元素
public boolean remove(Object o) {
if (o == null) {
// 遍历整个数组移除第一个元素为null的元素
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
// 遍历获取第一个与o equals()的元素
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将数组末尾处的元素置为null方便gc回收
elementData[--size] = null;
}3.3、移除所有包含在指定集合中的元素
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
// 循环遍历数组将不需要删除的元素放到数组的前面
if (c.contains(elementData[r]) == complement)
r是正在遍历的位置w是用于记录有效元素的在w之前的全是有效元素,w之后的会被删除
elementData[w++] = elementData[r];
} finally {
// 正常情况下r==size如果不等于说明遍历的过程遇见了异常就将出错位置r后面的元素全部放到w后面
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// 如果w!=size,代表有需要删除元素的否则就是找不到要删除的元素
if (w != size) {
// clear to let GC do its work
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}3.4、清除集合
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}3.5、移除区间内的所有元素
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
// 需要向前移动的元素个数
int numMoved = size - toIndex;
// 将elementData数组从toIndex下标开始移动numMoved个元素到fromIndex处
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// 有效元素后面的元素置空
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}4、改动元素
public E set(int index, E element) {
// 下标合法性校验
rangeCheck(index);
// 保存旧值
E oldValue = elementData(index);
// 设置新值
elementData[index] = element;
// 返回旧值
return oldValue;
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}5、获取元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}其它方法就不一一介绍了ArrayList的源码相对来说简单核心思想就是一个Object[]加上system.arraycopy对Object[]的操作。
6、ArrayList特点
1底层用Object数组来存储元素
2有扩容机制默认扩容机制是10每次扩容都是扩容到之前的1.5倍
3添加元素到指定位置可能会移动很多元素并且可能会触发扩容机制如果是添加元素到末尾那么只可能触发扩容机制
4删除指定位置的元素可能会移动很多元素删除末尾元素代价是最小的ArrayList删除元素是将末尾元素置为null
5查询或者修改某个具体位置的元素是很快的