1、前言
说到ArrayList，就不得不说Array。光看名字，还以为这2个是同一个东西。其实不然。
Array:指容量为固定的数组，常见的初始化方法如下：
String[] names = {"david","tom","kate"};
在声明的时候直接声明了内部元素，这样jvm就可以快速的分配给指定大小的空间。同时，看Array源码可知，Array的方法基本上都是native方法，其底层实现均为c/c++实现。
ArrayList:动态数组，允许新增、删除等操作，常见的初始化方法：
List<String> nameList = new ArrayList<>();
看完概念，我们开始正题，开始源码的解读。
2、与其他容器对比
与hashmap不同，ArrayList为集合的一种，来源自数据结构中的数组概念，与hashmap源自数据结构中的图概念不同。
我们先看ArrayList的uml图。
image
可以看出，ArrayList不仅实现了Cloneable、Serializable接口，还 实现了RandomAccess接口、List接口。
3、简述RandomAccess接口
在后续代码中，还可以看到RandomAccess这个接口。若实现了该接口，则表明该类可以进行下标式访问，类似于这样：
List<String> nameList = new ArrayList<>();
String david = names[0];
（这个会提示越界了）
4、成员变量分析
ArrayList的成员变量分析如下：
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空数组
private static final Object[] EMPTY_ELEMENTDATA = {};
//也是空数组，作用是在新增元素的时候用
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//数组
transient Object[] elementData;
//数组大小
private int size;
//数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//继承自AbstractList，用于fail-fast机制
protected transient int modCount = 0;
从成员变量来看，数组用transient修饰符修饰，作用应该是类似于hashmap的Node[]。
5、核心方法分析
5.1 容量扩增
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新空间分配直接扩大50%
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);
}
private static int hugeCapacity(int minCapacity) {
//这一点比较特殊,见下面分析
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
关于hugeCapacity的判断小于0则为溢出，由于在jvm内部是以反码存储的数据，首位为符号位，当容量扩增后，若溢出，首位则变为1，此时变为负数，则可以快速判断出是否溢出。
5.2 trimToSize 压缩空间
去掉多余的空对象，精简存储空间
public void trimToSize() {
modCount++;
//代码也写的很简洁，经常使用三元表达式
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
由上面的扩增容量可知，如果原始容量是100，在扩增容量后，那么分配的容量为150.但是实际上可能只存110个对象实例，那么此时调用这个方法，就可以节约一定的存储空间。不过若数组较大，那么操作可能会耗费一点时间。
5.3 fail-fast机制
这个其实在hashmap中也采取了类似机制，就是额外有一个成员变量，用于快速判断该实例是否有变化，若在进行迭代的时候有变更，那么就抛出一个并发修改异常(ConcurrentModificationException)。
5.4 indexOf 求 下标
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;
}
这段代码略过，用的比较多，没什么亮点。
5.5 新增一个元素
既然是数组，那么就有两种 新增的方式：指定特定的位置、向后插入。
向指定位置写入元素：
public void add(int index, E element) {
//下标检查，是否越界了
rangeCheckForAdd(index);
//扩增容量，同时改变modcount
ensureCapacityInternal(size + 1); // Increments modCount!!
//index后面的元素后移
System.arraycopy(elementData, index, elementData, index + 1, size - index);
//指定位置放置元素
elementData[index] = element;
//元素数量大小自增
size++;
}
向后插入一个元素:
public boolean add(E e) {
//扩大容量,修改modcount
ensureCapacityInternal(size + 1); // Increments modCount!!
//注意
//数组是从0开始的存元素的，而数组个数是从1开始计数的
//这个地方是往第size个位置上存元素
//再将元素个数加1
elementData[size++] = e;
return true;
}
从以上源码可以看出，向后插入一个元素不用进行元素的复制，自然效率要大于指定位置插入一个元素。
5.6 移除一个元素
同新增，也是分2种。
移除指定位置的元素：
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);
//这个与新增类似，但是是左自减运算，自己体会吧
//特地表明将该位置的置空，让gc回收空间
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
}
看到这个指定删除某个元素的代码，那么有人就会有疑问了，如果我里面有多个一样的元素，那这不是删不完吗？这个时候你得使用removeAll：
public boolean removeAll(Collection<?> c) {
//参数校验，仅判断c != null，感觉不太严谨
Objects.requireNonNull(c);
return batchRemove(c, false);
}
private boolean batchRemove(Collection<?> c, boolean complement) {
//常量数组，不允许再赋值,但是数组内部的元素允许自由移动、被重新赋值
final Object[] elementData = this.elementData;
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
//不包含该元素,则存到新数组,其实是位置前移
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//上面if内类型不匹配抛异常时，r与size不等
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
if (w != size) {
// clear to let GC do its work
//由于将已包含的元素前移了，那么不包含的元素都在后面，直接将后面的元素删掉
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
5.7 序列化
这个源码类似于hashmap，就不重复分析了。
5.8 其他
set、get方法比较简单， 就不分析了。
需要注意的是，arraylist继承的AbstractList覆写了hashcode和equals方法。
6 小结
总的来说，arraylist的源码比较简单，可供分析的内容不多。
网友评论