1.前言
ArrayList 是我们常用的数据结构，但是你对ArrayList了解有多少了？不妨来考一考自己。
2.ArrayList每日一问（答案见末尾）
（1）jdk1.8ArrayList默认容量是多大？
（2）ArrayList 扩容多大？
（3）ArrayList 是线程安全的吗？为什么？
（4）ArrayList 中 elementData 为什么使用 transient 修饰？
（5）ArrayList list = new ArrayList(20); 中的list扩充几次？
如果你对以上的问题全部都能答对，嗯，确认过眼神，大佬喝茶~
如果没有答对，也不要灰心，我们来一起学一学ArrayList
3.ArrayList底层分析（基于jdk1.8）
面试造火箭，开发拧螺丝，实际我们大多数都是在CRUD，ArrayList也不例外，我们就从ArrayList的CRUD展开
3.1 ArrayList的成员变量
//默认的容量
private static final int DEFAULT_CAPACITY = 10;
//空数组实例
private static final Object[] EMPTY_ELEMENTDATA = {};
//默认大小的空数组实例，这里有的同学问了，和上面的那个有什么区别吗?
//官方解释的是:与上面的实例分开，以至于我们知道何时会添加第一个元素
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//Object数组，也就是ArrayList的底层
transient Object[] elementData
//大小
private int size;
3.2 ArrayList的构造方法
无参的构造方法，这里我们看到无参的构造函数，也就是当我们不给ArrayList的大小时，ArrayList会是一个空数组
//这里我们看到初始了一个空数组
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
带初始化容量的构造方法
//1.如果初始化的值大于0，直接new一个initialCapacity的Object数组
//2.如果等于0，会是一个上面成员变量中的第一种,EMPTY_ELEMENTDATA
//3.小于0，会跑出IllegalArgumentException异常
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);
}
}
Collection类型的构造器
//1.将Collection的集合转换成数组,ArrayList底层
//2.如果c.toArray()不是一个Object数组，使用Arrays.copyOf方法进行转换
//3.如果c.toArray()的长度等于0，使用自己的成员变量
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
3.3 ArrayList add方法(分为两种)
直接添加
(1)判断是否个空数组，如果是空数组，就给默认值
(2)判断是否需要扩容
(3)正式扩容
(4)添加元素
//是否需要扩容
//添加元素
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//如果elementData，是个空数组的话，minCapacity也就是为1
//这里会取默认的大小：10，类似懒加载，默认是个空数组，当我们
//第一次添加时就会给个默认大小10,
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
//确定是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
//真正的扩容代码
//旧数组容量+旧数组容量右移一位=1.5倍
// 检查新容量的大小是否小于最小需要容量，如果是的，新容量等于最小需要容量
//如果新容量大于MAX_ARRAY_SIZE，使用hugeCapacity比较二者
//使用Arrays.copyOf 进行拷贝
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);
}
//对minCapacity和MAX_ARRAY_SIZE进行比较
//若minCapacity大，将Integer.MAX_VALUE作为新数组的大小
//若MAX_ARRAY_SIZE大，将MAX_ARRAY_SIZE作为新数组的大小
//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;
}
指定位置添加，就好比我们插队一样，需要在中间挪出一个位置才能进去,上面如果理解了，这里就比较好理解，就多了一个判断,判断有没有超过最大值，然后调用System.arraycopy进行拷贝
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
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));
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-UOEAi0zc-1597248035484)(http://52jdk.com/ArrayListAdd.png)]
3.4 get方法(两行代码)
第一步判断下表是否越界，第二步直接通过数组下表获取元素
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
3.5 remove方法(两种方法)
按照下标remove
(1) 判断下标是否越界，如果越界就会直接抛出异常
(2) 在数组中查询该元素
(3)计算需要移动的数目
(4)如果numMoved大于0,说明要删除的元素后面的都需要左移，如果是最后一个元素，则不需要移动
(5)使原数组大小减一，并赋值为空，有利于GC
(6)返回旧的元素
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;
}
//src:源数组
//srcPos:从源数组的srcPos位置处开始移动
//dest:目标数组
//desPos:源数组的srcPos位置处开始移动的元素，这些元素从目标数组的desPos处开始填充
//length:移动源数组的长度
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
按照元素值来删除，这里也比较好理解，就是先遍历，获取元素的下标，然后利用上面的删除代码进行删除
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
}
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-TTmIOap9-1597248035486)(http://52jdk.com/ArrayList%20remove.png)]
3.6 ensureCapacity 方法
这个方法可以在 add 大量元素之前用 ensureCapacity 方法，以减少增量从新分配的次数
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
3.7 writeObject和readObject
ArrayList 为什么要定义这两个读写流的方法呢，这就要回到我们第四个问题了，
ArrayList 中 elementData 为什么使用 transient 修饰？
由于 ArrayList 是基于动态数组实现的，所以并不是所有的空间都被使用。因此使用了 transient 修饰，可以防止被自动序列化。
因此 ArrayList 自定义了序列化与反序列化，具体可以看 writeObject 和 readObject 两个方法。
需要注意的一点是，当对象中自定义了 writeObject 和 readObject 方法时，JVM 会调用这两个自定义方法来实现序列化与反序列化。
writeObject 官方解释（意思是：通过流来序列化ArrayList）
/**
* Save the state of the ArrayList instance to a stream (that
* is, serialize it).
*
* @serialData The length of the array backing the ArrayList
* instance is emitted (int), followed by all of its elements
* (each an Object) in the proper order.
*/
readObject 官方解释 (意思是：通过流来反序列化ArrayList)
/**
* Reconstitute the ArrayList instance from a stream (that is,
* deserialize it).
*/
4.答案
jdk1.8如果不给初始值容量的话，是默认给了一个空数组，也就是0，当在第一次添加时，会重新比较大小，给10的容量
ArrayList 扩容1.5倍，记住右移一位：newCapacity = oldCapacity + (oldCapacity >> 1)
ArrayList不是线程安全的，当我们add添加或者删除时，elementData[size++] = e; elementData[–size] = e; 这两个操作，并不是原子操作，都是分为两步操作
3.7咋们已经分析到了
默认ArrayList的长度是10个，所以如果你要往list里添加20个元素肯定要扩充一次（newCapacity 扩充为原来的1.5倍，但和输入的minCapacity相比发现小于minCapacity，于是 newCapacity = minCapacity，所以只扩容一次，具体见扩容里的grow方法），但是这里显示指明了需要多少空间，所以就一次性为你分配这么多空间，也就是不需要扩充了！
5.提问
为什么添加删除操作都有 modCount++ ，有什么作用，相信聪明的你已经知道了答案，欢迎在评论区留言
6.关于
程序员小R:非专业咖啡调制师，公众号“程序员小R”，回复“666”获取1000页的最新面经题