3.jpg
Java.util.ArrayList是Java集合中最常用的类，也是Java开发中最常用的类之一。本篇基于JDK9，从ArrayList的基本用法开始，以源码中add()方法的完整实现过程，来分析ArrayList扩容原理的实现。
ArrayList的初始化
1.普通ArrayList,可以装任意Object对象。
List list = new ArrayList();
2.泛型类ArrayList,装指定类型的对象，如String类:
List<String> list = new ArrayList<>();
初始化时可以设置数组容量：
List list = new ArrayList(10);List<String> list = new ArrayList<>(10);
也可以直接初始化赋值：
List<String> list = new ArrayList<>(){{add("A");add("B");add("C");}};
List<String> list = new ArrayList<>(Arrays.*asList*("A", "B", "C"));
ArrayList的增删改查及常用方法
1.添加元素add()
List<String> list = new ArrayList<>();
add有两种重载的方法，分别是直接添加元素和给下标为index的位置添加元素。
list.add("A"); //此时list中有一个String对象：A
list.add(1,8); //给下标为1的位置添加Integer对象:8
注意，要是给不存在的下标位置添加元素，如list.add(3,8);则会引发异常：IndexOutOfBoundsException表示下标越界;如果list.add(index,obj);index下标对应的位置已有对象，则此对象及之后的对象全部依次后移一位。
代码如下:
image
运行结果:
新建一个ArrayList:
[A, B, C]
[A, D, B, C]
2.删除元素remove()
remove和add类似，也有两种重载的方法，分别是直接删除和根据下标index删除
List list = new ArrayList(Arrays.asList("A","B","C","B","C"));
此时数组中元素为A,B,C,B,C，此时list.remove("C")会移除第一个匹配到的"C"
remove()后的数组:
A,B,B,C
再进行list.remove(1)，数组变为：
A,B,C
同样有一点需要注意：如果移除不存在的元素，并不会报错；但是移除不存在的下标，如
list.remove(99)则也会报IndexOutOfBoundsException异常。
代码如下：
image
运行结果：
初始ArrayList:[A, B, C, B, C]
[A, B, B, C]
[A, B, C]
3.查看元素get()
查看元素只有一种方法：get(index)，即通过下标来查看对应的元素，如果下标不存在也会报IndexOutOfBoundsException异常。
代码如下：
image
运行结果：
初始ArrayList:[A, B, C]
get(1)查看'1'号元素：B
4.修改/重置元素set
set()和get()一样，只有一种方式，即通过下标index来修改相应位置元素的值。
代码如下：
image
运行结果：
初始ArrayList:[A, D, C]
[A, B, C]
5.除了get,set,add和remove外，ArrayList还要很多常用方法：
size()返回元素个数，addAll()合并另一个集合类，toArray()将ArrayLIst转化为Object数组，
indexOf()返回某个元素第一次出现的位置下标index，subList()截取指定下标范围的子List。
代码如下:
image
运行结果:
la.toString():[A, B, C]
la.addAll(1,lb):[A, B, C, D, B, C]
la.toArray():[Ljava.lang.Object;@3f0ee7cb
ABCDBCla.indexOf("B"):1
la.lastIndexOf("B"):4
la.subList(0,3):[A, B, C]
ArrayList从源码看扩容实现：
首先，看一下ArrayList的源码定义：
image
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
ArrayList类继承自抽象类AbstractList，实现了List接口，随机存取RandomAccess接口，克隆接口Cloneable，序列化接口Serializable。
通常，我们使用Arraylist添加一个对象往往无需过多考虑，直接add()即可，无需担心其容量是否超过限制，其原因就在于Arraylist源码中，实现add()方法之前会查看其容量是否够用，不够则会自动‘扩容’然后再执行add()添加元素，即自动扩容。
让我们从一个空的数组列表添加元素开始，看一下源码是如何实现的。
List list = new ArrayList();
list.add("A");
首先，List list = new ArrayList();初始化了一个空数组列表list，具体是ArrayList类源码中：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
初始化ArrayList对象的同时创建了一个默认为空的Object数组变量elementData。然后list.add("A")对应的是源码中的add()方法：
image
如图中所示，public boolean add(E e){}方法会执行modCount++;然后调用add(e,elementData,size)方法，最后返回布尔类型的ture。
modCount在ArrayList中定义如下：
protected transient int modCount = 0;
doc说明：
/**
** The number of times this list has been <i>structurally modified</i>.*
** Structural modifications are those that change the size of the*
** list, or otherwise perturb it in such a fashion that iterations in*
** progress may yield incorrect results....*
很多结构化地改变数组的操作都会用到modCount计数，用来标识数组被修改的次数。譬如add , set , remove等。
由于是初次添加元素，故modCount++后变为1，来到下一步add(e, elementData, size)，此时e为要添加的元素：“A”，elementData为刚刚创建的Object[], size为数组初始容量，值为0(在ArrayList中定义：private int size，int型初始未赋值则为0)
重点看下add方法的具体实现：
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow();
elementData[s] = e;
size = s + 1;
}
由于初始elementData.length==size==0故执行grow()方法，返回值赋给elementData。
private Object[] grow() {
return grow(size + 1);
}
grow有两个重载的方法，无参的grow()会调用有参的grow，参数为size+1。
private Object[] grow(int minCapacity) {
return elementData = Arrays.copyOf(elementData,
newCapacity(minCapacity));
}
此处size+1=1作为minCapacity，表示最小容量，实际也很好理解，因为add一个对象首先我需要的最小容量是原长度+1，有了最小容量才能进行下一步地添加元素操作，所以通过grow()来确保我arraylist对象的长度，即【扩容】
扩容的操作通过Arrays.copyOf方法实现：
Arrays.copyOf(elementData,newCapacity(minCapacity))
此方法直接将原数组elementData复制到一个新的给定长度的数组中，并返回此新数组对象。
那么新数组长度是多少呢？这个就是newCapacity()中定义的，让我们看一下：
private int newCapacity(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity <= 0) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
}
return (newCapacity - MAX_ARRAY_SIZE <= 0)
? newCapacity
: hugeCapacity(minCapacity);
}
http://1.int oldCapacity = elementData.length
此处由于elementData是空数组，所以oldCapacity==elementData.length==0
2.newCapacity = oldCapacity + (oldCapacity >> 1)
这一步是扩容的核心操作，即扩容后新数组的长度=原数组的容量+原数组的容量/2.
通过oldCapacity >> 1(Java移位运算，右移1位相当于除以2)来实现扩容原数组容量的一半，即ArrayList的扩容是根据原容量的1.5倍来扩容的。
但是此时oldCapacity值为0故newCapacity也为0，扩容无效...
3.if(newCapacity - minCapacity <=0)
经过第二步后的newCapacity=0，小于minCapacity=1故进入下面的步骤：
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
return Math.max(DEFAULT_CAPACITY, minCapacity);
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return minCapacity;
4.return Math.max(DEFAULT_CAPACITY, minCapacity);
DEFAULT_CAPACITY为ArrayList中初始的默认容量，大小为10。定义如下：
/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;
return Math.max(DEFAULT_CAPACITY, minCapacity)返回10和minCapacity中的最大值，此处直接返回10
现在，经过newCapacity()计算后的新数组容量为10，让我们回到grow()中的：
return elementData = Arrays.copyOf(elementData,newCapacity(minCapacity))
Arrays.copyOf将elementData复制到一个容量为10的新Object[]中去，并返回此数组对象elementData，完成了前面一大堆准备工作，并执行扩容后，终于来到了add()方法中的最后两部：
elementData[s] = e;
完成新增元素添加
size = s + 1;
将该ArrayList对象的数量+1
源码部分方法截图如下：
image
网友评论