ArrayList是一个底层基于数组的List接口实现,类似于Java的数据模型Array,但跟Array不一样的是它对于存储数量理论上是没有上限的(长度最大值是Integer.MAX_VALUE - 8),线程不安全,跟其相应的线程安全实现类是Vector,两者源码几乎一样,只不过在数据操作的时候Vector使用了synchronized机制来实现线程安全.
在阅读ArrayLIst的源码的时候,将它当成一个Array去理解解读的话会事半功倍,因为ArrayList相当于是用java代码实现的Array
番外篇 手写ArrayList https://github.com/wkx359518081/collection
源码版本 openjdk 1.8.0_212
字段
/**
* 默认初始化底层存储数组大小
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* ArrayList 延迟初始化的底层数组,构造方法不指定底层数组初始化大小或初始化大小为0时,先将底层数组赋值等于它
* 后面需要写操作的时候再进行初始化底层数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 用于存储数据的底层数组,绝大部分读写操作都与之相关
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* 存储数据数量, 相当于array.length
*/
private int size;
/**
* ArrayList 写操作次数,主要Java fastfail机制相关
*
*/
protected transient int modCount = 0;
读写操作
/**
* 获取ArrayList下某个下标的值
* 相当于 array[index]
*/
public E get(int index) {
// 核对是否数组越界
rangeCheck(index);
return elementData(index);
}
/**
* 设置ArrayList下某个下标的值为element
* 相当于array[index] = element
*/
public E set(int index, E element) {
// 核对index是否大于ArrayList的size,如果大于会抛出一个IndexOutOfBoundsException
// 如果array[array.length] = element 也会抛出IndexOutOfBoundsException,前面也说了ArrayList相当于Java代码实现的Array
rangeCheck(index);
// 将新的值放在该下标下并返回老的值
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
/**
* 往数组的末梢添加一个值,
* 在将ArrayList.size当成array.length的话相当于array[array.length] = e
* 但跟array不一样的是ArrayList会自动扩展它的底层数组ArrayList.elementData的长度大小,
* 避免ArrayList.elementData[size + 1] = e的时候抛出IndexOutOfBoundsException
*/
public boolean add(E e) {
// 检查ArrayList.elementData的大小是否大于size+1,如果小于需要进行对ArrayList.elementData长度扩展,具体实现看下面的动态扩展环节
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 跟前面的set(int index, E element)方法差不多,都会改变ArrayList下某个下标的值,
* 不一样的是该方法在修改index下标的值之前会移动将index到size-1下标的值进行右移
*/
public void add(int index, E element) {
// 核对index是否大于ArrayList.的size,如果大于抛出IndexOutOfBoundsException
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将index到size-1下标的值进行右移
/**
* System.arraycopy(arr, 2, arr, 3, arr.length - 1) 之前
* | A | B | C | D | E | F | G | H |
* System.arraycopy(arr, 2, arr, 3, arr.length - 1) 之后
* | A | B | null | C | D | E | F | G | H |
* 如果在面试的时候,面试官问你移动数组元素最快的方法是什么,答案就是System.arraycopy方法因为它的底层是用调用汇编的
*/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
/**
* 将ArrayLIst实例内存储的所有数据清空
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
// 方便jvm垃圾回收,去除掉没用数据的引用,参考jvm垃圾回收的可达性算法
elementData[i] = null;
size = 0;
}
动态扩展
/**
* 计算扩展的时候容量ArrayList.elementData数组的最小长度,
* 如果ArrayList.elementData没有初始化的话(值为{}),长度就是ArrayList.DEFAULT_CAPACITY
*/
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
/**
* 确保ArrayLIst.elementData的数组长度是否大于等于minCapacity如果不等于进行数组长度扩展
*/
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 判断是否需要数组长度扩展
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 实际扩展ArrayLIst.elementDatad的代码实现,每一次扩展都是老的长度的1.5倍
*/
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
// 计算新的数组长度,每一次扩展都是老的长度的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 判断计算出来的新的长度是否大于最大的长度,
// 如果大于的话但没有溢出Integer的存储范围的话等于Integer.MAX_VALUE
// 溢出抛出异常,表示达到了存储上限
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 进行数组扩展数据迁移
elementData = Arrays.copyOf(elementData, newCapacity);
}
网友评论