JDK源码篇(一) | ArrayList源码解析
ArrayList是我们使用频率非常高的一个集合，也是集合中相对比较简单的集合。是List接口的主要实现类。一般面试的时候经常会问到ArrayList和LinkedList的区别。
ArrayList: 底层是数组实现的，查找快，增删慢。
LinkedList: 底层是链表实现的，增删快，查找慢。
一.类结构
ArrayList是集合的一种，集合的最顶端抽象接口为Collection, Collection下面又有两个子接口，一个是List,一个是Set， List和Set的区别也经常别被问到。
List: 数据是有序的，可以根据序号获取元素，List中的数据是可以重复的
Set: 数据是无序的，并且数据是不可重复的（是否重复是根据hashCode和equals方法结果决定）
List下的常用子类为： ArrayList, LinkedList, Vector.
Set下的常用子类： HashSet.
上面说的结构只是对List结构的一个简单描述。一个相对完成的类结构图如下：
这里可以更加清晰的看出ArrayList的结构，其中最主要的就是实现了List接口。那么我们简单的列一下List接口中 都有哪些方法。
int size();
boolean isEmpty();
boolean contains(Object o);
Iterator<E> iterator();
Object[] toArray();
<T> T[] toArray(T[] a);
boolean add(E e);
boolean remove(Object o);
boolean containsAll(Collection<?> c);
boolean addAll(Collection<? extends E> c);
boolean addAll(int index, Collection<? extends E> c);
boolean removeAll(Collection<?> c);
void clear();
boolean equals(Object o);
int hashCode();
E get(int index);
E set(int index, E element);
void add(int index, E element);
E remove(int index);
int indexOf(Object o);
int lastIndexOf(Object o);
ListIterator<E> listIterator();
ListIterator<E> listIterator(int index);
List<E> subList(int fromIndex, int toIndex);
复制代码这你我把一些默认方法去掉了，因为看起来有点乱，其余的就是ArrayList中需要实现的方法了。这里边的大部分方法，我相信大家应该都使用过。而由于List是有序的，有序的意思就是我们可以通过编号来操作集合中的元素，所以上面有很多的方法都是可以传入 index参数的，就是直接根据编号来操作集合。
二. 构造方法
ArrayList中的构造方法总共有三个。其中两个应该是我们经常使用的。
public ArrayList(int initialCapacity);
public ArrayList();
public ArrayList(Collection<? extends E> c);
复制代码这相当于我们可以通过三种方式来构建一个ArrayList集合
public class Test{
public static void main(String[] args){
// 无参构造
List<String> list1 = new ArrayList<>();
// 传入初始化容量
List<String> list2 = new ArrayList<>(3);
// 传入一个集合
List<String> list3 = new ArrayList<>(list1);
}
}
复制代码这里边第一种方式应该是我们最长使用的，当然也是最不负责任的。第二种方式是编码规范的要求我们这么写的，传入一个初始化的容量。这么做的目的主要是防止向集合中添加数据时，由于集合扩容导致的性能下降问题。所以建议我们在创建集合的时候，最好就根据我们的需求，合理分配出集合的容量大小。第三种是直接传入一个Collection ,要注意，是一个Collection ,也就是List也行，Set也行，这种方法会把Collection直接转为数组，存储到创建的集合中。
三. ArrayList原理
介绍完了这几个构造方法，我们先来讲讲ArrayList的原理。
Q1：ArrayList为什么可以存储元素？
其实他的本质就是一个Object[] , 我们每次向List中添加一个元素，他都会把元素存储到他的一个Object[] 中。那么问题是，我创建一个多大的数组合适呢？ 这就涉及到了一个概念叫做 容量 (Capacity) ,所以刚刚的第二种构造方法，传入一个初始化的数组容量，就是代表我的Object[] 的初始化大小是多少。比如我传入了一个10， 那就代表创建了一个10个长度的Object[].
Q2: 如果存储的数据超出了Object[]的长度范围改怎么办?
假设我们通过List list = new ArrayList(10); 指定了集合的初始化长度，那我们向里边添加的元素个数可以超过10个么。答案是肯定的，也就是我们添加超过10个元素的时候，集合也不会报错，原因是什么的，就是ArrayList的自动扩容原理。当我们向集合中添加元素的时候，集合首先会判断当前的数组容量能否容纳得下所需添加的元素，如果容纳不下，就会触发自动扩容机制。而自动扩容机制的核心原理就是创建一个更大的Object[] ,然后将原来的数组中的元素拷贝到这个更大的数组中来，而往往这个过程是比较影响性能的，尤其是集合中的数据量很大的时候，所以我们前面提到了，尽量直接指定数据的容量（在我们可以判断所需大小的时候），目的就是为了减少他的自动扩容，提升效率。
Q3: capacity和size的区别？
这个概念很重要，大家一定要搞清楚这两个概念的区别，才能够更好的理解集合。
先说capcity, 我们上面提到了，他指的就是我用来存储数据的数组的大小。而size只的是集合中存入的元素个数。
什么意思呢，比如我capacity是10，就代表我的集合中数组的长度是10个，然后我向集合中add一个元素，那么size就是1。 size代表的是集合中存储的元素的真正个数。 当集合中的size即将超过capacity的时候，就会出发集合的扩容操作，capacity会继续增大。
Q4: ArrayList的扩容机制*
这个也是面试中会经常别问到的话题，集合的默认容量是多少，什么时候触发扩容，扩成了多大等等，接下来我们就来详细的分析一下。
1. 首先介绍一下ArrayList类中的五个核心成员变量。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 空数组，当capacity = 0是使用的
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;
}
复制代码这几个成员变量都是非常重要的。首先我们先来介绍一下这里有两个空的Object数组。一个是EMPTY_ELEMENTDATA，还有一个DEFAULTCAPACITY_EMPTY_ELEMENTDATA。
2. EMPTY_ELEMENTDATA 和 DEFAULTCAPACITY_EMPTY_ELEMENTDATA区别
这两个都是空数组，为什么要定义两个呢，有什么区别的？其实在注解中已经给出了解释。
这里在解释一下。其实主要区别就是这样的两个集合。
List list1 = new ArrayList(0);
List list2 = new ArrayList();
复制代码这两种集合，第一种情况，集合中的数组使用的就是EMPTY_ELEMENTDATA， 第二种情况使用的是DEFAULTCAPACITY_EMPTY_ELEMENTDATA。 我们也可以通过代码清晰的看出来。
主要就是对应有参构造方法中的0，和无参构造方法。
那么为什么非要用两个集合呢。主要原因在于，使用无参构造的集合（上述示例中的list2）是要扩容为默认长度（10）的数组，而指定长度的数组是不需要默认长度的。所以要用两个集合。详见计算容量的方法：
这里要注意一下，我是用的JDK8的代码和JDK7略有区别。就是数组在什么时候开辟空间。从jdk8开始，集合不是你new完了就把空间创建出来的，从代码也可以看出来，我们new完的集合（0参和无参），实际上就给了一个空数组，只有当我们向集合中添加元素的时候，才会根据长度初始化数组的长度。这样做的目的实际就是一个懒加载的思想，避免内存的浪费。
3. 扩容到底扩多大
那么接下来我们就来研究下，扩容到底扩成多大。先总结下我们创建数组的构造方法：
// 初始化了一个空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
List list1 = new ArrayList();
// 初始化了一个空数组： EMPTY_ELEMENTDATA
List list2 = new ArrayList(0);
// 初始化了一个10个长度的数组
List list3 = new ArrayList(10);
复制代码而当我们向list1中添加元素的时候，就会将其初始化成默认的长度，也就是10.
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
复制代码那么什么时候扩容呢: 看源码：
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
复制代码添加元素的时候，会使用size+1的值去计算是否需要扩容：
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
复制代码此时的minCapacity 的值就是 size + 1; 调用calculateCapacity 得出所需容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
复制代码这个时候就比较重要了， 当我们的集合是通过无参构造初始化的时候，他的容量是当前size+1 和默认长度的最大值。也就是当我们向集合中添加元素的时候，如果元素个数小于10，那么这个结果就是10， 如果元素个数大于10了，就取当前的最大值。
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
复制代码如果通过上面得到的值已经大于数组的长度了，就代表数组已经装不下了，这时候就会调用grow方法进行扩容。
// 扩容核心方法
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);
}
复制代码怎么扩的呢，新的容量为 ：oldCapacity + (oldCapacity >> 1); 其实就是原长度的1.5倍，如果你原来是默认的10个长度，扩容后会变为15个。但是也不是最终结果。如果扩完的长度还不够，那么就要多长给多长了。如果扩完的长度大于 MAX_ARRAY_SIZE（这个值是int的最大值-8）,就将数组扩容为int的最大值，如果minCapacity为负就代表内存溢出了。这里可能有人想不通，就是扩容后的长度怎么可能不够呢，要注意我们的集合操作不一定都是一个一个添加的，可以通过addAll方法添加一堆元素，那么此时就可能导致你扩容后还是装不下，那就直接初始化为所需长度。
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
复制代码最后再把原来的数组中数据拷贝到新的数组里即可。扩容操作完毕。有点复杂，没懂的多读几遍。
这里基本上就已经是ArrayList中最核心的方法了。剩下的就是一下常用的api都比较好理解了。
四. 常见Api解读
掌握了核心原理，我们就再来读读其他的方法。就比较好理解了。
1. size() 方法，获取集合中元素个数，这里一定注意和capacity的区别。
// 就是一个get方法
public int size() {
return size;
}
复制代码2. get方法和set方法
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;
}
复制代码这里注意一下： 凡是跟index相关的方法，都会先校验一下index是否合法，否则会出现一个我们非常眼熟的异常：
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
复制代码3. addAll方法： 这个方法也涉及到扩容问题。跟上面的差不多：
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;
}
复制代码这里注意下，判断是否扩容的长度就是size + numNew； 单个的时候用的是 size + 1去判断是否扩容。
4. modCount解释：
我们在代码中会随处发现一个变量modCount,比如扩容的时候，remove的时候，set,clear等方法被调用的时候，都有一个modCount++；
这个变量是干什么用的呢，其实就是用来记录集合被操作的次数。记录这个东西有啥用的，主要就是在做序列化的时候，也就是往出写的时候。在ArrayList中有一个writeObject方法：
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
复制代码写的时候会判断前后的modCount是否一致，如果不一致代表对象被操作过，就会报ConcurrentModificationException。
5.indexOf方法： 返回对象在数组中的位置，这里是使用equals方法比较的：
public int indexOf(Object o) {
if (o == null) {
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
复制代码这个应该比较好理解，就是遍历数组，查找对象，返回索引值。
6. clear方法：
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
复制代码将数组中所有元素置为null, size改为0
剩下的方法就不一一过了。 全篇代码中没有出现 synchronized关键字，也间接证明该类线程不安全
- 点赞
- 收藏
- 关注作者
评论（0）