ArrayList相信大家都用过，那么今天就来聊聊ArrayList。
概述
ArrayList是一个相对来说比较简单的数据结构，底层是用数组实现的，它和数组最大的区别就是可以自动扩容，即我们可以认为ArrayList就是一个动态数组。
ArrayList 允许空值和重复元素，ArrayList 是非线程安全类，并发环境下，多个线程同时操作 ArrayList，会引发不可预知的错误。
源码分析
构造方法
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//transient 修饰，不参与序列化
transient Object[] elementData;
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
ArrayList 有两种构造方法，一种有参，一种无参。逻辑都很简单，目的就是初始化底层的数组elementData。默认的构造方法会初始化一个空的数组。
增加元素
public boolean add(E e) {
//检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加元素到末尾
elementData[size++] = e;
return true;
}
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++;
}
add方法有两种，一种是直接添加元素到末尾，一种是添加到指定位置。两种步骤差不多，就是第二种会有一个将元素整体位移的操作。（第二种效率肯定较低，在大集合中应该尽量避免调用）
从上面代码中不难看出，扩容的操作是在ensureCapacityInternal方法中完成的，那么我们来看看扩容的具体过程。
private static final int DEFAULT_CAPACITY = 10;
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//边界检查，保证最小容量 >10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//扩容的核心方法
private void grow(int minCapacity) {
int oldCapacity = elementData.length;
//扩容为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
//仍然不够就直接扩容为需求值
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 如果最小容量超过 MAX_ARRAY_SIZE，则将数组容量扩容至 Integer.MAX_VALUE
newCapacity = hugeCapacity(minCapacity);
//产生新的数组，并复制原有数组到新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
代码虽然不短，但是大部分操作都是边界检查。扩容的核心方法是grow方法。它计算出新的容器大小（即newCapacity），并确保了newCapacity不会比minCapacity小，最后调用Arrays.copyOf()创建一个新的数组并将数据拷贝到新数组中，最后让elementData进行引用。默认的扩容大小是当前数组大小的一半，即扩容至当前容量的1.5倍。
删除元素
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
删除操作也不是很复杂，就直接将删除元素后面的所有元素向前移一位，这样目标元素就会被覆盖，然后把最后的那个元素置空，同时将size变量减1。
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;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
remove方法还有另一种，用要删除的Object作为参数。这种就是从前往后遍历整个数组，找到第一个和目标相等的对象，然后执行删除操作，删除的过程和指定位置删除没有区别。如果删除了元素会返回true，该元素不存在则返回false。
查询及修改
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
get方法，直接返回目标元素。
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
set方法，直接修改目标元素。
总结
ArrayList是我们常用的集合类型，底层由数组实现，方法都非常简单。在用无参构造方法创建时会创建一个空数组，直到有元素放入后才会扩容为10。默认扩容为原来的1.5倍，如果1.5倍仍不够，则会直接扩容到目标值。由于扩容操作会将原数组拷贝到创建出的新数组中，因此开销较大，应尽量在初始化时设置好数组的容量。
由于底层为数组实现，随机读写开销小，因此ArrayList适用于存储访问频繁，但增删较少的数据。
网友评论