Java之ArrayList解剖学
- 2019 年 10 月 8 日
- 筆記
“ 一起来了解集合中ArrayList的源码实现 。” —— 23号老板
0
1
引入
先送一张图。好好珍藏~ (来自网络)

回归基础,回归原理,你会有更深的领悟。今天来聊一聊在Java当中常用的一个集合类:ArrayList。
在大学学习数据结构的时候,我们知道常见的一种数据结构,就是集合。而在Java中的集合,是用于存储对象的工具类容器,它实现了常用的数据结构,提供了一系列公开的方法用于增加、删除、修改、查找和遍历数据,降低了日常开发的成本,提高了开发效率。
从上面的框架图中可以看出,Java的集合主要分为两类。
1、按照单个元素存储的Collection,在其继承树中,Set、List都实现了Collection接口;
2、按照Key – Value存储的Map,也是当下最流行的一种数据结构,业内出现了以此为基础的各式Nosql数据存储层产品。
02
了解ArrayList
List集合是线性数据结构的主要实现,集合元素通常存在一个明确的元素关系,Pre、Next。因此,List集合的遍历结果是稳定的。ArrayList就是List集合中的一个实现类,在开发中也是最常使用的一个集合类。这里以最常使用的JDK8为例,如果有版本上的不一致,请参看对比。
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
也许你会在面试当中,常说到这样的话,和LinkedList作一次对比。ArrayList在使用上查询效率较高,新增元素的效率较低,balabala……然后就没什么可说的。再一问,这是为什么?不知道。

简单来说,ArrayList在内存上的存储,是利用了一个连续的存储空间,是一个顺序容器。即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。

ArrayList的几个实现。
1、实现RandomAccess类
其原理的本质就在于indexedBinarySerach(list,key)或iteratorBinarySerach(list,key)方法。你会发现实现RandomAccess接口的List集合采用一般的for循环遍历,而未实现这接口则采用迭代器。通过大量的测试可以知道,使用迭代器遍历集合的速度会比for循环遍历差。
2、实现Cloneable类
Cloneable是一个标记接口,只有实现这个接口后,然后在类中重写Object中的clone方法,然后通过类调用clone方法才能克隆成功,如果不实现这个接口,则会抛出CloneNotSupportedException(克隆不被支持)异常。
3、实现Serializable类
实现Serializable接口的作用是就是可以把对象存到字节流,然后可以恢复(反序列化),能够进行关于对象的网络传输方式。
0
3
深入理解
/** * 默认初始容量 */ private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; /** * 空表的表示方法 */ private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; /** * 底层的数组为elementData */ transient Object[] elementData; // non-private to simplify nested class access /** * ArrayList的大小 */ private int size; /** * 带有初始容量的构造器 */ public ArrayList(int initialCapacity) { if (initialCapacity > 0) {//大于0时创建一个initialCapacity大小的数组 this.elementData = new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); } } /** * 无参构造,默认空表数组 {} */ public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } /** * 当size大于0,采用Arrays.copyOf的复制方法赋值数组 */ public ArrayList(Collection<? extends E> c) { elementData = c.toArray(); if ((size = elementData.length) != 0) { // c.toArray might (incorrectly) not return Object[] (see 6260652) if (elementData.getClass() != Object[].class) elementData = Arrays.copyOf(elementData, size, Object[].class); } else { // replace with empty array. this.elementData = EMPTY_ELEMENTDATA; } }
03
add、remove等
ArrayList的底层是基于动态数组实现的原因,动态数组的意思就是指底层的数组大小并不是固定的,而是根据添加的元素大小进行一个判断,不够的话就动态扩容,扩容的代码就在ensureCapacity里。
/** * 确保在扩容时的容量 */ public void ensureCapacity(int minCapacity) { int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) // any size if not default element table ? 0 // larger than default for default empty table. It's already // supposed to be at default size. : DEFAULT_CAPACITY; if (minCapacity > minExpand) { ensureExplicitCapacity(minCapacity); } } /** * 数组的最大长度值,超过则OutOfMemoryError * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * 扩容,原数组长度的2倍+1,采用的Arrays.copyOf复制方法 */ 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); elementData = Arrays.copyOf(elementData, newCapacity); } public int size() { return size;} public boolean isEmpty() { return size == 0;} public boolean contains(Object o) { return indexOf(o) >= 0;}

空间的问题解决后,插入过程就显得非常简单。

/** * 获取index位置的元素 */ public E get(int index) { rangeCheck(index); return elementData(index); } /** * 替换index位置上的元素 */ public E set(int index, E element) { rangeCheck(index); E oldValue = elementData(index); elementData[index] = element; return oldValue; } /** * 新增元素 */ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } /** * 删除元素 */ public E remove(int index) { rangeCheck(index); modCount++; E oldValue = elementData(index); int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work return oldValue; } public boolean remove(Object o) { if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { for (int index = 0; index < size; index++) if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; } private void fastRemove(int index) { modCount++; int numMoved = size - index - 1; if (numMoved > 0) System.arraycopy(elementData, index+1, elementData, index, numMoved); elementData[--size] = null; // clear to let GC do its work }
删除是每次进行数组复制,然后让旧的elementData置为null进行垃圾回收。
以remove()方法为例。
可以看到这个 remove() 方法被重载了,一种是根据下标删除,一种是根据元素删除,这也都很好理解。
根据下标删除的 remove() 方法,大致的步骤如下:
1、检查有没有下标越界,就是检查一下当前的下标有没有大于等于数组的长度
2、列表被修改(add和remove操作)的次数加1
3、保存要删除的值
4、计算移动的元素数量
5、删除位置后面的元素向左移动,这里是用数组拷贝实现的
6、将最后一个位置引用设为 null,使垃圾回收器回收这块内存
7、返回删除元素的值
根据元素删除的 remove() 方法,大致的步骤如下:
1、元素值分为null和非null值
2、循环遍历判等
3、调用 fastRemove(i) 函数
a、修改次数加1
b、计算移动的元素数量
c、数组拷贝实现元素向左移动
d、将最后一个位置引用设为 null
e、返回 fase
4、返回 true

04
小结
现在,你对ArrayList是不是有了一个更深入的理解。深入源码,有时候能够让你更加理解代码的逻辑和数据结构。
文章部分内容来自网络博客,综合整理,在此鸣谢。