ArrayList
目录
一、基础常量以及结构
// 默认数组长度
private static final int DEFAULT_CAPACITY = 10;
// 数组容器
transient Object[] elementData;
// 长度设置成0的默认数组容器
private static final Object[] EMPTY_ELEMENTDATA = {};
// 默认的数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 容器现有元素数量
private int size;
ArrayList用到的存储结构就是数组，我们看常量有两个空的数组常量，为什么会有两个？（下面再说）
二、构造方法
初始化很简单，没有什么扩容阈值，就初始化一个数组，值得注意的就是默认的初始化和参数为0的初始化不太一样，用了两个不一样的空数组，就是上面说的两个空数组常量，所以这里猜测目的就是为了区分指定初始化容量为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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
三、add操作
有两个add方法
不带索引的： 1.扩容判断 2.尾部赋值
带索引的：1.下标校验 2.扩容判断 3.数组数据后移 4.指定位置赋值
源代码如下：
// 默认添加 直接数组尾部添加
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++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void ensureCapacityInternal(int minCapacity) {
// 当数组是无参构造方法生成的默认数组的时候，这里会给一个默认的数组大小 10
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// 容量大于数组长度 就扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
问题一：两个默认的常量空数组有什么作用？
用于区分指定0容量初始化和默认初始化两种情况，无参构造初始化的时候并没有初始化默认的数组长度为10，而是在第一次add操作的时候扩容里面判断赋值的，这里的判断就是通过两个数组的对比来实现的
指定0容量初始化：在第一次add操作后，数组长度为1
ArrayList<Object> objects = new ArrayList<>(0);
objects.add(1);
默认初始化：在第一次add操作后，数组长度为10
ArrayList<Object> objects = new ArrayList<>();
objects.add(1);
问题二：指定下标赋值的时候，数组数据是怎么移位的？
是利用最底层的**System.arraycopy()方法，常见的ArrayList.toArray()**方法也是利用的这个
源代码如下：
/**
* @param src 源数组
* @param srcPos 源数组起始位置
* @param dest 目标数组
* @param destPos 目标数组的起始位置
* @param length 源数组要复制的长度
*/
public static native void arraycopy(Object src, int srcPos,Object dest, int destPos,
int length);
这是个数组复制的方法，简单来说就是把源数组中的一段连续的数据截取出来，复制到目标数组的指定位置中，如下面例子：
Integer[] arr1 = { 1, 2, 3, 4, 5 };
Integer[] arr2 = new Integer[5];
System.arraycopy(arr1, 2, arr2, 3, 2);
System.out.println(Arrays.toString(arr2));
// 结果输出 arr2为：
[null, null, null, 3, 4]
从源数组中找出从下标2开始连续两个数，复制到目标数组的下标3处，ArrayList里面同理从原下标开始往后所有数据都复制，再赋值到数组原下标+1的位置，就完成了整体数据往后移一位的效果了
图示只是为了更好理解，不是原理图：
四、grow()扩容操作
这里需要注意的就是每次扩容都是原来的1.5倍，会创建一个新的数组，然后再利用System.arraycopy() 将原数据复制过去
源代码如下：
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)
newCapacity = hugeCapacity(minCapacity);
// 扩容需要将老数据转移到新数组上 原理上面说过了
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;
}
五、get 操作
这个不多说了，数组取值 简单的一批
源代码如下：
public E get(int index) {
// 下标校验 不能超过现有容量
rangeCheck(index);
// 根据下标数组取值
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
六、contains操作
遍历对比元素，以后要有人问怎么优化，二分查找法丢过去
源代码如下：
public boolean contains(Object o) {
// 下标存在即 true
return indexOf(o) >= 0;
}
//遍历取下标
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;
}
七、remove操作
利用System.arraycopy()，最后把尾部元素置null
源代码如下：
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;
}