阅读优秀的源码是提升编程技巧的重要手段之一。
如有不对的地方，欢迎指正~
转载请注明出处http://www.imooc.com/u/125243。
前言
当你对某件事情很感兴趣的时候，时间的流逝在感知中都模糊了（是不是很文艺，绕口得都快听不懂了），通俗来说，就是时间过得很快。
而且，只有感兴趣才能驱动你继续下去，不然读源码，写解析博客这么高(Ku)大(Zao)上的事，是很难坚持的。
详细地写一篇源码解析博客少则半天一天，比如本篇，多则几天，比如红黑树在Java - HashMap中的应用，又要画图又要注释，还要排版，时不时要加点表情，开个车什么的，你说要是没兴趣，怎么坚持呢，还不如吃个鸡实在(啊，暴露了我是吃鸡选手)。
闲话少说，打开你的IDE，挽起袖子，开撸代码，加上注释，总计1461行代码。
基本介绍
常量
相比HashMap来说，ArrayList的常量算是短小精悍了，只有几个。
其中包含一个默认容量和两个空数组等，如下。
/**
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空数组共享实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 缺省大小的空数组共享实例
* 与 EMPTY_ELEMENTDATA 区分开来，以便知道第一个元素添加时如何扩容
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 最大可分配大小
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
成员变量
成员变量也是简单到令人发指，一个负责实际存储的缓冲数组和一个表示大小的变量。
/**
* 实际负责存储的缓冲数组
* ArrayList的容量就是缓冲数组的长度
*
* 空的ArrayList(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)在第一个元素添加时将会以默认容量扩容
*/
transient Object[] elementData; // 非私有，以简化嵌套类的访问
/**
* 大小
*/
private int size;
构造函数
三个构造函数，分别是利用默认初始容量/给定初始容量/给定特定集合来构造ArrayList。
/**
* 根据给定初始容量构造一个空的list
*
* @param initialCapacity list的初始容量
* @throws 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);
}
}
/**
* 按默认初始容量(10)构造一个空的list
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 根据给定集合构造一个list，将按集合迭代的顺序存储
*
* @param c 集合
* @throws NullPointerException 集合为null时抛异常
*/
public ArrayList(Collection<? extends E> c) {
//集合转数组后赋值给缓冲数组
elementData = c.toArray();
//判断大小
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
//c.toArray方法可能不会返回Object[]形式的数组
//下面做一层判断
if (elementData.getClass() != Object[].class)
//做拷贝操作
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
//如果是空集合，则替换成共享空数组实例
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
功能
看完了基本介绍，应该会觉得Just so so。
接下来就要逐一介绍各个功能的具体实现了。
ArrayList中，我们常用的功能有add/remove/get等。
无外乎增删改查，下面一一介绍~
add
在ArrayList中，添加操作还分为几种
- 从尾部添加元素
- 指定位置添加元素
- 从尾部添加集合
- 从指定位置添加集合
/**
* 从尾部添加指定元素
*
* @param e 元素
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
//确保内部容量，有一系统调用链但不复杂，下面分析
ensureCapacityInternal(size + 1); // Increments modCount!!
//存储元素
elementData[size++] = e;
return true;
}
/**
* 在指定位置插入元素
* 移动当前位置的元素 (如果存在) 和后继元素到右边
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
//判断边界，可能会产生数组越界
rangeCheckForAdd(index);
//确保内部容量，同上
ensureCapacityInternal(size + 1); // Increments modCount!!
//调用效率较高的System.arraycopy进行数组复制
//目的是为了空出指定位置
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//指定位置上放入指定元素
elementData[index] = element;
//容量+1
size++;
}
在添加的元素的时候，有一个关键方法ensureCapacityInternal是来确保内部缓存数组的容量，当容量不够时进行扩容，下面具体看下这个方法的调用链
/**
* 私有方法
*/
private void ensureCapacityInternal(int minCapacity) {
//判断是否是默认空实例，如果是的话，计算扩容容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
//调用ensureExplicitCapacity
ensureExplicitCapacity(minCapacity);
}
...
private void ensureExplicitCapacity(int minCapacity) {
//操作计算+1
modCount++;
// overflow-conscious code
//只有当容量不够时才扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 缓冲数组扩容以确保能够存储给定元素
*
* @param minCapacity 期望的最小容量
*/
private void grow(int minCapacity) {
// overflow-conscious code
//现有元素长度
int oldCapacity = elementData.length;
//新容量为 旧容量 + 旧容量的一半
//如 10 + 5 = 15
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:
//最小扩容容量通常是接近size的，所以这是一场胜利
//这么臭美的吗
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;
}
set
这里的set其实可以理解为修改，将指定位置的元素替换为新元素。
/**
* 修改指定位置的元素
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
//范围检查
rangeCheck(index);
//取出旧值用以返回
E oldValue = elementData(index);
//放入新的值
elementData[index] = element;
return oldValue;
}
remove
数组的移除和添加一样，也分为几种方式
- 根据下标移除
- 根据对象移除
- 根据集合移除
- 根据过滤器移除
- 根据范围移除(受保护的方法)
/**
* 删除指定位置的元素，后继元素左移(前移)
*
* @param index 下标
* @return the 被移除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
//下标检查
rangeCheck(index);
//操作计数 + 1
modCount++;
//获取指定位置的元素(用以返回)
E oldValue = elementData(index);
int numMoved = size - index - 1;
//用system.arraycopy的方式移动元素
//相当于是index位置后的元素前移
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//最后一个数组元素引用置为null，方便GC
elementData[--size] = null; // clear to let GC do its work
//返回
return oldValue;
}
/**
* 当元素存在的时候，删除第一个找到的指定元素
*
* 如果元素不存在，则list不会变动
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
//o是否是null元素(数组允许存储null)
if (o == null) {
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
//调用内部的fastRemove方法，后面分析
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
//这里跟上面不一样的是，是用equals来比较，而不是比较地址
if (o.equals(elementData[index])) {
//同上
fastRemove(index);
return true;
}
}
return false;
}
/**
* 根据给定的集合，将list中与集合相同的元素全部删除
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
//调用批量删除，后续分析
return batchRemove(c, false);
}
/**
* 通过一个过滤器接口实现，来实现删除
*/
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
//用bitset来存储哪些下标对应的元素要删除，哪些下标对应的元素要保存
//这里不清楚BitSet的用法的，可以先行了解一下
final BitSet removeSet = new BitSet(size);
//判断并发修改用
final int expectedModCount = modCount;
final int size = this.size;
//按顺序遍历且没有并发修改
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//利用过滤器匹配元素，如果匹配，则删除计数+1，并将下标进行存储
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
//判断是否存在并发修改
if (modCount != expectedModCount) {
//抛出并发修改异常
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
//判断是否有要删除的元素
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//下一个要保存的元素
i = removeSet.nextClearBit(i);
//存放到新数组
elementData[j] = elementData[i];
}
//把实际要保存的元素之后的全部置为null，用以GC
//实际上，上面的操作已经将要保留的元素全部前移了，后面的元素都是不保留的，所以要置为null来帮助gc
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//设置size
this.size = newSize;
//判断是否并发修改
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
/**
* 删除list中指定范围的元素
*
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
//范围删除时，其实数组被分成三个部分
//分别为[保留区 - 删除区 - 保留区]
//实际操作，则是计算出最后那部分保留区的长度
//利用arraycopy拷贝到第一个保留区的后面
//然后置空多余部分，帮助GC
int numMoved = size - toIndex;
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
size = newSize;
}
//最后，来看一下批量删除这个私有方法
/**
* 批量删除
*/
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++)
//这里其实有可能抛异常的
//complement
//为false时，则证明下标r的元素不在删除集合c中，所以这个时候存储的是不删除的元素
//为true时，则证明下标r的元素在删除集合c中，所以这个时候存储的是要删除的元素
//这个布尔值的设计很巧妙。所以本方法可以供removeAll、retainAll两个方法来调用
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
} finally {
// Preserve behavioral compatibility with AbstractCollection,
// even if c.contains() throws.
//所以这里要实际进行判断循环是否正常
if (r != size) {
//如果不正常的话，需要挪动元素
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
//如果有需要删除的元素的话，则证明有一部分位置需要只为null，来帮助GC
//并且设置是否有修改的标志为true
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;
}
至此，删除相关的方法都已经分析完毕。
有几个比较有意思的应用
- BitSet 标志哪些下标要删除，哪些不删除
- batchRemove 方法中的布尔值很巧妙
get
作为数组型的list，获取方法时比较简单的，只需要根据给定下标，读取指定下标的数组元素即可。
public E get(int index) {
//范围检查
rangeCheck(index);
return elementData(index);
}
contains
当前list是否包含指定元素
/**
* 返回布尔值表示是否包含
*/
public boolean contains(Object o) {
//实际上是判断下标是否存在
return indexOf(o) >= 0;
}
/**
* 指定元素在list中首次出现的下标，不存在则返回-1
*/
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;
}
//另外，还有一个，最后一次出现的下标
public int lastIndexOf(Object o) {
//跟上面的类似，只不过遍历方式是从尾部开始
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
clear
清空缓冲数组。
public void clear() {
//修改计数 + 1
modCount++;
// clear to let GC do its work
//全部置为null，帮助GC
for (int i = 0; i < size; i++)
elementData[i] = null;
//size设置为0
size = 0;
}
以上相关方法基本都已经介绍完毕。
总结
Array相比其他集合框架，如Map、Set之类的，还是比较简单的。
只需要了解相关方法的应用和原理，注意下标越界问题，以及内部的缓冲数组是如何扩容的，基本上就OK了。
溜了溜了。有帮助的话给格子点个赞呗~~3Q~