序言
序言包含了引入和基于注释的介绍，可以跳过序言进入正文
List<Object> name = new ArrayList();
List 在 Java 中的使用频率可谓非常之高，这次就初步探究下其实现
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{...}
可以看到，List 是一个接口，ArrayList 是 List 的一个实现类，还提供了可序列化和可克隆
JDK中对 ArrayList 的注释包括如下：
ArrayList的定义为：
Resizable-array implementation of the List interface.
即，一个实现了List接口大小可变的数组！
有一个追加的描述：
This class is roughly equivalent to Vector, except that it is unsynchronized.
讲述了 ArrayList 和类 Vector 的实现类似。区别在于 ArrayList 是线程不安全的，对类 Vector 有了解的话可以对比两者的实现
Each ArrayList instance has a capacity.The capacity is the size of the array used to store the elements in the list.As elements are added to an ArrayList, its capacity grows automatically.
ArrayList 内部有一个 capacity，它存储了 ArrayList 数组的大小，ArrayList 是一个大小可变的数组，意味着capacity会随着 elements 的增加而增加
关于capacity需要了解的是
An application can increase the capacity of an ArrayList instance before adding a large number of elements using the ensureCapacity operation. This may reduce the amount of incremental reallocation.
增加大量的节点时，可以使用 ensureCapacity 方法，它会有效的减少 capacity 大小改变时再分配次数
需要特别注意的是
Note that this implementation is not synchronized.If multiple threads access an ArrayList instance concurrently and at least one of the threads modifies the list structurally, it must be synchronized externally.
ArrayList 是一个非线程安全的类，多线程访问且需要修改其结构时，如需要扩容 capacity，需要在外部实现同步，或者使用官方推荐的形式实现同步，如下
List list = Collections.synchronizedList(new ArrayList(...));
The iterators returned by this class's {@link #iterator() iterator} and {@link #listIterator(int) listIterator} methods are <em>fail-fast</em>: if the list is structurally modified at any time after the iterator is created, in any way except through the iterator's own {@link ListIterator#remove() remove} or {@link ListIterator#add(Object) add} methods, the iterator will throw a {@link ConcurrentModificationException}.
在 ArrayList 中，可通过特定的方法获取 Iterator，它实现了一个特别的 fail-fast 机制，即快速失败。触发条件是获取到 Iterator 后 ArrayList 的结构发生变化，当快速失败触发时，除非通过指定的方法，否则会抛出 ConcurrentModificationException 异常
关于 Iterator 的补充
Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.
官方特别提示，Iterator 不应该用来实现程序逻辑，而是应该用于检测错误
正文
1.参数
2.构造方法
3.基本操作
Note：代码非源码，去除了判断和无关代码，保留主要逻辑
1.参数
//非空情况下容器的初始大小
private static final int DEFAULT_CAPACITY = 10;
//ArrayList 允许的最大存储数量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//ArrayList 中实际存储的节点数
private int size;
//ArrayList 中实际用于存储数据的数组
transient Object[] elementData;
2.构造方法
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
无参构造初始化 elementData 为空数组
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else ...
}
参数类型为int的构造把 elementData 实例化为一个参数长度的数组
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();//相当于实例化elementData
if ((size = elementData.length) != 0) //相当于实例化size
...
}
以 Collection 为类型的参数的构造获取参数的数据实例化数组和size
3.基本操作
3.1 add
3.2 get
3.3 set
3.4 other
3.1 add
public boolean add(E e) {
modCount++;//记录修改次数
//数组节点用完，需要扩容
if (s == elementData.length)
elementData = grow(size + 1);
//存储核心逻辑elementData和size
elementData[size] = e;
size = size + 1;
return true;
}
//扩容函数，调用Arrays.copyOf(...)实现
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
/* 新数组大小 */ newCapacity(minCapacity));
}
//计算新数组大小
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新数组大小计算规则
int newCapacity = oldCapacity + (oldCapacity >> 1);
//数组为空且add节点时触发，初始化数组的长度为10
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return newCapacity;
}
对于刚刚实例化的，且使用的是无参的构造方法，elementData 数组初始容量为空，第一次add()时会触发数组扩容，初始大小为10，后续的扩容遵循 x + (x >> 1)这样的计算方式
注释中提到的 ArrayList 拥有的 capacity 在源码中的表现形式是 elementData.length，通过size与capacity的对比，判断是否需要扩容，再进行size位置的插入，然后以size++结束
当然，add()的插入还是能指定位置的，毕竟是数组嘛，很简单的实现
public void add(int index, E element) {
...
//把指定位置之后的数据往后移
System.arraycopy(elementData, index,
elementData, index + 1,
s - index);
//插入指定位置
elementData[index] = element;
size = s + 1;
}
3.2 get
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
很直白，直接获取数组指定位置的数据，当然少不了对参数位置的判断，add中忽略掉，这里代码少保留了
3.3 set
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
JDK中很保守的做法，参数判断，替换新值，返回旧值
3.4 other
其他的诸如 isEmpty、size等的实现就是简单的对数组和size进行操作
后记
往后还可以分析ArrayList 的可克隆，可序列化还有迭代器的实现，还有其最大的问题，线程不安全，有时间再完成接下来的分析！
网友评论