今天看了下ArrayList作为自己读源码的第一步。ArrayList从名字可以知道底层是由数组实现的。而作为Collection的大家庭一员，可以说是很基础的集合了。
1.什么是ArrayList
ArrayList 底层是一个动态数组，大小是可变的。它实现了List接口，允许null添加进来。有以下几点注意：
- 每个ArrayList实例都会有一个容量capacity用来存储元素数组的大小。默认是10
- 同时会有一个size属性，来记录当前ArrayList中的个数。
- 随着元素增加，容量也不断增长，需要检查是否需要，当size == capacity 就需要扩容啦
- 扩容操作就是将原来数组中的内容进行拷贝。
- 所以我们知道具体数量的话，应赋给一个默认值，减少拷贝的，因为拷贝是需要消耗资源的
2.我们来看看ArrayList的源码
2.1.底层使用数组
private transient Object[] elementData;
由此可以看出底层是一个数组 transient 关键字：
当对象存储时，它的值不需要维持。Java的serialization提供了一种持久化对象实例的机制。当持久化对象时，可能有一个特殊的对象数据成员，我们不想用serialization机制来保存它。为了在一个特定对象的一个域上关闭serialization，可以在这个域前加上关键字transient。当一个对象被序列化的时候，transient型变量的值不包括在序列化的表示中，然而非transient型的变量是被包括进去的。(可以参考)
2.2构造
/**
* 构造一个具有指定初始容量的空列表。
*/
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity);
this.elementData = new Object[initialCapacity];
}
/**
* 构造一个初始容量为 10 的空列表
*/
public ArrayList() {
this(10);
}
构造基本上是对ArrayList进行初始化操作，默认是10
2.3新增 add操作
public boolean add(E e) {
//检测扩容
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
新增元素也就是在数组的末尾新增元素。这里ensureCapacity()方法是对ArrayList集合进行扩容操作
public void add(int index, E element) {
//判断索引位置是否正确
if (index > size || index < 0)
throw new IndexOutOfBoundsException(
"Index: "+index+", Size: "+size);
//扩容检测
ensureCapacity(size+1);
/*
* 对源数组进行复制处理（位移），从index + 1开始，长度为size - index
* 主要目的就是空出index位置供数据插入，
* 即向右移动当前位于该位置的元素以及所有后续元素。
*/
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//在指定位置赋值
elementData[index] = element;
size++;
}
- add方法本质上是，arraycopy()这个复制数组的方法。
- 这是非常麻烦和耗时的，
- 所以如果指定的数据集合需要进行大量插入（中间插入）操作，推荐使用LinkedList。
2.4删除操作
remove(int index)
public E remove(int index) {
//位置验证
RangeCheck(index);
modCount++;
//需要删除的元素
E oldValue = (E) elementData[index];
//向左移的位数
int numMoved = size - index - 1;
//若需要移动，则想左移动numMoved位
if (numMoved > 0)
System.arraycopy(elementData, index + 1, elementData, index,
numMoved);
//置空最后一个元素
elementData[--size] = null; // Let gc do its work
return oldValue;
}
由源码可以知道删除的操作本质上还是index+1开始长度为 size - index -1 到 ，然后复制到新的数组里，然后最后一个元素置空，由GC处理掉
remove(Object o)移除此列表中首次出现的指定元素（如果存在）。
public boolean remove(Object o) {
//因为ArrayList中允许存在null，所以需要进行null判断
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;
}
ArrayList是可以存null，因此需要null判断，其余的只要用equals进行匹配即可其中
其中fastRemove()方法用于移除指定位置的元素。如下：
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; // Let gc do its work
}
modCount 表示的是修改次数，根据线程不安全的话可以判断其他线程是否修改了该集合的元素，如果modCount和存储的mcount不一样那就抛异常 。因此推荐迭代器遍历
2.5查找
public E get(int index) {
RangeCheck(index);
return (E) elementData[index];
}
}
由此可以看出来ArrayList 查找元素是很快的，只需要把索引赋值进去就可以啦，时间复杂度为O（1）
2.6关键的地方：扩容
- 在上面的新增方法的源码中我们发现每个方法中都存在这个方法：ensureCapacity()，
- 若新增元素后元素的个数会超过ArrayList的容量，就会进行扩容操作来满足新增元素的需求。
- 所以当我们清楚知道业务数据量或者需要插入大量元素前，我可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。
public void ensureCapacity(int minCapacity) {
//修改计时器
modCount++;
//ArrayList容量大小
int oldCapacity = elementData.length;
/*
* 若当前需要的长度大于当前数组的长度时，进行扩容操作
*/
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
//计算新的容量大小，为当前容量的1.5倍
int newCapacity = (oldCapacity * 3) / 2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
//数组拷贝，生成新的数组
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
}
1.5倍考虑到资源的分配不会浪费很多资源也不会，也能够满足性能的需求
网友评论