Java开发离不开数据结构，这篇文章总会在这着重的讲下我们在开发中尝试用的数据结构-ArrayList。
针对ArrayList，我会深入的探究关于它的扩容机制、线程安全问题以及为什么使用ArrayList而不使用数组等这些问题。首先，我们知道ArrayList是Collection的子类，而Collection是单列集合，所以ArrayList亦是如此。继承自 AbstractList，实现了 List 接口。底层基于数组实现容量大小动态变化。允许 null 的存在。同时还实现了 RandomAccess、Cloneable、Serializable 接口，所以ArrayList 是支持快速访问、复制、序列化的。
一、关于为什么使用ArrayList而不使用数组
这个问题其实很好回答了：①数组需要先定义好容量大小才可以添加数据，一旦定义好的容量长度是固定的，后期无法动态修改，而ArrayList的容量是自动扩展的，灵活性更强。②ArrayList中实现了增、删、改的方法，支持快速访问等方法。
二、ArrayList线程安全问题
ArrayList是线程不安全的集合类。为什么这么说，我们该怎样解决关于他线程不安全的问题呢？首先我们上代码：
List<String> list = new ArrayList<>();
for (int i = 0; i < 5000; i++) {
new Thread(() -> list.add(Thread.currentThread().getName())).start();
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("ArrayList添加的元素个数--> " + list.size());
输出结果: ArrayList添加的元素个数--> 4999
上面的结果显而易见，我们创建5000个线程并发操作，正常情况下ArrayList添加的元素个数应该是5000个，输出的结果是4999个，这个结果却与我们预期的结果不一致。所以，这就是多线程并发下导致数据不安全的结果，所以这就是我们为什么说ArrayList是线程不安全的原因了，点进ArrayList的源码，找到add()你会发现它并未加同步锁synchronized:
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
前面已经说到，ArrayList之所以是线程不安全的，是因为未加同步锁，所以我们可以尝试用这个方法解决问题：
List<String> list = new ArrayList<>();
for (int i = 0; i < 5000; i++) {
new Thread(() -> {
synchronized (list) {
list.add(Thread.currentThread().getName());
}
}).start();
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("ArrayList添加的元素个数--> " + list.size());
输出结果:ArrayList添加的元素个数--> 5000
想要解决这个方法有很多种，不仅仅是这一种，譬如，我们可以使用Collections工具类将ArrayList转换成线程安全的集合类：
List<String> ls = new ArrayList<>();
List<String> list= Collections.synchronizedList(ls);
for (int i = 0; i < 5000; i++) {
new Thread(() -> {
list.add(Thread.currentThread().getName());
}).start();
}
try {
Thread.sleep(1000);
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println("ArrayList添加的元素个数--> " + list.size());
输出结果:ArrayList添加的元素个数--> 5000
或者使用其他线程安全的集合类，如Vector、CopyOnWriteArrayList等等，这里推荐使用CopyOnWriteArrayList，因为它的效率高的多，它的底层不是通过synchronized来保证线程安全的,而是通过Lock来保证线程安全的，我们在学习锁和线程同步安全的知识时就知道了，在相同的多个线程并发操作相同的共享数据时，synchronized是比Lock的效率要低的。对比结果如下图所示：
三、ArrayList扩容机制(基于JDK1.8)
在讲解扩容机制前，我们先把以下几个重要的结论放出来,这样可以方便大家前后对照：
①ArrayList中维护了一个Object类型的数组elementData,即：Object[]elementData,添加的对象是所有类型，包括null。
②当下创建ArrayList对象时，如果使用的是无参构造创建，那么elementData的初始容量为0，第一次添加时则elementData的容量扩展至10，如果超过容量10的添加量，则需再次扩展，则elementData容量扩展为1.5倍（自身容量的0.5倍）。
③当下创建ArrayList对象时，如果使用指定容量大小的构造器，则elementData的容量初始大小为构造器中指定的大小数量，如需扩容，则elementData容量扩展为1.5倍（自身容量的0.5倍）。
④数组扩容最终使用的是Arrays.copyOf(),在保证原有的数据情况下对原来数组进行扩容。
其实，无论ArrayList是通过无参构造创建集合还是通过构造方法中传入集合默认容量大小，最终的结果都会呈现出通过无参构造创建集合实现扩容机制的步骤。所以，这里直接拿无参构造创建ArrayList的样板来对它的扩容机制深入的学习。一般的，我们创建一个ArrayList的代码如下：
List<String> ls = new ArrayList<>();
点进源码，我们会发现：
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
其实就是创建了一个空的Object[],而elementData就是我们真正实现增、删、改、查的数组，无参构造创建默认初始的容量就是0。 我们继续往下看，找到扩容的实现方法：add(E element):
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
我们会发现，当集合每添加一个元素进来时，数组的index就自增，而size就是ArrayList中的元素个数，而ensureCapacityInternal(size + 1)这个方法就是扩容的方法，我们点进去看一下：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
看到calculateCapacit有两个参数，一个是ArrayList所维护的关键数组elementData和当前数组的容量minCapacity，ArrayList一开始创建时，它的容量minCapacity=0。calculateCapacit方法中还有一个参数DEFAULT_CAPACITY，点进发现：
private static final int DEFAULT_CAPACITY = 10;
没错，它的默认容量就是10，也就是说当我们使用无参构造创建ArrayList时，默认初始容量是0，首次扩容的容量大小是10。我们接着往下看：
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
此时minCapacity=10，而 elementData.length还是0，所以，进入grow(minCapacity)：
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);
}
BingGo！到了grow()这个方法，说明我们已经深入到ArrayList扩容核心代码中了，上面我们已经分析了minCapacity的容量是10，oldCapacity在这里是0，实现扩容的算法： int newCapacity = oldCapacity + (oldCapacity » 1)，仔细发现是在原数组容量的前提下，扩展了原数组一半大小的容量（ oldCapacity » 1 相当于 oldCapacity÷2 ），这里使用位移实现的原因是因为计算机是通过二进制操作数据的，位移的实现比我们使用乘法或除法实现的效率更高。首次扩容的newCapacity大小也是为0，所以最终会将扩容的DEFAULT_CAPACITY通过rrays.copyOf(）复制进来，这个方法在保证原有数据不丢失的前提下进行扩容。 那我们会在何时执行第二次乃至第N次扩容呢？答案就是当我们添加的数据容量超过第一次扩容的容量大小为10的情况下，这时就会触发第二次扩容，扩容的大小按照：int newCapacity = oldCapacity + (oldCapacity » 1)实现，即：int newCapacity=10+10÷2 也就是第二次会扩容到15，第三次扩容到22，第三次33…
下面，我将根据上面我们所学的一系列原理，写一个简单ArrayList：
/**
* 模拟数组的简单实现
*
* @param <E>
*/
@SuppressWarnings("all")
class AtomArrayList<E> {
private Object[] elementData;
//默认空数组
private final Object[] EMPTY_DATA = {};
//首次扩容默认的容量大小
private final int Default_Capacity = 10;
//元素个数
private int size = 0;
//刚创建的数据默认是空数组，默认初始容量为0
public AtomArrayList() {
elementData = EMPTY_DATA;
}
//扩展容量
int exCapacity = 0;
//临时记录扩展容量的变量
int tempCapacity = 0;
/**
* 添加数据
*
* @param e 元素
*/
public void add(E e) {
//首次扩容先给容量10
if (size < Default_Capacity) {
exCapacity = Default_Capacity;
tempCapacity = exCapacity;
}
//第二次及以后扩容，其容量在原有容量的基础上再扩展原容量的0.5倍增长。
if (size >= tempCapacity) {
exCapacity = tempCapacity + (tempCapacity >> 1);
tempCapacity = exCapacity;
}
System.out.printf("集合当前的容量：%d \n", exCapacity);
//实现扩容的核心方法：在保留元素组的容量前提下，对元素组容量的一半进行复制，这样可以避免数组不会倍覆盖
elementData = Arrays.copyOf(elementData, exCapacity);
//添加元素的同时，实现index自增
elementData[size++] = e;
}
/**
* 获取集合长度
*
* @return 集合长度
*/
public int size() {
return size;
}
/**
* 获取元素
*
* @param position 角标
* @return 元素
*/
public E get(int position) {
return (E) elementData[position];
}
/**
* 清除所有元素
*/
public void clear() {
for (int i = 0; i < size; i++) {
elementData[i] = null;
}
size = 0;
}
}
使用的过程很简单，和我们使用ArrayList一样：
strS.add("张三");
strS.add("李四");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
strS.add("赵五");
System.out.println("添加数据后的集合长度：" + strS.size());
//清除数据
strS.clear();
System.out.println("清除数据后集合的长度：" + strS.size());
输出结果:
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:10
集合当前的容量:15
添加数据后的集合长度:11
清除数据后集合的长度:0
