ArrayList源码解析
前言
扯了那么多，终于见到一个具体的实现类了，这次要好好解剖下ArrayList ArrayList算是我们经常使用的一个List，所以先介绍ArrayList的源码
源码分析
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import sun.misc.SharedSecrets;
/*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/
//看这个extends和implements语句特别有意思啊，因为AbstractList已经implementsList接口了
//ArrayList还implements List接口干嘛，多此一举嘛，下面是作者的解释
//来源于:[Stack Overflow的解释](https://stackoverflow.com/questions/2165204/why-does-linkedhashsete-extend-hashsete-and-implement-sete)
//如下：I've asked Josh Bloch, and he informs me that it was a mistake.
//He used to think, long ago, that there was some value in it,
//but he since "saw the light".
//Clearly JDK maintainers haven't considered this to be worth backing out later.
//翻译一下就是：Josh认为是错误的！但是我们看起来比较清晰
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
//ArrayList默认初始化长度是10，HashMap的是16,
//他俩一个是十进制的代表，一个是二进制的代表
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//ArrayList真正存储元素的地方，就是这个elementData数组
transient Object[] elementData; // 不加private，是为了让内部类访问
//这个是ArrayList装了元素的个数，不是elementData的length
private int size;
//构造方法
public ArrayList(int initialCapacity) {
//你要是传入一个初始容量，就用这个容量
if (initialCapacity > 0) {
//这个容量必须大于0
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//等于0就来个空的,我在想，这样子写不行吗
//this.elementData = [];?,为了标识和速度？毕竟EMPTY_ELEMENTDATA已经分配好了不需要new了
//数组长度为0，他也是个对象
this.elementData = EMPTY_ELEMENTDATA;
} else {
//否则抛出异常，这个是RuntimeException类型的异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//看到没，如果你只是 List<String> list = new ArrayList<>();
//那么这个list对象的长度就是0，只有当你add的时候，他才会去扩容
//所以有些面试题问你：ArrayList的初始化的默认长度多少？要分开说了
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
//这句话会在下面 [查看疑难解释](#疑难问题分析加实验)
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
//这个方法主要是缩容，就是去除掉这个ArrayList一些空的位置
//因为这个ArrayList的扩容是按照 0.5 的速度扩容的，如果比较小
//扩容没啥问题，但是如果上100万，那一下扩容就是50万，内存占据不可小觑
public void trimToSize() {
modCount++;
//比对下size(存了几个元素)和elementData.length(分了多少个位置)
//然后利用Arrays.copy函数，去除掉多余分的位置
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
* 这句话也就是解释了为啥子数组的length不能倒 Integer.MAX_VALUE
* 就是因为数组也是对象，他的对象头部也要存储点东西,例如锁标志等
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
//size是装了几个元素，切记
public int size() {
return size;
}
//还是重写了AbstractCollection的size()==0的写法
//因为，size() 需要调用一次函数，性能没这个好
//看JDK源码，最能看到这些源码作者很多细致入微的提升性能的做法
public boolean isEmpty() {
return size == 0;
}
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
//获取传入对象的下标，这个地方我们看到并没有使用迭代器，也是重写了AbstractCollection的方法
//还是那句话，迭代器的速度没有这种定位快，既然，ArrayList是用数组存储了，那就用最快的方式来
//细致入微提升性能的做法
//这个地方是用equals来比较，所以你的对象的equals方法会影响所有的查找
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;
}
//这个是倒着查找，查找节点从size-1开始
//注意size和elementData.length的区别
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;
}
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
E elementData(int index) {
return (E) elementData[index];
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
//替换未知为index的值，
public E set(int index, E element) {
//检查掺入的index和size的比较，这也就是IndexOutOfBoundsException出现的原因
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
//加入元素，可能会涉及到扩容
public boolean add(E e) {
//查看一下是否需要扩容,这个传入size+1，是因为你要加入一个元素了
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1);
//这就是指定位置插入引起的数组copy，性能不大好啊,数组就这个缺点
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
public E remove(int index) {
rangeCheck(index);
//所有的增删改都会修改modCount的数值
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null;
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;
}
//删除也很费劲，还是需要数组copy动作
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
}
public void clear() {
modCount++;
// clear to let GC do its work
//上面这句话真的很有用，当你找不到关于List OOM问题的时候，请使用List的clear方法
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
//下面基本是批量操作，基本都是数组copy动作
public boolean addAll(Collection<? extends E> c) {
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
return numNew != 0;
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
protected void removeRange(int fromIndex, int toIndex) {
modCount++;
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 void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}
疑难问题分析加实验
1、 c.toArray might (incorrectly) not return Object[] 这个是Jdk的一个bug，官方文档
A DESCRIPTION OF THE PROBLEM :
The Collection documentation claims that
collection.toArray()
is "identical in function" to
collection.toArray(new Object[0]);
However, the implementation of Arrays.asList does not follow this: If created with an array of a subtype (e.g. String[]), its toArray() will return an array of the same type (because it use clone()) instead of an Object[].
If one later tries to store non-Strings (or whatever) in that array, an ArrayStoreException is thrown.
Either the Arrays.asList() implementation (which may return an array of component type not Object) or the Collection toArray documentation (which does not allow argumentless toArray() to return arrays of subtypes of Object) is wrong.
翻译过来：一般情况下Collection.toArray()方法返回的是Object[],但是有特殊人员存在，那就是Arrays.asList().toArray()返回
的就不是Object[],所以需要检查一下,不过看官网的意思，JDK9已经解决了这个问题，没看过JDK9的源码，暂且不清楚
下面是我的实验代码
public class CollectionFound {
private static final Logger logger = LoggerFactory.getLogger(CollectionFound.class);
/**
* 验证Collection.toArray的类型
*/
@Test
public void toArrayType(){
ArrayList<Date> first = new ArrayList<>();
Object[] firstArray = first.toArray();
logger.info("查看类型:{}",firstArray.getClass());//查看类型:class [Ljava.lang.Object;
List<Date> second = Arrays.asList(new Date(), new Date());
Object[] secondArray = second.toArray();
logger.info("查看类型;{}",secondArray.getClass());//查看类型;class [Ljava.util.Date;
}
}
1、 size和elementData.length的区别
这个图展示的ArrayList的size为：4 elementData.length=6
1、 ArrayList的扩容的过程
public boolean add(E e) {
//要去检查下要不要扩容了
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
////下面三个函数就是想获取最小需求的容量
private void ensureCapacityInternal(int minCapacity) {
//minCapacity:最小容量，就是 size+1(当前尺寸加上插入的一个，只有在插入的时候才会想起来
//扩容，平时get，set，容量不变化，所以没有扩容的事情)
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//这个函数就是返回 10(默认的容量)或者 size+1
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++;
// 只有当需要的最小容量大于 elementData.length的时候，才会去扩容
//也就是说只有再实在装不下的时候才会去扩容,不像HashMap那种有负载因子
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
真正的扩容函数
private void grow(int minCapacity) {
// 计算扩容的大小
int oldCapacity = elementData.length;
//从这个地方可以看到扩容后的容量大小是
//新容量 = 老容量 + 老容量/2 使用位移速度快,也就是扩容了0.5倍大概
int newCapacity = oldCapacity + (oldCapacity >> 1);
//下面主要是检查扩容之后别超过最大值 Integer.MAX_VALUE-8 或者扩容
//之后还没有最小需求量小的情况
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);
}