基础知识参考了一个大佬的博客。内容很全，很有层次。
https://www.cnblogs.com/skywang12345/p/3308498.html
这里我主要是就自己的源码学习过程做一个笔记及总结。
源码的学习和查看顺序打算按照 非线程安全的集合 > 多线程相关 > 线程安全的集合 这样的顺序学习。
ArrayList
笔记基于博客 https://www.cnblogs.com/skywang12345/p/3308556.html + 自己阅读 JDK1.8 源码整理。
1. 继承关系
// List代表这是一个序列
// 基类AbstractList实现了一些与数据结构无关的通用方法
// RandomAccess接口提供了可以通过下表访问元素的功能，可以对比LinkedList,并没有实现该接口
// Cloneable是拷贝接口
// Serializable是序列化接口，代表该类可以被序列化成文件存储或发送
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
2. 成员变量
// 默认初始化容量，该参数其实就是为了预估使用者需要的大小，以便减少重新分配size的次数
private static final int DEFAULT_CAPACITY = 10;
// static final的对象，当ArrayList的size为空时，实际的elementData都指向这里
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 数据的实际存储方式是Object数组
transient Object[] elementData; // non-private to simplify nested class access
// 数据的实际大小
private int size;
3. 构造方法
- ArrayList()
// 初始化一个默认长度为10的ArrayList
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
- ArrayList(int)
// 初始化一个特定容量的ArrayList，这个initialCapacity也只是建议长度，ArrayList的实际size不取决于这个值
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];// 以容量大小创建数组
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;// 默认为0长度的数组
} else {// 小于0报错
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
- ArrayList(Collection<? extends E>)
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {// 将c中的数据转为数组存入elementData
// 这里注释说，c.toArray()方法不一定可以正确的返回Object数组
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {// 如果c的数据不存在,正常初始化
this.elementData = EMPTY_ELEMENTDATA;
}
}
可以看到，除非指定了容量大小，elementData会变成长度为容量大小的数组，否则，elementData都会被赋值为0长度的数组。
4. ArrayList 的 add() 方法
4.1 add(E)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // 添加前先确认容量
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 如果是初始化并且没分配过容量，先确定容量大小，此步骤保证数组大小在执行过add后不小于10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 返回目前size+1
return minCapacity;
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 如果需要的容量 大于 现实容量 说明需要扩容
// 此处可以看到如果Integer.Max再加1，无法满足条件，所以不执行扩容
// 相应的elementData[size++]会报数组越界的错误
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容操作 设置 新的容量=“(原始容量x3)/2 + 1”
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);
}
// 如果需要的容量大于int类型的最大值，就只去int的最大值
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
4.2 add(int, E)
public void add(int index, E element) {
rangeCheckForAdd(index);// index检查
ensureCapacityInternal(size + 1); // Increments modCount!!
// native方法 index位置的数据全部需要向后移动一位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
4.3 addAll(Collection<? extends E>)
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
4.4 addAll(int, Collection<? extends E>)
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
5. ArrayList 的 indexOf() 方法
通过索引遍历，使用equals来比较
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
5. ArrayList 的 get() 方法
public E get(int index) {
rangeCheck(index);// index检查
return elementData(index);
}
E elementData(int index) {
// 直接通过数组索引取值
return (E) elementData[index];
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
6. ArrayList 的 set() 方法
public E set(int index, E element) {
rangeCheck(index);// index检查
E oldValue = elementData(index);// 通过索引取值
elementData[index] = element;
return oldValue;
}
6. ArrayList 的 remove() 方法
// 通过索引移除元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;// 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;
}
// 直接移除元素
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
}
8. ArrayList 的 遍历方式
- 通过迭代器遍历
- 通过索引遍历
- 通过foreach遍历
运行结果：
iteratorThroughRandomAccess：3 ms
iteratorThroughIterator：8 ms
iteratorThroughFor2：5 ms
由此可见，遍历ArrayList时，使用随机访问(即，通过索引序号访问)效率最高，而使用迭代器的效率最低！
9. ArrayList 的 trimToSize() 方法
// 将当前容量值设为 实际元素个数
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
10. SubList
SubList内置了ArrayList对象，计做parent，同时存有offset,index等索引。操作SubList的数据会改变原本ArrayList的数据！
