ArrayList 源码解析
/**
* Default initial capacity.
* 默认的容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
从代码中可以看出ArrayList 底层实现是一个可以扩容的数组实现的。因为数组在内存中是一段连续的内存空间，比如 1 ，2，3，4 在内存中是连续的，所以查找和删除的时候比较快直接可以定位到。
上面说了，ArrayList会自动扩容，下面就看下是如何进行扩容的。扩容发生在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;
}
在add的时候会通过ensureCapacityInternal(size + 1)来确保添加一个元素内存大小够用。进入源码看下这个流程是怎么处理的。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 这里的minCapacity 就是传入的size +1
// 如果size +1 大于当前的列表长度就会进入grow
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 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;
// newCapacity = oldCapacity + oldCapacity / 2;
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:
// 扩容之后会把之前的数据copy 到新的空间
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
在grow方法里会把传入的size 和当前的大小进行比较，如果大于当前的list 长度就，就会扩容为当前大小+ 当前大小/2 的容量，然后把老数据copy 的新的空间。
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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++;
}
添加元素到指定位置，会把后面的数据进行后移。移动的过程也是for 循环 bs->write_ref_array_pre(dst, length);
Copy::conjoint_oops_atomic(src, dst, length);
拷贝也是个需要消耗性能的，所以在添加和删除需求比较多的场景下就要用用到链式结构，下面的章节会具体分析下链式的。查询arrayList效率还是很快的。
总结
综上所述，ArrayList增删慢查询快，适合在增加和删除比较少且查询比较多的环境下使用。
