Java基础——ArrayList详解

Z时代
2024-01-10
分类：技术分享

结构图

ArrayList内部是以动态数组的形式来存储数据的。这里的动态数组不是意味着去改变原有内部生成的数组的长度、而是保留原有数组的引用、将其指向新生成的数组对象、这样会造成数组的长度可变的假象。

ArrayList具有数组所具有的特性、通过索引支持随机访问、所以通过随机访问ArrayList中的元素效率非常高、但是执行插入、删除时效率比较底下

ArrayList实现了Serializable接口，因此它支持序列化，能够通过序列化传输，实现了RandomAccess接口，支持快速随机访问，实际上就是通过下标序号进行快速访问，实现了Cloneable接口，能被克隆。

ArrayList不是线程安全的，只能用在单线程环境下，多线程环境下可以考虑用Collections.synchronizedList(List l)函数返回一个线程安全的ArrayList类，也可以使用concurrent并发包下的CopyOnWriteArrayList类。

基础属性

ArrayList部分源码如下：

public class ArrayList<E>
extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable,java.io.Serializable{
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
private transient Object[] elementData;
private int size;
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
protected transient int modCount = 0;
}

DEFAULT_CAPACITY：默认初始容量

EMPTY_ELEMENTDATA：一个空数组，方便使用，主要用于带参构造函数初始化和读取序列化对象等

DEFAULTCAPACITY_EMPTY_ELEMENTDATA：用于默认大小的空实例的共享空数组实例
- DEFAULTCAPACITY_EMPTY_ELEMENTDATA 和EMPTY_ELEMENTDATA 的区别
- 仅仅是为了区别用户带参为0的构造和默认构造的惰性初始模式对象。
- 当用户带参为0的构造，第一次add时，数组容量grow到1。
- 当用户使用默认构造时，第一次add时，容量直接grow到DEFAULT_CAPACITY（10）。

elementData：当前数据对象存放地方，当前对象不参与序列化

size：当前数组中元素的个数

MAX_ARRAY_SIZE:数组最大可分配容量

modCount：集合数组修改次数的标识（由AbstractList继承下来）

构造方法

//方法一
public ArrayList(int initialCapacity)
//方法二
public ArrayList()
//方法三
public ArrayList(Collection<? extends E> c){
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}

方法一：表示接受指定地容量值，初始化创建数组，建议在可估算数组大小时,创建ArrayList可指定

方法二：是默认的构造方法，它将创建一个空数组

方法三：接收一个Collection类的实例，将该Collection实例转换为ArrayList对象

add(E e)

public boolean add(E e) {
ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
returntrue;
}

向ArrayList集合添加元素，最重要的方法是扩容数组

//方法一
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//方法二
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//方法三
private void grow(int minCapacity) {
// overflow-conscious code
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);
}

方法一：在第一次向ArrayList添加元素时，设置容量扩容到多少

方法二：如果当前数组容量<需要的最小容量，则准备给数组扩容

方法三：扩容方法：
- 扩容原理：
- 获取当前数组容量
- 扩容后新数组容量newCapacity为旧数组的1.5倍
- 若值newCapacity比传入值minCapacity还要小，则使用传入minCapacity，若newCapacity比设定的最大数组容量大，则使用最大整数值
- 使用Arrays.copyof(elementData, newCapacity)进行扩容

于此，add方法走的流程就是：先扩容，再赋值，然后返回true

add(int index, E element)

public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);  // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,size - index);
elementData[index] = element;
size++;
}

向指定位置添加元素：

校验下标：调用rangeCheckForAdd方法进行下标校验，不正确则会抛出IndexOutOfBoundsException异常

扩容

移动数据

赋值

长度增加

扩容方法总结

ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍加1，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组。当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，这个操作代价很高，因此最好在创建ArrayList对象时就指定大概的容量大小，减少扩容操作的次数,或者使用LinkedList