ArrayList实现原理（JDK1.8）
arraylist实现原理（jdk1.8）
public class arraylist<e> extends abstractlist<e>
implements list<e>, randomaccess, cloneable, java.io.serializable
arraylist 继承于abstractlist，实现了list接口，其实abstractlist 已经实现过list接口，这里重复实现使得接口功能更加清晰，jdk中很多类都是如此。
其中cloneable接口是克隆标记接口，serializable序列化标记接口，需要clone和序列化功能必须实现这两个接口，而randomaccess，单纯是一个标志接口 ，该接口表示该类支持快速随机访问，且在循环遍历时for循环的方式会优于用迭代器。
1.成员变量
// 默认初始容量
private static final int default_capacity = 10;
// 空数组实例，初始容量为0或者传入集合为空集合（不是null）时使用
private static final object[] empty_elementdata = {};
// 空数组示例，无参构造时使用
private static final object[] defaultcapacity_empty_elementdata = {};
// arraylist内部数据容器
transient object[] elementdata; // non-private to simplify nested class access
// 实际元素数量
private int size;
在arraylist中，主要有五个成员变量。default_capacity表示初始容量大小，即在我们初始化arraylist时不指定容量大小， 默认容量将会是10，object[] elementdata 则是arraylist内部实际存储对象的容易，也就是我们常说的arraylist是数组实现的。
在1.8中，空数组分为了两类情况，empty_elementdata 与 defaultcapacity_empty_elementdata，在标记空数组的时候区分了不同的情况。
2.构造方法
arraylist有三个构造方法，指定容量的arraylist(int initialcapacity) ，无参构造arraylist() 以及传入集合的arraylist(collection<? extends e> c)。
public arraylist() {
this.elementdata = defaultcapacity_empty_elementdata;
}
最简单的莫过于无参构造，直接赋值为空数组defaultcapacity_empty_elementdata。其实对于常说的默认容量10，是在第一次添加元素调用add()方法时处理的，并不是构造方法中。
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);
}
}
对于传入容量的构造方法，当传入参数 > 0时，直接初始化对应容量的数组，参数类型为int，也即arraylist的最大初始容量不能超过integer.max_value，事实上arraylist的最大容量也只能是integer.max_value。而初始容量传入0，会赋值为空数组empty_elementdata。如果 < 0，这个显然的不允许了，直接illegalargumentexception
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;
}
}
集合构造时，没有进行null校验，也就是说如果传入null，直接就会npe异常。集合构造的逻辑也很简单，当传入集合不为空时，调用arrays.copyof进行复制，并且容量 size为传入大小，而传入集合为空，则赋值为空数组empty_elementdata。
3.添加元素
arraylist在添加元素时，都会进行容量确认，可能会涉及到扩容，数组复制，所以效率相对较低。同时在添加元素时，arraylist并未对元素本身进行校验，所以是允许集合中存在null的情况。
3.1.尾部添加元素
public boolean add(e e) {
// 确定容量
ensurecapacityinternal(size + 1); // increments modcount!!
// 设值
elementdata[size++] = e;
return true;
}
在add()方法中，最主要的是确定容量ensurecapacityinternal(int mincapacity)方法。
private void ensurecapacityinternal(int mincapacity) {
ensureexplicitcapacity(calculatecapacity(elementdata, mincapacity));
}
首先会调用calculatecapacity(object[] elementdata, int mincapacity) 计算容量然后再ensureexplicitcapacity(int mincapacity)
private static int calculatecapacity(object[] elementdata, int mincapacity) {
if (elementdata == defaultcapacity_empty_elementdata) {
return math.max(default_capacity, mincapacity);
}
return mincapacity;
}
这里仅仅判断了是否是空数组defaultcapacity_empty_elementdata（== 地址比较），如果前面还有印象的话，这个只会在无参构造时，才会初始化为defaultcapacity_empty_elementdata，这时候会取default_capacity（10）与传入mincapacity的较大值，常说的默认容量大小10也就是在这里诞生的。
而其他的情况，都直接但会mincapacity，也即 size + 1，如果首次添加，那就是1。
private void ensureexplicitcapacity(int mincapacity) {
modcount++;
// overflow-conscious code
if (mincapacity - elementdata.length > 0)
grow(mincapacity);
}
modcount是一个操作计数器，add与remove都会 + 1。当我们需要在循环中删除arraylist元素时，需要使用迭代器iterator的remove()方法，此时直接使用list的删除有针对modcount的校验，会抛出 concurrentmodificationexception异常。
如果mincapacity大于数组容量，则调用grow(int mincapacity)进行扩容。
private void grow(int mincapacity) {
// overflow-conscious code
int oldcapacity = elementdata.length;
// 新容量增长 0.5倍
int newcapacity = oldcapacity + (oldcapacity >> 1);
if (newcapacity - mincapacity < 0)
newcapacity = mincapacity;
if (newcapacity - max_array_size > 0) // max_array_size = integer.max_value - 8
newcapacity = hugecapacity(mincapacity);
// mincapacity is usually close to size, so this is a win:
elementdata = arrays.copyof(elementdata, newcapacity);
}
扩容时，新的容量为原容量 + 原容量的一半，也就是0.5倍增长。如果增长后的新容量比计算出来的容量mincapacity小，则赋值为mincapacity，如果大于max_array_size(integer.max_value - 8)，则进入hugecapacity(int mincapacity)方法。
private static int hugecapacity(int mincapacity) {
if (mincapacity < 0) // overflow
throw new outofmemoryerror();
return (mincapacity > max_array_size) ?
integer.max_value :
max_array_size;
}
这里可以看到，当mincapacity < 0 时，会产生outofmemoryerror，这是一个error子类，这是需要避免的。什么时候mincapacity会小于0呢，当arraylist大小为integer.max_value后，还需要扩容，则会发生错误。
这个方法，我们可以看出，当arraylist需要的容量首次大于max_array_size时，会设置为max_array_size，然后再次扩容时会变成integer.max_value，如果还不够，那就会发生错误。
扩容的最后一步是调用arrays.copyof进行元素的复制，这个最终也是调用system.arraycopy进行操作的。同时size++，实际元素的数量也增加 1。
3.2.中间添加元素
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++;
}
在中间添加元素的逻辑和尾部添加元素基本一样。
private void rangecheckforadd(int index) {
if (index > size || index < 0)
throw new indexoutofboundsexception(outofboundsmsg(index));
}
添加元素前，首先要进行范围检查，添加的范围只能在[0，size]之间，index == size时，其实就是尾部插入。然后确认容量新的容量，这个方法尾部添加时已经讲过，接着数组复制，这步复制会跳过index位置的处理，最后再对index位置赋值，即完成了index位置的添加。
可以看到最后调用了size++，add(int index, e element)方法总是会添加元素，即使该index位置存在数据，只是会将原来的index位置数据往后挤动一位，并不会进行覆盖。
3.3.批量添加
arraylist除了add()与add(int index, e element)，还有两个批量添加的方法。
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;
}
有了前面单个元素的添加基础，批量添加就很好懂了，唯一的区别就是在数组复制时，是复制整个待添加的集合。对于index位置的批量添加，中间插入的话（nummoved > 0），第一次复制会腾出中间要添加集合长度的位置，第二次将添加的集合复制到index位置。
4.修改元素
对于arraylist中元素的修改，如果是对象属性的修改，可以直接修改引用对象，但对于基本类型包装类或者string呢，并没有办法通过引用修改，亦或者我们要更换对象引用，这时候就需要调用set(int index, e element)。
public e set(int index, e element) {
// 范围检查
rangecheck(index);
e oldvalue = elementdata(index);
elementdata[index] = element;
return oldvalue;
}
这个方法实现很容易，arraylist的修改本质就是对数组的值进行更改。首先进行范围检查，防止数组越界，这个很好理解，arraylist内部就是数组，然后对index位置的值进行替换即可。
private void rangecheck(int index) {
if (index >= size)
throw new indexoutofboundsexception(outofboundsmsg(index));
}
elementdata(int index)获取了原来的值，用于set返回值，elementdata实现更加简单，就是数组取值。
5.移除元素
arraylist中移除元素的方法有三个，按索引删除remove(int index)、按元素删除remove(object o)以及批量删除removeall(collection<?> c)等。
5.1.索引删除
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;
}
由于移除元素，并不涉及内部数组大小变化，所以实现相对较简单。必须要的范围检查，这个已经丝毫不陌生了，然后判断是否是尾部删除，如果不是尾部删除，则进行system.arraycopy复制，复制的目的是将index后的元素向前挪动 1 位元素以覆盖要删除的index位置，然后size减 1。
在移除方法中，可以看到modcount进行增加。同时对移除后尾部的元素赋值为null了，让gc生效。
5.2.按元素删除
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;
}
按元素删除的时候，首先判断了元素是否为null，因为arraylist中是可以添加null的，这里不同分支的逻辑是一样的，都是遍历集合比较是否和传入元素相同，只是比较一个是 == null 一个是 equals。如果相同则删除，然后return了，所以remove(object o)方法只会删除集合第一个与传入对象相同的元素。
重点就是这个fastremove了。
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
}
看到这个方法第一感觉是什么？是不是似曾相识，没错，fastremove和按指针删除基本上市一样的，只是少了范围校验和获取删除前的元素这两步。
5.3.批量删除
public boolean removeall(collection<?> c) {
objects.requirenonnull(c);
return batchremove(c, false);
}
对于removeall(collection< ? > c)，校验非空后调用了batchremove(collection< ? > c, boolean complement)。
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;
}
这个方法看着可能有一点点绕，但明白其原理后就很清晰了，首先遍历数组，找出在要移除数组中不包含的元素，从原数组头部开始放，这样的数有w个，即最终数组前w个元素都是在集合c中包含的，而剩下的位置的元素则不关心，最后就是讲w到size的元素赋值为null，以便gc工作。
6.循环删除
前面也提到了，arraylist在循环删除时会报错，这个究竟是怎么回事呢？
如果我们想删除一个集合中全部的某一个元素，例如下面集合ss中的a元素。
list<string> ss = new arraylist<>();
ss.add("a");
ss.add("b");
ss.add("a");
ss.add("b");
ss.add("c");
当我们需要删除一个时，我们可以调用remove方法删除，根据索引或者根据元素都用，但是多个时，我们不知道每一个元素的索引，而根据值也不知道有多少个a存在，所以我们需要遍历集合。
这时候就可能存在问题了。
for (string s : ss) {
if("a".equals(s)){
ss.remove(s);
}
}
无论是fori的还是foreach的删除，都会抛出java.util.concurrentmodificationexception，这是因为arraylist循环时每一次取值都会调用其内部类itr.next()方法。
public e next() {
// 校验modcount
checkforcomodification();
int i = cursor;
if (i >= size)
throw new nosuchelementexception();
object[] elementdata = arraylist.this.elementdata;
if (i >= elementdata.length)
throw new concurrentmodificationexception();
cursor = i + 1;
return (e) elementdata[lastret = i];
}
在该方法最开始的地方，有校验modcount的checkforcomodification()方法，这个方法中比较了modcount和expectedmodcount，不相等就会抛出concurrentmodificationexception异常。
final void checkforcomodification() {
if (modcount != expectedmodcount)
throw new concurrentmodificationexception();
}
那expectedmodcount到底是什么，为什么和modcount不相等呢。
private class itr implements iterator<e> {
int cursor; // index of next element to return
int lastret = -1; // index of last element returned; -1 if no such
int expectedmodcount = modcount;
expectedmodcount是itr的成员变量，这个在进行循环时会初始化赋值为modcount，最开始的时候他们是相等的，经过前面的探究，我们已经知道在remove调用时modcount会自增，所以checkforcomodification就会抛出异常。
而我们常使用的这个做法就是使用 itr 的remove。
iterator<string> it = ss.iterator();
while (it.hasnext()){
if("a".equals(it.next())){
it.remove();
}
}
这样删除时就没有任何问题了，这是因为 itr 的remove中，对expectedmodcount进行了重新赋值，使得每一次调用后值都相等。
public void remove() {
if (lastret < 0)
throw new illegalstateexception();
checkforcomodification();
try {
// 调用arraylist的删除
arraylist.this.remove(lastret);
cursor = lastret;
lastret = -1;
// expectedmodcount重新赋值
expectedmodcount = modcount;
} catch (indexoutofboundsexception ex) {
throw new concurrentmodificationexception();
}
}
7.其他方法
arraylist中主要的就是构造方法、add和remove了，这几个方法看懂后，其他方法实现就比较清晰了。
比如get方法，其实就是根据索引获取了数组的元素。
public e get(int index) {
// 范围检查
rangecheck(index);
// 从数组获取值，即 elementdata[index]
return elementdata(index);
}
例如size方法， 就是返回了size属性的值。
public int size() {
return size;
}
而isempty方法，就是判断size是否为0.
public boolean isempty() {
return size == 0;
}
在arraylist中，有一个获取子集合的sublist方法，这个方法返回的是一个内部类sublist，该类并没重新创建新的数组，依旧持有了arraylist数组的元素的引用，所以当修改arraylist元素的时候，sublist的元素也会跟着修改，这个在实际开发中一定要注意。
public list<e> sublist(int fromindex, int toindex) {
sublistrangecheck(fromindex, toindex, size);
return new sublist(this, 0, fromindex, toindex);
}