JDK源码深入学习之ArrayList
ArrayList概述
ArrayList：是一个可以动态改变大小的数组。
ArrayList：直接用的数组下标取的元素，所以查询效率较高。但是由于增删涉及数组元素的移动，所以增删效率比较低
ArrayList：线程不安全的，建议使用Vector或者CopyOnWriteArrayList
ArrayList：继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。设计初衷就是为了解决数组大小不可动态拓展的局限性。
ArrayList继承关系图：
ArrayList源码解读（JDK1.8）
ArrayList全局变量
// 默认的数组初始化大小为10
private static final int DEFAULT_CAPACITY = 10;
// 用于空实例的共享空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
// 用于默认大小为空的共享数组的实例。我们将其与空实例的共享空数组实例分开来，以了解添加第一个元素时要膨胀多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 实际存放数据的数组
transient Object[] elementData;
// arrayList的长度
private int size;
ArrayList三个构造器
1.传入创建ArrayList大小为initialCapacity的有参构造器，创建一个指定大小的数组
创建大小 initialCapacity > 0,创建initialCapacity大小的ArrayList
创建大小 initialCapacity = 0,创建初始化大小为10的ArrayList
创建大小 initialCapacity < 0,抛异常不支持
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.无参构造器，创建一个空数组
注意：无参初始化并不是在无参构造方法的位置执行的，而是在第一次执行add方法的时候执行了容器大小的设置。所以容器的初始大小应该是0
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.传入一个集合Collection的有参构造器,创建一个与Collection c一样大小的数组，并把c中元素赋值至新数组
public ArrayList(Collection<? extends E> c) {
// 将c转换成数组
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// 如果数组的类型不是object，转为object类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 指向一个空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
arraycopy()方法：将原数组赋值到新创建的数组中（由于ArrayLits底层都会用到arraycopy方法，这里我提前说明一下）
src：原数组
srcPos：原数组中开始复制的位置
dest：目标数组
destPos：目标数组存放的位置，即从原数组的复制过来的元素从这个位置开始存放数据
length：复制数组的长度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
add()添加元素
JDK源码中ArrayListd添加一个元素提供了2个add()方法，分别是添加在ArrayList末尾和在具体某个下标位置添加元素。ArrayList在添加元素时会检查当前数组是否已经满了，如果满了则会进行1.5倍扩容。
/**
* add方法1：ArrayList末尾添加一个元素
* @param e 添加的元素
* @return
*/
public boolean add(E e) {
// 添加元素时,判断数组大小是否越界，越界则需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* add方法2，在某个下标位置添加元素
* @param index 下标位置
* @param element 添加的元素
*/
public void add(int index, E element) {
// 检查下标是否在数组范围内
rangeCheckForAdd(index);
// 添加元素时,判断数组大小是否越界，越界则需要扩容
ensureCapacityInternal(size + 1);
// 1.从index位置开始复制原数组elementData到最后一个元素
// 2.copy至原数组elementData的index+1的位置开始（size - index）个元素，也就是后面所有元素
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 给index位置赋值新添加元素
elementData[index] = element;
// arrayList长度+1
size++;
}
ArrayList在添加元素时动态扩容：
ensureCapacityInternal是ArrayLlist比较核心的一个方法，用于数组大小不够时进行扩容
private void ensureCapacityInternal(int minCapacity) {
// 计算添加元素后的新数组容量，若新容量导致数组越界则扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
// 修改的次数，添加一次修改次数+1。用于快速失败迭代器（和列表迭代器）
modCount++;
// 如果当前数组长度不满足于最小所需新容量，则扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// 扩容原数组大小的1.5倍
int oldCapacity = elementData.length;
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);
}
/*
*计算添加元素后的新数组容量
*若当前数组为空，容量为默认数组大小10和minCapacity最大的一个
*若当前数组不为空，容量为minCapacity
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
get()取得元素
get()：直接用数组下标取得，所以ArrayList查询速度比较快
/**
* 取得一个元素
* @param index 取得元素下标
* @return
*/
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
remove()删除元素
JDK提供2个移除元素的方法，分别是以下标或元素来移除元素。
具体移除都是先移除指定位置的元素,然后将该元素之后的元素集体前移一位。如果这个元素位置十分靠前，而数组长度又很大，此时就会极大的耗费性能。
/**
* 移除一个元素
* @param index 待移除元素下标
* @return
*/
public E remove(int index) {
// 校验待移除元素下标是否在数组范围内
rangeCheck(index);
// 操作计数+1
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
// 1.复制elementData数组从（index+1）位置开始的元素，
// 2.把复制的元素从index位置开始，拷贝numMoved个元素至elementData，也就是（index+1）位置后所有元素
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 移除一个元素
* @param index 待移除元素
* @return
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
clone()克隆：拷贝一个ArrayList
注意：ArrayList的clone()是浅拷贝
浅拷贝：被复制对象的任何变量都含有和原来的对象相同的值，而任何的对其他对象的引用仍然指向原来的对象。对拷贝后的引用的修改，还能影响原来的对象。
深拷贝：把要复制的对象所引用的对象都复制了一遍，对现在对象的修改不会影响原有的对象。
/**
* 克隆：ArrayList是浅拷贝，拷贝一个List
* @return
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
ArrayList三种遍历方式
（1）随机访问，通过索引值去遍历。由于ArrayList实现了RandomAccess接口，它支持通过索引值去随机访问元素。（索引取数据，效率最高）
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
（2）for循环遍历
for (Object str : list) {
System.out.println(str);
}
（3）迭代器访问
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()){
String str = iterator.next();
System.out.println(str);
}
总结
- ArrayList的元素有序可重复
- ArrayList底层的操作都是基于数组的操作
- ArrayList查询快，增删慢
- ArrayList线程不安全
- ArrayList每次扩容1.5倍
- ArrayList允许存放null
本文地址：https://blog.csdn.net/qq_38425803/article/details/107086438
上一篇： C#操作session的类实例