关于java:Debug-ArrayList源码

1，ArrayList 面试必问

• 说说 ArrayList 和 LinkedList 的区别？

  ArrayList 基于数组实现，LinkedList 基于链表实现，不同的数据结构决定了 ArrayList 查问效率比拟高，而 LinkedList 插入删除效率比拟高，反过来就比较慢了。

• ArrayList 默认初始容量为多少？依照几倍来扩容？

  10，1.5 倍。

• 说说数组扩容的原理？

  ArrayList 扩容调用的是 Array.copyof 函数，把老数组遍历赋值给新数组返回。

• 说说 ArrayList 常见办法的工夫复杂度？

  • get 办法通过下标获取元素，工夫复杂度为 O（1）
  • add 办法间接增加会增加到汇合的尾部，工夫复杂度为 O（1）
  • add 办法通过下标增加到非尾部会引起数组的批量挪动，工夫复杂度为 O（n），否则为 O（1）
  • remove 办法通过下标删除非尾部元素引起数组批量挪动，工夫复杂度为 O（n），反之则为 O（1）
  • remove 办法依据对象删除须要遍历汇合，工夫复杂度为 O（n），如果删除的为非尾部元素，会使数组批量挪动，工夫复杂度为 O（n^2）

 总之，通过下标操作的工夫复杂度为 O（1），如果触发了数组的批量挪动，工夫复杂度为 O（n），如果通过对象操作须要遍历汇合，工夫复杂度曾经为 O（n），若同时触发了数组的挪动，工夫复杂度为 O（n^2）.

• ArrayList 和 vector 的区别

  • 最大的区别在于线程是否平安
  • 其次 Vector 是两倍扩容
  • 最初就是在不指定大小的状况下，ArrayList 容量初始化是在增加元素的时候，而 Vector 有一个无参结构器间接初始化为 10

2，Debug ArrayList 源码

因为 1.7 和 1.8 简直没什么变动，本文以 jdk1.8 为例。

2.1 用 Debug 剖析一个元素是如何 add 进 ArrayList

编写测试用例，打上断点：

先剖析构造函数如何初始化，关键步骤如下：

elementData 是 ArraList 底层数组的实现，（ps：hashMap 数组应用 table 命名）

DEFAULTCAPACITY_EMPTY_ELEMENTDATA 示意默认的空数组，也就是说 ArrayList 在构造函数初始化时并不会进行底层数组的初始化。

给元素的增加打上断点，剖析过程：

进入 add 办法外部：

public boolean add(E e) {
// 确保外部容量，在元素增加进来前可能要进行扩容操作，size 初始化为 0，示意汇合的长度
ensureCapacityInternal(size + 1); // Increments modCount!!
// 增加元素，size 自增
elementData[size++] = e;
return true;
}

进入 ensureCapacityInternal 办法外部：此时 elementData 为空，size+1=minCapacity=1

ensureExplicitCapacity：确保明确的能力

计算容量，calculateCapacity 办法：

private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 判断数组是否为空，若为空，返回默认容量和最小容量的最大值，若不为空，返回最小容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}

DEFAULT_CAPACITY 默认容量为 10：

持续剖析，进入：

ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); 此时参数为 10，也就是 ArrayList 的默认容量

private void ensureExplicitCapacity(int minCapacity) {
modCount++;   // 汇合的批改次数
​
// 如果最小容量减去数组长度大于 0，进行扩容，此时最小容量为 10，数组长度为 0
if (minCapacity – elementData.length > 0)
grow(minCapacity);
}

外围扩容函数 grow：（ps：HashMap 中扩容函数为 resize）

private void grow(int minCapacity) {
//oldCapacity：旧数组容量
int oldCapacity = elementData.length;

// 新容量等于旧容量加上旧容量的一半,>>1 相当于除以 2（ArrayList 扩容是 1.5 倍）
int newCapacity = oldCapacity + (oldCapacity >> 1);

// 新容量小于最小容量，则赋值为最小容量，此时 newCapacity 等于 0，minCapacity 为 10
if (newCapacity – minCapacity < 0)
newCapacity = minCapacity;

//MAX_ARRAY_SIZE = Integer.MAX_VALUE – 8
if (newCapacity – MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 赋值给新数组
elementData = Arrays.copyOf(elementData, newCapacity);
}

数组复制 Arrays.copyOf：

2.2 用 Debug 剖析如何通过数组下标获取 ArrayList 元素

打上断点，debug：

首先进行范畴查看，而后返回元素

2.3 用 Debug 剖析如何通过数组下标删除一个元素

打上断点：

进入 remove 办法外部，

public E remove(int index) {
// 下标范畴查看
rangeCheck(index);
// 批改次数自增
modCount++;
// 保留以后删除元素的值，稍后返回
E oldValue = elementData(index);
// 须要挪动元素的个数
int numMoved = size – index – 1;
if (numMoved > 0)
// 底层应用 native 办法，debug 进不去。native 办法：java 调用其余语言的接口
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 最初一地位空
elementData[–size] = null; // clear to let GC do its work
// 返回删除元素的值
return oldValue;
}

2.4 用 Debug 剖析如何通过对象删除一个元素

进入 remove 办法：

public boolean remove(Object o) {
// 如果对象为空，则遍历 ArrayList 汇合
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;
}

进入 fastRemove 办法：

private void fastRemove(int index) {
modCount++;

//numMoved：须要挪动数组的个数
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 wrk
}

2.5 用 Debug 剖析向数组两头增加元素

进入 add 办法

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++;
}

对于 System.arraycopy 工夫复杂度问题，在增加或者删除最初一个元素的时候不会触发数组的复制机制，工夫复杂度为 O（1），若是增加到数组两头，因为会触发数组的复制，工夫复杂度为 O（n）。对于删除元素同样，依据数组下标删除的状况下，删除尾部元素是不会触发数组的扩容机制的，若删除两头的元素，同样会触发数组的复制。若依据对象删除元素，因为自身遍历到对象的工夫复杂度为 O（n），删除元素后再对数组进行重组，所以工夫复杂度为 O（n^2）。