一, 基本概念
ArrayList 是一个可以添加对象元素, 并进行元素的修改查询删除等操作的容器类. ArrayList 底层是由数组实现的, 所以和数组一样可以根据索引对容器对象所包含的元素进行快速随机的查询操作, 其时间复杂度为 O(1). 但是和数组不同的是, 数组对象创建后数组长度是不变的, ArrayList 对象创建后其长度是可变的, 所以 ArrayList 也称为动态数组, 那么 ArrayList 的动态数组数据结构又是如何实现的呢? 接下来打开 ArrayList 源码看看.
二, 源码分析
2.1,ArrayList 类的继承与实现
图 2.1 ArrayList 类的继承与实现(不包括继承 ArrayList 的类)
从继承接口可以发现, ArrayList 继承了 AbstractCollection 抽象类, 实现了 List 接口, 并且实现还实现了 RandomAccess,Cloneable 和 Serializable 三个标记接口, 所以 ArrayList 的的对象具有能根据索引对元素进行快速随机访问, 可以调用 Object 的 clone()方法, 可以进行序列化的特性. 有关 Java 的标记接口是什么, 在上一篇文章
《Java 的四个标记接口 Serializable,Cloneable,RandomAccess 和 Remote 接口》 进行了总结
2.2,ArrayList 的属性
通过源码可以知道 ArrayList 主要有以下属性
- private static final long serialVersionUID = 8683452581122892189L;// 用于 ArrayList 对象序列化的版本 ID
- private static final int DEFAULT_CAPACITY = 10;//ArrayList 对象的默认容量大小
- private static final Object[] EMPTY_ELEMENTDATA = {};// 用于 Null 的 ArrayList 对象
- private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// 用于创建一个默认容量大小的 ArrayList 对象
- transient Object[] elementData; // 用于创建动态大小的 ArrayList 对象, 这个实例变量引用的数组可以说就是 ArrayList 容器
- private int size;//ArrayList 对象的尺寸
2.3,ArrayList 类的三个构造函数
一个无参构造函数, 一个传入一个 int 量指定容量的构造函数和一个传入一个容器对象来进行初始化的构造函数
- 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);
- }
- }
- // 指定 ArrayList 初始容量的构造器
- public ArrayList() {
- this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
- }
- // 一个默认容量的 ArrayList 无参构造器
- public ArrayList(Collection<? extends E> c) {
- elementData = c.toArray();
- if ((size = elementData.length) != 0) {
- if (elementData.getClass() != Object[].class)
- elementData = Arrays.copyOf(elementData, size, Object[].class);
- } else {
- this.elementData = EMPTY_ELEMENTDATA;
- }
- }
- // 一个参数为一个容器对象的构造器, 将该容器对象转化为一个数组对象后, 将 ArrayList 对象内的数组引用 elementData 初始化为这个数组对象(Object[])
2.4,ArrayList 动态数组的具体实现细节
ArrayList 对象创建后, 是怎么改变这个对象的容量实现动态数组的呢, 来看看动态数组实现的几个重要方法
grow 方法. 实现了 ArrayList 对象容量增加的方式, 一般 ArrayList 新的容量为原容量的 1.5 倍大小, 源码如下
- private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;//int 整型的最大值减 8
- private void grow(int minCapacity) {
- int oldCapacity = elementData.length;// 原 ArrayList 对象的容量
- int newCapacity = oldCapacity + (oldCapacity>> 1);// 新的容量变为原容量 + 原容量 / 2, 也就是新的容量增大为原来的 1.5 倍
- if (newCapacity - minCapacity <0)
- newCapacity = minCapacity;
- // 新的容量如果还是小于指定容量, 则新容量的值更新为指定容量
- if (newCapacity - MAX_ARRAY_SIZE> 0)
- newCapacity = hugeCapacity(minCapacity);
- // 如果新容量大于 int 整数的最大值减 8 的值, 则调用 hugeCapacity(minCapacity), 新的容量为 Interger.MAX_VALUE, 即最大的 Int 整数
- elementData = Arrays.copyOf(elementData, newCapacity);
- // 创建一个数组长度为 newCapacity, 包含所有原 ArrayList 内 elementData 所有元素的新的 elementDate 数组
hugeCapacity 方法, 在 grow 方法中被调用
- private static int hugeCapacity(int minCapacity) {
- if (minCapacity <0) // overflow
- throw new OutOfMemoryError();
- return (minCapacity> MAX_ARRAY_SIZE) ?
- Integer.MAX_VALUE :
- MAX_ARRAY_SIZE;
- }
- View Code
trimToSize 方法. 将 ArrayList 对象内的 elementData 对象的长度变为 size,size 变量保存了 ArrayList 对象所含元素个数. 使用这个方法可以使 ArrayList 对象内的 elementData 数组长度为元素个数, 以避免不必要的内存占用.
- public void trimToSize() {
- modCount++;
- if (size <elementData.length) {
- elementData = (size == 0)? EMPTY_ELEMENTDATA: Arrays.copyOf(elementData, size);
- }
- // 如果 size 小于 elementData 的话, 如果 size=0, 令 elementData 为一个空数组; size>0, 使 elementDate 数组变量指向包含原 elememtData 所有元素, 长度为元素个数 size 的新数组
- }
ensureExplicitCapacity 方法, 在参数 minCapacity 大于 elementDate 引用的数组的长度时, 调用 grow 方法来增加容量
- private void ensureExplicitCapacity(int minCapacity) {
- modCount++;
- if (minCapacity - elementData.length> 0)
- grow(minCapacity);
- }
ensureCapacity 方法, 如果构造 ArrayList 对象时调用的是无参构造器, 此时 elementDate 数组还没创建, 这个方法调用后可以确保 ArrayList 对象容量至少为 10(默认值), 且不小于 minCapacity 参数指定的值
- public void ensureCapacity(int minCapacity) {
- int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0: DEFAULT_CAPACITY;
- if (minCapacity> minExpand) {
- ensureExplicitCapacity(minCapacity);
- }
- }
ensureCapacityInternal 方法, 在调用 add 方法增加元素时, 调用这个方法来确保元素个数 + 1(size+1)小于或等于 elementDate 数组的长度, 若 size+1 大于 element.length, 在 ensureExplicitCapacity 方法中会调用 grow 方法对 ArrayList 对象进行扩容
- private void ensureCapacityInternal(int minCapacity) {
- ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
- }
add(int index)方法, 实现了在指定的索引处添加元素, 时间复杂度为 O(n)
- public void add(int index, E element) {
- rangeCheckForAdd(index);// 先检测索引是否越界
- ensureCapacityInternal(size + 1); // 确保 ArrayList 的容量, 即 elementData 数组的长度, 在添加元素前大于 size+1
- System.arraycopy(elementData, index, elementData, index + 1,
- size - index);
- // 将从 index 处以及后面的元素的都向后移动一位, 索引 + 1. 所以调用这个方法的时间复杂度为 O(n)
- elementData[index] = element;
- // 将元素 element 添加到索引为 index 的位置
- size++;// 元素个数加一
- }
remove(int index)方法, 实现了在指定的位置删除元素, 时间复杂度为 O(n)
- public E remove(int index) {
- rangeCheck(index);// 检查索引是否越界
- modCount++;
- E oldValue = elementData(index);
- int numMoved = size - index - 1;// 这个元素后面的元素个数
- if (numMoved> 0)
- System.arraycopy(elementData, index+1, elementData, index, numMoved);
- // 将这个元素后面的元素的前移一位, 索引减一, 原来 index 处的元素 (要被删除的元素) 被后面一位的元素覆盖. 所以这个方法的时间复杂度为 O(n)
- elementData[--size] = null;
- // 数组索引为 size 处没有元素, 使其为空, 元素个数 size-1
- return oldValue;
- // 将删除的元素作为方法的返回值
- }
- (ArrayList 还有很多其他的方法, 以上是 ArrayList 实现动态数组的主要方法, ArrayList 类其他的方法在这里就不一一赘述了)
- (小官原创, 若有谬误, 望各位大佬批评指正)
- (转载请注明出处)
来源: https://www.cnblogs.com/jianguan/p/10707419.html