揭开ArrayList的外衣，看本质?

mp.weixin.qq.com图标

源码还是比较多的，安安静静的读完确实不易，所以我们读源码要有著重点。

  • ArrayList的继承和实现关系
  • ArrayList的成员
  • ArrayList的构造
  • ArrayList的容量与扩容问题
  • ArrayList的遍历删除修改操作

1 继承和实现

看下ArrayList的定义：

public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable {}

ArrayList继承了 抽象类AbstractList，实现了 List介面，并且实现了RandomAccess, Cloneable, java.io.Serializable这三个标记介面，标记介面中是没有

声明任何方法的，没有方法并不代表没有用，他们分别表示ArrayList具有可随机访问，可克隆及可序列化能力。

我们通过一张UML图来看可能更直观：

2 成员

初始化容器常量

/**
* 静态常量 空数组 用于返回 元素为空的实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
* 空数组 和 EMPTY_ELEMENTDATA 用于区别，以便在第一个元素添加时知道扩容多少
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

修改次数

//用来记录集合结构变动的次数
protected transient int modCount = 0;

默认容量

/**
* 静态常量 默认容量
*/
private static final int DEFAULT_CAPACITY = 10;

/**
* 包含元素的数量，私有变数只能通过size()方法获得
*/
private int size;

/**
* 数组的最大长度，一些虚拟机在存储数组对象时会将一些头信息存入其中，
* 分配过大的数组空间很可能导致 OOM，数组长度超过VM的限制。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

看到上面的 DEFAULT_CAPACITY，你是不是真的信了，默认容量是10 ？（稍后揭晓）存储容器

/**
* 声明一个默认许可权的数组,用以存储元素,只能在本类或本包中访问
*/
transient Object[] elementData;

上面这些成员中，主角就是 elementData，这个数组就是我们存储对象的地方。为什么使用数组呢？那么来补补数组的知识。

数组1. 数组 和其他容器之间的区别有三方面：效率，类型和保存基本类型的能力。2. 数组是一种效率最高的的存储和随机访问对象的方式，它是一种简单的线性序列，这使得元素访问非常快速，但代价是它的长度是被固定的，在它生命周期中是不可以变更的。3. 访问数组的唯一方式就是使用数组索引，即我们常说的下标。

内部类及嵌套类

  • SubList

ArrayList的一个子集视图，为什么说是视图呢？因为它展示的就是ArrayList中的部分元素，无论改变它本身还是ArrayList，双方都会手影响。

  • Itr

迭代器Iterator介面的实现类。

  • ListItr

继承于Itr，是Itr的功能增强版。

  • ArrayListSpliterator

分割迭代器，可以将迭代器分割一分为二，依次类推。

3 构造方法我们都用过 ArrayList ，但最常用的应该是 new ArrayList() 或者 new ArrayList(10) 吧！其实构造方法有三种，我们依次来看看：

指定容量构造

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);
}
}

  • 指定初始容量后便创建一个指定大小的数组赋值给elementData
  • 如果指定容量为0，则将elementData指向上面成员常量中的第一个空数组
  • 若指定容量为负数，则抛出异常

无参构造

public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

嗨！有没有发现不对啊？不是说好的默认容量是10吗？那这句话是嘛意思？这明显是是赋了一个空数组嘛……其实在之前的1.6版本中确实初始化时是10，你看：

public ArrayList() {
//这里调用第一个指定容量的构造方法，传入了10作为初始容量
this(10);
}

指定集合构造

public ArrayList(Collection<? extends E> c) {
//调用集合的toArray()方法将集合转为数组
elementData = c.toArray();
if ((size = elementData.length) != 0) {

if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}

这里主要是将传入的集合通过toArray()转为数组，然后赋值给elementData。4 容量与扩容继续说说默认容量这回事，如今的版本中数组初始化时的容量确实为0，作者把默认容量从初始化时延迟到了第一次添加元素时。

public boolean add(E e) {
//判断是否扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
//如果当前集合中元素为空，那么 选取 默认容量和最小容量 中的最大值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}

ensureExplicitCapacity(minCapacity);
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;

// 扩容时机：当容量全部被占用完时，那么进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}

抓住上面的3个重点：1. 添加元素时都会判断当前是否需要扩容2. 如果构造集合时指定默认容量，那么本次扩容到103. 只有当容量全部被占用时才会扩容（除主动扩容和第2条时）

private void grow(int minCapacity) {
int oldCapacity = elementData.length;

//新容量为原来的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);

//如果扩容1.5倍后还不满足需要的最小容量
// 那么就直接扩容到所需的最小容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//复制原来数组元素到一个新长度的数组中
elementData = Arrays.copyOf(elementData, newCapacity);
}

这段代码展示的是扩容到多大，oldCapacity >> 1 就相当于 oldCapacity/2, 把容量扩大到原来的1.5倍。5 遍历删除修改

List<String> list = new ArrayList<>(Arrays.asList("code","code","test","hello"));

错误一

for(inti=0;i<list.size();i++){
String a=list.get(i);
if (a.equals("code")) {
list.remove(a);
}
}

为什么第二个code没有被删除？你会发现它删除的元素之后的一个元素会被遍历跳过。因为删除元素后，其右边的所有元素都往前移动了一位，而你的下标却一直增加。

错误二

for (String s: list) {
if (s.equals("code")){
list.remove(s);
}
}

你将会得到一个ConcurrentModificationException异常。

错误三

list.forEach(s -> {
list.remove(s);
});

你同样得到一个ConcurrentModificationException异常。好吧，这下看出问题了，只要你在遍历list时调用自身的remove方法，都是不对的。

分析

错误二使用的其实是Iterator的方式遍历的，错误三使用的是forEach方法，我们看下源码都发现了一个共同之处：

int expectedModCount = modCount;
//省略步骤
if (modCount != expectedModCount)
throw new ConcurrentModificationException();

如果再遍历的过程中，modCount发生了改变(remove,set等)就会导出抛出异常。

正确方式

Iterator<Integer> iterator = list.iterator();
while (iterator.hasNext()){
Integer next = iterator.next();
iterator.remove();
}

为什么这样可以？因为 iterator.remove()方法在删除元素后，将下标回拨了一位。6 最后
  • ArrayList 的读取速度非常快，我想原因你应该知道了，这得益于底层的数组。
  • ArrayList 频繁扩容将会导致性能下降，因为每次扩容都会复制原来的数组到创建的新数组。
  • ArrayList 插入时会移动数组元素，插入越靠前，移动的元素就越多，效率越差。

源码阅读 在GItHub上：

flyhero/JDK8-Note?

github.com

推荐阅读（点击标题可跳转阅读）

1. 千万不要这样使用 Arrays.asList !

2. 八张图带你认识Java3. 不同时重写equals和hashCode又怎样！

推荐阅读：
相关文章