ArrayList 我们都知道底层是使用 数组（线性表）来存储元素的。我们就来简单的分析一下 ，它是如何动态扩容的。
// 构造函数
List list = new ArrayList();
list.add(1);// 添加一个元素。
我们就从这两句代码开始。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
// initialCapacity 默认是10
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity]; // 初始化Object 数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA; // 初始容量为0 的话，就是默认空数组。
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
}
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
我们看到 ArrayList 集合是采用 Object 数组来存储的数据。创建时我们可以传入 数组容量大小，没有传入的话 就是一个空数组。
- add() 方法：
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
往集合里面 添加一个元素，首先 重新确定 集合 大小 ensureCapacityInternal(size + 1);，然后 将元素 elementData[size++] = e; 加入到 数组中。注意这里是线程非安全的。我们再来看看 它底层是如何计算 数组容量的。
- ensureCapacityInternal(size + 1); //size 默认等于 0
private void ensureCapacityInternal(int minCapacity) { // minCapacity = 0+1;
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // 空数组的情况下
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // 容量去 两者的最大值。这里就是 10
}
ensureExplicitCapacity(minCapacity); // 10
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 计数器
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity); //动态计算容量，当前 minCapacity = 10
}
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length; // 旧的数组长度
int newCapacity = oldCapacity + (oldCapacity >> 1); // 新的值 = 旧的值 + 旧的值/2 (1.5 倍)
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); //复制 原来 数组中的 元素 到 到新的元素中去。
}
- elementData = Arrays.copyOf(elementData, newCapacity);
/**
* Copies the specified array, truncating or padding with nulls (if necessary)
* so the copy has the specified length. For all indices that are
* valid in both the original array and the copy, the two arrays will
* contain identical values. For any indices that are valid in the
* copy but not the original, the copy will contain <tt>null</tt>.
* Such indices will exist if and only if the specified length
* is greater than that of the original array.
* The resulting array is of exactly the same class as the original array.
*
* @param <T> the class of the objects in the array
* @param original the array to be copied
* @param newLength the length of the copy to be returned
* @return a copy of the original array, truncated or padded with nulls
* to obtain the specified length
* @throws NegativeArraySizeException if <tt>newLength</tt> is negative
* @throws NullPointerException if <tt>original</tt> is null
* @since 1.6
*/
@SuppressWarnings("unchecked")
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
@SuppressWarnings("unchecked")
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
- System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength)); 复制 原来的数组到 新的数组中。
original ：原来的数组 值
第一个 0 : 复制开始的角标， 从0 开始
copy： 复制到目标数组
第二个0 ： 目标数组中开始 保存数据的脚本 ，从0 开始
Math.min(original.length, newLength) ：需要复制的元素的个数。
// 本地方法栈中的数据
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
上面的逻辑 完成了以下的事情：
- 当新添加数据是，重新计算 object 数组的大小，默认是 10 ，当容量超过10 后 ，会扩容为 15 （1.5 倍）
- 复制原来数组中的数据 到新的数组中，更新数组变量引用。
我们再回过头来看看这个代码：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
- elementData[size++] = e; 添加新元素到 Object[] 中，同时 size++ 。
上面这句话就完成了 一个元素 添加到 Object[]中 。
- 从上面代码也能分析出，在ArrayList 中 元素是有序存储的，新添加的元素总是在 集合的最后面。下面我们看看 在 指定的位置 插入 元素是怎么一回事。
我们从 线性表-数组的存储结构上看，在一个数组中 插入一个元素 是要移动 原来 元素的位置的，我们就来分析下，java 是怎么玩的
public void add(int index, E element) {
rangeCheckForAdd(index);
// 这句话 动态的扩容后 ，还将原来数组中的数据复制到了新的数组中。
ensureCapacityInternal(size + 1); // Increments modCount!!
// 这句话就是 将 index 后面包括 index 所在的元数 向后 移动一位，留出 位置。
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element; // 将元数 写入 index 位置
size++; // size 自增
}
我们发现 java 中 移动 元数 是 调用 本地方法栈中的方法。
上面我们分析了 两种add 方法，步骤都差不多，核心就是 动态扩容后，会将原来的 数据 复制到 新的object[] 中。
