共计 5499 个字符，预计需要花费 14 分钟才能阅读完成。
ArrayList 8 源码剖析
1、简介
- 汇合的底层是 Object[] 的数组，外部实现动静扩容
- 在内存中是间断的内存空间、并且依照程序进行存储的，所以在查找某个地位数据是很快的，往两头插入数据是很慢的。- 容许有空值存在，值也是齐全能够反复的，然而必须是同一类型的值。- 初始化大小为 10，但后续扩容时，波及的数组的复制，所以对系能是一种耗费，如果已知数据量多大的状况下，最好指定汇合的大小。2、实现的接口
（1）RandomAcess 接口
容许通用算法在利用于随机或程序拜访列表时扭转其行为以提供良好的性能。（2）Cloneable 接口
汇合能够实现接口和数据的克隆。（3）Serializable 接口
汇合反对被序列化，能够用于网络传输。3、属性
1、private static final int DEFAULT_CAPACITY = 10; // 示意汇合数组的默认大小为 10
2、private static final Object[] EMPTY_ELEMENTDATA = {}; // 空数组，当设置大小为 0 时用
3、private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 默认空参构造函数应用
4、transient Object[] elementData；数组的值
5、private int size; 以后数组的大小，也就是数组里蕴含的元素的个数 4、构造方法
（1）无参构造方法
public ArrayList() {// 就相当于 elementData = {}
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}（2）指定初始化大小的构造方法
public ArrayList(int initialCapacity) {if (initialCapacity > 0) {
// 当初始化大小大于 0，则间接赋值
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {// 当初始化大小等于 0 时，== {}
this.elementData = EMPTY_ELEMENTDATA;
} else { // 否则参数谬误
throw new IllegalArgumentException("Illegal Capacity:"+
initialCapacity);
}
}（3）引入另一个汇合的构造方法
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;
}
}5、执行增加操作
（1）一般增加数据
public boolean add(E e) {
// 先对以后数组的大小 +1，而后进行判断是否须要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 在数组最末地位填充值
elementData[size++] = e;
return true;
}（2）向指定地位增加数据
public void add(int index, E element) {
// 这个办法用来判断增加的地位是否越界（正当的地位应该：< size、>0）rangeCheckForAdd(index);
// 先对以后数组的大小 +1，而后进行判断是否须要扩容
ensureCapacityInternal(size + 1);
// // 将 index 地位之后的数据往后移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 挪动完之后 index 还是老的值，而后新值间接笼罩
elementData[index] = element;
// 长度加 1
size++;
}
（3）扩容操作
// 办法 1：扩容入口
private void ensureCapacityInternal(int minCapacity) {ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 查看以后的数组大小，如果第一次存，则间接返回初始值 10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断以后是否是一个空的汇合，第一次数组里还啥也没有，就将默认的 10 和以后传过来的数（以后数据长度 size + 1）if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
// 第一次都返回 10
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 如果以后数组不是空的，间接返回以后数组长度 + 1
return minCapacity;
}
// 办法 2:
private void ensureExplicitCapacity(int minCapacity) {
modCount++; // 对数据的操作次数 + 1
// size 加 1 之后的值与数组总长度进行比拟，如果加 1 之后的数组的个数大于总长度，则须要扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 办法 3：扩容
private void grow(int minCapacity) {
// 先获取旧数组的总长度，比方是 10
int oldCapacity = elementData.length;
// 新长度 = 旧长度 + 旧长度 /2（即：新的 = 旧的 * 1.5）int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果扩容 1.5 倍之后还小于 size + 1 的值
if (newCapacity - minCapacity < 0)
// 新长度 = size + 1
newCapacity = minCapacity;
// 新长度大于 Integer.MAX_VALUE - 8 么？if (newCapacity - MAX_ARRAY_SIZE > 0)
// 扩容到最大值时（int.Max - 8）时返回 int 的最大值，示意再也不能扩容了
newCapacity = hugeCapacity(minCapacity);
// 创立完新的数组，而后实现数据复制。elementData = Arrays.copyOf(elementData, newCapacity);
}
通过这个过程你应该了解，在创立 list 的时候尽可能的指定汇合的大小，防止频繁的扩容。6、执行删除操作
（1）依据下标删除
public E remove(int index) {
// 判断下标是否符合标准
rangeCheck(index);
modCount++;
// 获取到旧值，删除胜利后返回
E oldValue = elementData(index);
// 获取须要挪动的元素的个数（数组元素个数 - 以后地位）int numMoved = size - index - 1;
if (numMoved > 0)
// 将以后地位往后的一位数到数组的最初一位数对立往前挪动一位，那以后地位的元素就被 index + 1 的元素笼罩掉了。System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将数组最初一地位空
elementData[--size] = null;
return oldValue;
}
留神：这个操作没有遍历数组所以复杂度是 o(1（2）依据内容删除
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;
}
}
// 如果值不存在间接返回 false
return false;
}（3）fastRemove(index)
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
// 将以后地位往后的一位数到数组的最初一位数对立往前挪动一位，那以后地位的元素就被 index + 1 的元素笼罩掉了。System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}（4）在循环遍历删除
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(5);
list.add(9);
list.add(0,999);
System.out.println(list);
for (Integer num : list){if(num == 9){list.remove(num); // 会报错：java.util.ConcurrentModificationException
}
}
Result：下面这个代码报错的起因是因为在遍历之前就曾经把以后汇合的操作数赋值给一个预期操作数的变量，执行 remove 之前会把以后的操作指令数 + 1，而后以后操作数会跟预期操作数进行比拟，如果不统一就会报上述谬误，总而言之就是在扭转汇合之前先对以后操作数进行批改了。
So：怎么正确删除汇合的元素呢？
List<Integer> list = new ArrayList<>();
list.add(3);
list.add(5);
list.add(9);
list.add(0,999);
System.out.println(list);
// 先将汇合变成 iterator
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()){Integer num = iterator.next();
if(num == 5){iterator.remove();
}
}
System.out.println(list);7 查问操作
public E get(int index) {
// 查看 index 大小是够正当（0<= x <= size）rangeCheck(index);
// 注解返回 elementData[index] 的值
return elementData(index);
}8 汇合清空
public void clear() {
modCount++;
// 循环删除所有元素
for (int i = 0; i < size; i++)
elementData[i] = null;
// 长度置为 0
size = 0;
}
// 这里数组的总长度没有变 总结面试题：
1、ArrayList 的初始化大小事几？
答：102、ArrayList 扩容后的长度是多少？
答：原来长度的 1.5 倍 3、ArrayList 增加和查找元素的工夫复杂度是多少？
答：都是 O(1)4、ArrayList 是线程平安的么？会有什么问题？有线程平安的 List 吗？
答：不是线程平安的的，会有很多问题，比方反复赋值、反复扩容等，线程平安的 List 有 Vector、CopyOnWriteArrayList。5、ArrrayList 和 LinkedList 有什么区别？
答：（1）构造不同，ArrayList 底层是基于数组实现的，所以在内存中数据存储是间断的。而 LinkedList 底层是基于链表实现的，所以内存中的数据可能是间断的也可能是不间断的。（2）场景不同，ArrayList 因为是内存间断的数组，所以它反对随机拜访，当咱们须要拜访某个地位的数据时，ArrayList 可间接获取，LinkedList 则须要遍历链表获取，在这个过程中寻址是很慢的。当须要向两头地位新增某一个值的时候，因为 ArrayList 是间断的内存则须要将所增加地位之后的所有元素后移，留出一个地位来寄存增加元素，而 LinkedList 链表只须要批改增加地位的元素的前后指针就能够了，删除和批改相似。所以对于随机拜访 ArrayList 效果显著，当增删改时，LinkedList 的效果显著。注：增删改时 ArrayList 到底比 LinkedList 慢多少，这个得看电脑配置。我用 MacBookPro 17 款 4 核 16G 内存的电脑，在 200 万长度之前是一样的，前面开始越多越慢，在 300 万和 3000 万时对 5001 地位新增，ArrayList 别离慢 1ms 和 10ms.
正文完