ArrayList简介及扩容机制

个人博客链接（原文）：欢迎点击

ArrayList介绍

ArrayList 是一个数组队列，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List, RandomAccess, Cloneable, java.io.Serializable这些接口。 1. ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。 2. ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。RandmoAccess是java中用来被List实现，为List提供快速访问功能的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象；这就是快速随机访问。稍后，我们会比较List的“快速随机访问”和“通过Iterator迭代器访问”的效率。 3. ArrayList 实现了Cloneable接口，即覆盖了函数clone()，能被克隆。 4. ArrayList 实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。

---

  和Vector不同，ArrayList中的操作不是线程安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。

ArrayList的继承关系

ArrayList构造函数

// 默认构造函数 ArrayList() // capacity是ArrayList的默认容量大小。当由于增加数据导致容量不足时，容量会添加上一次容量大小的一半。 ArrayList(int capacity) // 创建一个包含collection的ArrayList ArrayList(Collection<? extends E> collection)

扩容机制

  首先大家都知道ArrayList的扩容规则是变成原来最大容量的1.5倍。   你也可以通过eclipse等IDE打开ArrayList.add()的源码查看。

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }

通过ensureCapacityInternal方法判断是否要扩容。源码如下：

/** * 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. * EMPTY_ELEMENTDATA是空数组，表示现在ArrayList是空的 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};// //elementData是存放元素的对象数组 transient Object[] elementData; // non-private to simplify nested class access private void ensureCapacityInternal(int minCapacity) { if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); }

  ensureCapacityInternal（确保内部容量）中首先是判断现在的ArrayList是不是空的，如果是空的，minCapacity就取默认的容量和传入的参数minCapacity中的大值,然后调用ensureExplicitCapacity方法。

private void ensureExplicitCapacity(int minCapacity) { modCount++; //如果数组（elementData)的长度小于最小需要的容量（minCapacity）就扩容 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }

  如果minCapacity的值大于add数据之前的大小，就调用grow方法，进行扩容，否则什么也不做。   增长机制是通过grow方法实现的。

/** *增加容量，以确保它至少能容纳 *由最小容量参数指定的元素数。 * @param mincapacity所需的最小容量 */ private void grow(int minCapacity) {//minCapcatiy的值是size+1 // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //>>位运算，右移动一位。 整体相当于newCapacity =oldCapacity + 0.5 * oldCapacity 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); }

  实现grow方法调用就肯定是(size+1)>elementData.length的情况，所以size就是初始最大容量或上一次扩容后达到的最大容量，所以才会进行扩容。

---

  newCapacity=oldCapacity+(oldCapacity>>1)，这里就是扩容大小确定的地方，相当于新的最大容量是 size+1+size/2 相当于原来的1.5倍 。

这样便实现了ArrayList的自动扩容。

总结

注意其三个不同的构造方法。无参构造方法构造的ArrayList的容量默认为10，带有Collection参数的构造方法，将Collection转化为数组赋给ArrayList的实现数组elementData。注意扩充容量的方法ensureCapacity。ArrayList在每次增加元素（可能是1个，也可能是一组）时，都要调用该方法来确保足够的容量。当容量不足以容纳当前的元素个数时，就设置新的容量为旧的容量的1.5倍，如果设置后的新容量还不够，则直接新容量设置为传入的参数（也就是所需的容量），而后用Arrays.copyof()方法将元素拷贝到新的数组（详见下面的第3点）。从中可以看出，当容量不够时，每次增加元素，都要将原来的元素拷贝到一个新的数组中，非常之耗时，也因此建议在事先能确定元素数量的情况下，才使用ArrayList，否则建议使用LinkedList。ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

---

参考资料：http://blog.csdn.net/u010176014/article/details/52073339