ArrayList 源码解读
依赖
ArrayList依赖
关于为什么ArrayList已经继承了AbstractList还要实现List接口, 可参考 Why does LinkedHashSet extend HashSet and implement Set
StackOverflow解释
可能这样增加可读性吧, 接口的第二个功能一样
字段
/**
* Default initial capacity.
* 默认初始化容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances
* 空实例的共享数组实例
* 若是无参构造方法 使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
* 若是含参构造方法 使用 EMPTY_ELEMENTDATA
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
*
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int 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
* 某些 VM 保留数组头部用于存储一些 header words
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
可以发现, elementData 和 size 两个变量在ArrayList的运行中会有很大的变动, 可以使用反射进行观察
构造函数
ArrayList()
/**
* 构造函数1: 默认构造函数,
* DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0,
* 初始是一个空数组, 当添加一个元素的时候, 扩充为10(如何扩充为10, 详见下述)
* 原因详见 transient Object[] elementData上的注释
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
也就是在创建对象的时候，并没有立刻初始化容器的大小，直到第一次调用 add()方法的时候，才进行确定。
ArrayList(int initialCapacity)
/**
* 构造函数2 带初始容量参数的构造函数, (用户自己定义容量)
*/
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);
}
}
初始化容量大小为initialCapactiy
ArrayList(Collection<? extends E> c)
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
* 构造包含指定collection元素的列表 这些元素利用该集合的迭代按顺序返回
* 如果指定的集合为null, 抛出 NullPointerException
*/
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 {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
总结
- 常量EMPTY_ELEMENTDATA和DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了初始化elementData的。如果为无参构造函数，使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA；如果为含参构造函数，使用EMPTY_ELEMENTDATA
- 以无参构造方法创建arraylist时, 实际上初始化的值是一个空数组. 添加第一个元素时 扩容为10
- 如果使用
Collection实例初始化, 不为空将调用toArray()方法初始化elementData, 为空时初始化为空数组EMPTY_ELEMENTDATA
增
add(E e)
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
在调用 add()方法的时候，首先调用 ensureCapacityInternal()方法来确定是否还有容量来容纳新的值。size是表示数组的初始大小，默认为 0 。
ArrayList-add执行步骤
按照流程走一遍:
- 第一次调用的时候:
- 第一步, 因为还为添加成功元素,
size = 0,size + 1 = 1 - 第二步, 首先执行第三步, 传入两个参数
elementData和minCapacity - 第三步, 此时的
elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATAT, 然后minCapaciy==1, 返回DEFAULT_CAPACITY - 第四步, 此时的
minCapacity==10,elementData.length = 0所以执行if分支 - 第五步,
oldCapacity==0经计算newCapacity==0然后newCapacity-minCapacity<0, 所以newCapacity==10之后进行数据的复制，这时，elementData的长度是 10.，第一个元素成功的添加到数组中。
- 第一步, 因为还为添加成功元素,
- 第二次调用
- 第一步, 因为已经添加成功了一个元素,
size = 1,size + 1 = 2 - 第二步, 首先执行第三步, 传入两个参数
elementData和minCapacity - 第三步, 此时的
elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATAT, 然后minCapaciy==2, 不执行if分支, 返回2 - 第四步, 此时的
minCapacity==2,elementData.length = 10所以不执行执行if分支, 也就是无需扩容
- 第一步, 因为已经添加成功了一个元素,
- 反复添加直到添加第11个元素的时候, 再次出发第四步的grow, 进行扩容, 扩为原先的1.5倍.
add(int index, E element)
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
使用arraycopy方法, 可以看做将指定坐标位置以及右侧所有元素向后移动一位，腾出空间存放新元素。
addAll(Collection<? extends E> c)
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;
}
addAll(int index, Collection<? extends E> c)
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;
}
总结
- 共实现四中添加方法:
- 添加单个元素(默认在尾部添加)
- 在指定位置添加单个元素
- 添加一个集合(默认在末尾)
- 在指定位置添加一个集合
- 每次执行add操作时都会首先调用
ensureCapacityInternal()方法来确定是否还有容量来容纳新的值, 若是没有则进行扩容, 有则直接添加
删
remove()方法用来从集合中删除一个元素，可以删除指定索引出的元素，也可以指定元素。
remove(Object o)
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;
}
// 将index位置后的所有元素前移一位, 之后size-1
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
}
流程走一遍
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("a");
arrayList.add("b");
arrayList.add("c");
arrayList.remove("a");
要删除
a这个元素，把a传入到remove()这个方法，首先进行判断是否为null，因为ArrayList可以存放null，如果为null则用==判断元素是否相等，否则用equals()方法进行判断。然后循环遍历
elementData这个数组，size为数组元素个数，找到和a相等的元素的索引，例子中 index = 0， 然后把 0 传入到fastRemove()方法中，之后计算要移动的元素的个数：int numMoved = size - index -1;例子中
numMoved = 3 - 0 -1 = 2，也就是一共要移动两个元素，然后把a之后的两个元素往前移动，然后进行size-1，把最后一个元素位置的值设置为 null。这样即可在
ArrayList中删除一个元素。
remove(int index)
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
总结
没啥好总结的
查
public E get(int index) {
// 判断查询的位置是否符合要求
rangeCheck(index);
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
E elementData(int index) {
return (E) elementData[index];
}
没啥好说的, 就是正常数据的使用
附加
hugeCapacity 方法
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
只有newCapacity >MAX_ARRAY_SIZE 才回调用该方法, 方法中使用三元运算, 意思是若果minCapacity> MAX_ARRAY_SIZE 则newCapacity的容量大小为Integer.MAX_VALUE也就是2**31次方, 若是minCapacity< MAX_ARRAY_SIZE 则newCapacity的容量大小为Integer.MAX_VALUE-8
ensureCapacity用法
Arraylist源码中有一个ensureCapacity方法
/***
* 如有必要，增加此 ArrayList 实例的容量，
* 以确保它至少可以容纳由minimum capacity参数指定的元素数。
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// any size if not default element table
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.
: DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
该方法适用于添加大量的元素, 以减少上文的增量重新分配的次数
ArrayList<Object> list = new ArrayList<>();
final int N = 10000000;
long startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
long endTime = System.currentTimeMillis();
System.out.println("使用ensureCapaticy方法之前: "+ (endTime - startTime));
list = new ArrayList<>();
list.ensureCapacity(N);
startTime = System.currentTimeMillis();
for (int i = 0; i < N; i++) {
list.add(i);
}
endTime = System.currentTimeMillis();
System.out.println("使用ensureCapaticy方法之后: "+ (endTime -startTime));
使用ensureCapaticy方法之前: 3345
使用ensureCapaticy方法之后: 257
总结
ArrayList集合底层是用一个 Object 数组来存放元素的，其可以存放 null 值，因为是使用数组来存放元素，所以在知道索引的情况下，进行元素的查找是很快的，但是也有缺点，如果数组的容量不能够存放新元素的时候，会进行数组的扩容，也就是把数组元素复制到一个容量更大的数组中，所以如果在经常进行元素添加和删除操作的情况下效率会比较低。还有一点，ArrayList不是线程安全的，要保证线程安全，可以使用 Vector代替。
System.arraycopy(src, srcPos, dest, destPos, length) 与 Arrays.copyOf(original, newLength)区别
arraycopy()的参数
- src:源数组;
- srcPos:源数组要复制的起始位置;
- dest:目的数组;
- destPos:目的数组放置的起始位置;
- length:复制的长度.
两者的区别在于，Arrays.copyOf()不仅仅只是拷贝数组中的元素，在拷贝元素时，会创建一个新的数组对象。而System.arrayCopy只拷贝已经存在数组元素, 是否创建新的数据对象,根据写法而定
//System.arraycopy,只拷贝已存在的数组元素
int[] src = {0, 1, 2};
int[] dest = new int[3];
System.arraycopy(src, 0, dest, 0, src.length);
System.out.println(Arrays.toString(dest)); //[0, 1, 2]
//Arrays.copyOf,会创建一个新的数组对象
int[] src = {0, 1, 2};
int[] dest = Arrays.copyOf(src, src.length);
System.out.println(Arrays.toString(dest)); //[0, 1, 2]
实际上Arrays.copyOf方法的内部实现也是通过System.arraycopy方法实现，在Arrays类中有多个copyOf的重载方法，现以拷贝int[]为例：
1 public static int[] copyOf(int[] original, int newLength) {
2 int[] copy = new int[newLength];
3 System.arraycopy(original, 0, copy, 0, Math.min(original.length, newLength));
4 return copy;
5 }
