本文基于JDK1.8源码剖析来剖析,ArrayList顾名思义,数组的结构来表明一个List,先上一张图抛砖引玉:
这张图表明的便是恳求了容量capacity
为10的array buffer
,但是有用容量size
为1的情况。
开始剖析源码:
1. 特点及结构办法
先来看他的几个特点和结构办法:
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData; // non-private to simplify nested class access
private int size;
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);
}
}
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 {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
相信咱们看完这个代码的第一个疑问肯定是为什么要搞两个空Object数组出来。
EMPTY_ELEMENTDATA
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
这两个都是空数组,其实要搞清楚这个问题看一下他们别离在什么地方运用就好了。
- 首先是
EMPTY_ELEMENTDATA
,他一切被运用的地方都是在初始化的时分size为0的时分被赋值给elementData
,所以它的效果便是在size为0的时分不用去创建一个空数组了,而是提前创建好了放在那儿,便利被运用。 - 再看
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
,他被运用的场景是在默许结构办法的时分被赋值给elementData
,然后在add扩容的时分,被用来做判别。也便是说它的含义是告诉后边的代码当前是空的,需求被扩容成默许巨细DEFAULT_CAPACITY = 10
。
其实深一点说它的效果是做一个时刻上的拖延处理,咱们每次new ArrayList()的时分其实这个时分并没有给咱们恳求内存,只要在add的时分才会恳求10个内存空间,它的含义在这儿。
那咱们来看结构办法,三个结构办法,其实没什么好说的,看完上面咱们的一个解说其实咱们应该好了解了。
这儿要留意的是假如咱们调用了一个new ArrayList(20)
,是直接恳求了一个20的数组,而不是从0开始扩容,即使是new了一个ArrayList(Integer.MAX_VALUE)
也是这样,并没有触发扩容,后边add的时分才会扩容。
好的,那既然是调集类,那咱们别离来看它的增修改查办法~
2. add
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
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++;
}
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;
}
四个add办法,分为两种用法:
add单个
addAll
咱们发现这些办法都调用到了一个叫做ensureCapacityInternal
的办法,下面看它的代码:
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//初始化成DEFAULTCAPACITY_EMPTY_ELEMENTDATA的时分容量赋值成DEFAULT_CAPACITY
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0) //①
grow(minCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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:
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;
}
首先先回忆一下上面咱们说的add的时分关于赋值成
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
用来做拖延恳求内存的常识,在calculateCapacity
办法里边.
2.1. 扩容
下面就到了ArrayList的核心办法grow
扩容。
咱们先从最不鸿沟的情况看起,先了解一个最简略的扩容机制,capacity容量
和size
都为10的时分再add一个是怎样触发grow
的,grow办法里边真实起效果的便是下面两句了。
// 15 = 10 + (10 >> 1) = 10 + 5
int newCapacity = oldCapacity + (oldCapacity >> 1);
//复制数据
elementData = Arrays.copyOf(elementData, newCapacity);
看起来也不难,那其实写东西理清了思路逻辑就那么一点,其实真实难处理的和容易出问题的都在鸿沟上。咱们看到在grow办法里边有一些if来处理鸿沟条件,我在上面的if后边标了①②③④
的注释,咱们别离看一下能触发这些if的条件。
①
. 由于每次都会调用查看是否需求扩容,那判别只要大于elementData.length
的时分才需求扩容。
②
. 这句是说oldCapacity扩容1.5倍之后假如比需求的minCapacity
还要小,那就直接用minCapacity
作为newCapacity
来做扩容。这个其实很好了解,在addAll的时分假如需求add的调集很大的时分就会呈现这种情况。
比方:
List src = new ArrayList(10);
List tar = new ArrayList(10);
src.addAll(tar);
那很明显oldCapacity = 10; 扩容1.5后newCapacity = 15,而minCapacity = 20。
③④
,这俩其实是一同的。假如扩容后的newCapacity
大于MAX_ARRAY_SIZE
,也便是大于Integer.MAX_VALUE - 8
或者爽性大于Integer.MAX_VALUE
最大值,这个时分就直接赋值为Integer.MAX_VALUE
。
这个时分其实咱们还留意到hugeCapacity
这儿有这么一个判别:
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
那什么时分会小于零呢?咱们知道java里边int是没有所谓的unsigned的概念的,也便是无符号的概念。这儿可以看一下我写过的一篇文章一次与或非操作实战,也便是说超过了Integer.MAX_VALUE
就变成负数了。所以假如恳求的超过最大值就直接抛OOM了。
那其实看完扩容,add就很简略了,不解说了,直接上图。
2.2. add(E e)
add单个元素:
2.3. add(int index, E element)
2.4. Collection<? extends E> c
这儿需求留意的是addAll的时分,不管被add的List的size是多大的,只会扩一次容。一次性到需求的capacity。
3. get set
那其实getset就简略的很了,没几句代码,由于是ArrayList,优势便是在可以以O(1)的时刻复杂度找到需求的方位,很简略就不解说了。
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
4. remove
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 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;
}
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
}
那看代码来说,remove(int index)
跟remove(Object o)
肯定是功率不一样的,一个O(1)一个是O(n)。这是remove单个的时分,便是找到需求移除的index的办法不一样,那找到之后的工作量都是由System.arraycopy
来完成的,附图:
那removeAll的代码如下
public boolean removeAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
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++)
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;
}
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;
}
我也是在看的时分才发现有retainAll
这么个办法,跟removeAll
的区别只要一个标志位。那含义便是彻底相反的,咱们知道removeAll
是把方针调集全部移除去,retainAll
刚好相反,是只保存方针调集里的元素.
就比方说有listA: [0, 1, 2, 3, 4]
,同时有listB: [1, 2, 3]
。
-
listA.removeAll(listB)
=>listA: [0, 4]
-
listA.retainAll(listB)
=>listA: [1, 2, 3]
那咱们来看removeAll
,complement为false,关键办法batchRemove
,这儿面有两个变量r
和w
,咱们还是拿listA.removeAll(listB)
来举比如:
r
会循环0 ... 4
:
- 第一遍循环,
r= 0
且w = 0
,这时listB
包括elementData[0]=0
不建立,所以把elementData[0]
赋值给elementData[w=0]
,然后w++
之后w = 1
- 第二遍循环,
r= 1
且w = 1
,这时listB
包括elementData[1] = 1
建立,不做赋值 - 第三遍循环,
r= 2
且w = 1
,这时listB
包括elementData[2] = 2
建立,不做赋值 - 第四遍循环,
r= 3
且w = 1
,这时listB
包括elementData[3] = 3
建立,不做赋值 - 第五遍循环,
r= 4
且w = 1
,这时listB
包括elementData[4] = 4
不建立,elementData[4]
赋值给elementData[w=1]
,然后w++
之后w = 2
循环完毕。这时分removeAll操作就完成了。retainAll的操作便是刚好相反,下面附一张图,更直观: