前言
- ArrayList是大家代码中经常使用的数据结构，但是ArrayList底层是怎么实现的，大家知道吗？
- 今天带大家对ArrayList源码进行剖析，了解其底层数据结构。
目录
捕获.PNG
1.概述
先来学习一下官方文档：
Resizable-array implementation of the <tt>List</tt> interface. Implements
all optional list operations, and permits all elements, including
<tt>null</tt>. In addition to implementing the <tt>List</tt> interface,
this class provides methods to manipulate the size of the array that is
used internally to store the list. (This class is roughly equivalent to
<tt>Vector</tt>, except that it is unsynchronized.)
- 动态数组，会自动扩容，允许元素为null。
- ArrayList不是同步的，也就是说不是线程安全的，要实现同步可以使用Vector或者调用Collections的相关方法：
List list = Collections.synchronizedList(new ArrayList(...))
2.源码分析
2.1 关键成员变量解释
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//空数组, 当用户指定该 ArrayList 容量为 0 时，返回该空数组
//例如：ArrayList<String> a = new ArrayList<String>(0);
private static final Object[] EMPTY_ELEMENTDATA = {};
//空数组，当调用ArrayList的无参构造函数时，返回该空数组
//例如：ArrayList<String> a = new ArrayList<String>();
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//真正用于存储数据的数组
transient Object[] elementData;
//数组中元素的个数，注意不是数组的长度
private int size;
2.2 构建方法分析
//传入初始初始容量，根据初始容量进行处理：大于0则创建长度为initialCapacity的数组，并赋值给elementData；
//等于0则把空数组EMPTY_ELEMENTDATA赋值给elementData；小于0则抛出参数非法的异常。
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，此时其内数组缓冲区 elementData = {}, 长度为 0
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
2.3 add() 方法解析
- add方法是了解集合底层结构的关键，通过分析元素的插入过程能过够知道底层的实现。
public boolean add(E e) {
// 动态扩容的关键
ensureCapacityInternal(size + 1); // Increments modCount!!
//在size+1的位置进行赋值
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//使用无参构造函数创建ArrayList实例时第一次调用add()会进入这里，初始容量为10，
//第二次调用add()就不会了，原因是： 第一次调用add()方法时会
//调用elementData = Arrays.copyOf(elementData, newCapacity)，此时elementData 会指向新的数组，不是指向DEFAULTCAPACITY_EMPTY_ELEMENTDATA
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//第一次调用add()时，minCapacity = 10，lementData.length = 0，调用grow方法
//第二次调用add()时，minCapacity = size + 1，等于2，而elementData.length =10，不会调用grow方法。以此类推。
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
private void grow(int minCapacity) {
// overflow-conscious code
//每次扩容新的数组长度是原来的1.5倍
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
//调用add()只能增加一个元素，但是扩容后数组长度是原来的1.5倍，通常情况下不会出现newCapacity - minCapacity < 0的情况，
//出现这种情况的原因有：
//1.无参构造函数第一次调用add()时，此时newCapacity = 0，minCapacity = 10；之后再也不会出现这种情况了
//2.有参构造参数初始容量 = 0 ，然后前2次调用add()时，或者初始容量 = 1，第一次调用add时，具体原因思考一下就明白了
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//判断数组长度是否超出MAX_ARRAY_SIZE
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//创建一个长度为newCapacity的新数组，并把数组的数据复制在对应的位置上
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
Arrays.copyOf 方法
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")
//根据class的类型是否是 Object[] 来决定是 new 还是反射去构造一个长度为newLength的数组
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
//将数组数据复制新创建的数组中，复制的长度为Math.min(original.length, newLength)，避免数组越界
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));
return copy;
}
2.4 get()方法解析
public E get(int index) {
//检测范围
rangeCheck(index);
//返回下标为index的元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
3.与Vector比较
3.1 构造函数比较
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
public Vector() {
this(10);
}
无论调用哪个构造函数最终都会调用Vector(int initialCapacity, int capacityIncrement)，其中initialCapacity为初始容量，capacityIncrement为每次数组扩容增加的数组长度，由此可以发现有2处不同的地方：
Vector调用无参构造时直接初始话一个长度为10的数组，而ArrayList调用无参构造函数时初始化一个空数组，直到首次调用add()方法才创建一个长度为10的数组
Vector可以指定每次扩容增加多少长度，而ArrayList无法指定
3.2 add()方法比较
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
private void ensureCapacityHelper(int minCapacity) {
// 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 + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
- Vector的add（）方法使用关键字synchronized 修饰，所以是线程安全的，而ArrayList不是线程安全的，其实除了add方法，几乎Vector的所有方法都使用synchronized修饰，Vector是线程同步的，但是效率很低，一般不赞成使用。
- Vector扩容多少根据capacityIncrement而定，capacityIncrement为0时则数组长度变为原来的两倍，不为0则在原来的数组长度上增加capacityIncrement，而ArrayList每次扩容长度变为原来的1.5倍
总结
- ArrayList底层是动态数组，，每次扩容数组长度变为原来的1.5倍。
- ArrayList按数组下标访问get(i)，或者在末尾插入元素，效率很高，但是在中间位置删除元素，插入元素，以及扩容都需要调用System.arraycopy()来操作元素，性能比较差。
