ArrayList源码分析

1. 基本介绍

阿里面试官没想到一个ArrayList，我都能跟他扯半小时 ArrayList基于数组实现，是一个数组队列，相当于动态数组，相对于Java中的数组相比，他的容量可以动态增长

特点： 查询效率高，增删效率低，线程不安全。使用频率很高。

2. 使用方法

jdk在线api

3. 使用建议

也就是说ArrayList是Array的复杂版本，ArrayList内部封装了一个Object类型的数组，从一般的意义来说，它和数组没有本质的差别，甚至于ArrayList的许多方法，如Index、IndexOf、Contains、Sort等都是在内部数组的基础上直接调用Array的对应方法

1⃣️ 为什么要用ArrayList而不直接用Array

因为Array的容量固定，而ArrayList可以动态扩容

2⃣️ 内部的Object类型数组的影响

对于一般的引用类型来说，这部分的影响不是很大，但是对于值类型来说，往ArrayList里面添加和修改元素，都会引起装箱和拆箱的操作，频繁的操作可能会影响一部分效率。 但是恰恰对于大多数人，多数的应用都是使用值类型的数组。

消除这个影响是没有办法的，除非你不用它，否则就要承担一部分的效率损失，不过这部分的损失不会很大

3⃣️ 数组扩容的影响

构建新数组再把旧元素copy到新数组里面的开销是比较大的，我们可以在初始化的时候就根据所需容量进行初始化

4⃣️ 频繁的调用IndexOf、Contains等方法（Sort、BinarySearch等方法经过优化，不在此列）引起的效率损失

ArrayList是动态数组，它不包括通过Key或者Value快速访问的算法，所以实际上调用IndexOf、Contains等方法是执行的简单的循环来查找元素，所以频繁的调用此类方法并不比你自己写循环并且稍作优化来的快，如果有这方面的要求，建议使用Hashtable或SortedList等键值对的集合

4. 继承关系

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

1⃣️ List接口

在ArrayList实现了List接口，父类AbstractList也实现了相同的接口，开发这个collection 的作者Josh说：这其实是一个错误，他写这代码的时候觉得这个会有用处，但是其实并没什么用，但因为没什么影响，就一直留到了现在

2⃣️ RandomAccess接口

这是一个标记性接口（里面实际上没有方法需要被实现），它标志着提供了随机访问功能，即可以通过元素的序号快速获取元素对象

实现了该接口的话，那么使用普通的for循环来遍历（下标访问），性能更高，例如ArrayList。而没有实现该接口的话，使用Iterator来迭代，这样性能更高，例如linkedList。所以这个标记性只是为了让我们知道我们用什么样的方式去获取数据性能更好

3⃣️ Cloneable接口

即覆盖了函数clone()，能被克隆。

4⃣️ java.io.Serializable接口

这意味着ArrayList支持序列化，能通过序列化去传输；就是能够从类变成字节流传输，然后还能从字节流变成原来的类

5⃣️ AbstractList抽象类

为什么要先继承AbstractList，而让AbstractList先实现List？而不是让ArrayList直接实现List？

接口中全都是抽象的方法，而抽象类中可以有抽象方法，还可以有具体的实现方法，正是利用了这一点，让AbstractList是实现接口中一些通用的方法，而具体的类，如ArrayList就继承这个AbstractList类，拿到一些通用的方法，然后自己在实现一些自己特有的方法，这样一来，让代码更简洁，将继承结构最底层的类中通用的方法都抽取出来，先一起实现了，减少重复代码

5. 源码分析

5.1 成员变量

// 序列版本号 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; // 空对象数组 private static final Object[] EMPTY_ELEMENTDATA = {}; // 缺省空对象数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 元素数组 transient Object[] elementData; // 实际元素大小，默认为0 private int size; // 最大数组容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; }

可以看到底层是使用object数组来存储的，但是为什么 ArrayList 的 elementData 加上 transient 修饰？ 看一下ArrayList的修饰

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

可以看到 ArrayList 实现了 Serializable 接口，这意味着 ArrayList 支持序列化。transient 的作用是说不希望 elementData 数组被序列化，重写了 writeObject 实现： 每次序列化时，先调用 defaultWriteObject() 方法序列化 ArrayList 中的非 transient 元素，然后遍历 elementData，只序列化已存入的元素，这样既加快了序列化的速度，又减小了序列化之后的文件大小

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 array length* s.writeInt(elementData.length); *// 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(); }

5.2 构造方法

1⃣️ 无参构造方法：默认容量为空

arrayList1.7开始变化有点大，一个是初始化的时候，1.7以前会调用this(10)才是真正的容量为101.7即本身以后是默认走了空数组，只有第一次add的时候容量会变成10 // 数组大小为空 public ArrayList() { this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

2⃣️ 有参构造方法，参数是容量的大小

// ArrayList带容量大小的构造函数。 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); } }

针对上面带参数的构造哈函数有一个问题 至于为什么会这样，这是因为，当我们使用大小初始化list的时候，里面并没有对size进行赋值，而以后判断是否越界的操作都是针对size成员变量来判断的

3⃣️ 有参构造方法，指定初始数据初始化

// 创建一个包含collection的ArrayList 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; } }

c.toArray might (incorrectly) not return Object[] (see 6260652)意思就是：public Object[] toArray() 返回的类型不一定就是 Object[]，其类型取决于其返回的实际类型. Java笔记—c.toArray might (incorrectly) not return Object[] (see 6260652)官方Bug 6260652 这个编号代表JDK bug库中的编号。可以去官网查看bug详情：JDK-6260652 ArrayList 中 toArray() 的源码如下：

public Object[] toArray() { return Arrays.copyOf(elementData, size); }

该方法为什么返回的不一定就是 Object[] 呢？原因很简单，因为由于继承的原因，我们父类实例的具体类型，实际上是取决于在 new 时，我们所使用的子类类型

public static class Father { } public static class Son extends Father { } /** * 测试 java.lang.ArrayStoreException * - 父类(抽象类、接口)对象的实际类型，取决于其实例化时子类的类型 */ @org.junit.Test public void test1 () { Son[] sons = new Son[]{new Son(), new Son()}; System.out.println(sons.getClass()); // class[Lcom.johnnie.test.Test$Son; Father[] fathers = sons; System.out.println(fathers.getClass()); // class[Lcom.johnnie.test.Test$Son; fathers[0] = new Father(); // java.lang.ArrayStoreException }

对于 fathers[0] = new Father(); 这句话，为什么会报错？报错原因是因为 fathers 实际类型是 Son[]，由于数组中元素类型都是son类型的，因而会出现向下转型异常。也就是说假如我们有 1 个Object[]数组，并不代表着我们可以将Object对象存进去，这取决于数组中元素实际的类型

我们现在进行第二次测试，这次测试就会真正抛出这个官方错误，并且让我们知道为什么会报错。代码如下： ① 新建一个 MyList，该类继承 ArrayList

@SuppressWarnings("serial") public class MyList<E> extends ArrayList<E> { // toArray() 的同名方法 public String[] toArray() { return new String[]{"1", "2", "3"}; } } /** * 测试：c.toArray might (incorrectly) not return Object[] (see 6260652) 这个官方 bug */ @org.junit.Test public void test3() { List<String> ss = new LinkedList<String>(); // LinkedList toArray() 返回的本身就是 Object[] ss.add("123"); Object[] objs = ss.toArray(); objs[0] = new Object(); // 此处说明了：c.toArray might (incorrectly) not return Object[] (see 6260652) ss = new MyList<String>(); objs = ss.toArray(); System.out.println(objs.getClass()); // class [Ljava.lang.String; objs[0] = new Object(); // java.lang.ArrayStoreException: java.lang.Object }

当我们调用 List的 toArray() 时，我们实际上调用的是其具体实现类 MyList 中重写的 String[] toArray() 方法。因此，返回数组并不是 Object[] 而是 String[]，向下转型是不安全的，因此会抛出异常

5.3 核心方法

1⃣️ add()

① boolean add(E)(jdk1.7)

默认直接在末尾添加元素，先通过ensureCapacity()判断空间够不够，在ensureCapacity()方法里，modCount++，并判断之前数组的空间够不够，不够则把容量设置为 “(原始容量x3)/2 + 1”，调用Arrays.copyOf返回新数组，再去把size++的部分赋值

/** * Appends the specified element to the end of this list.添加一个特定的元素到list的末尾。 * * @param e element to be appended to this list * @return <tt>true</tt> (as specified by {@link Collection#add}) */ public boolean add(E e) { //确定内部容量是否够了，size是数组中数据的个数，因为要添加一个元素，所以size+1，先判断size+1的这个个数数组能否放得下，就在这个方法中去判断是否数组.length是否够用了。 ensureCapacity(size + 1); // Increments modCount!! //在数据中正确的位置上放上元素e，并且size++ elementData[size++] = e; return true; }

其中的ensureCapacity(int minCapacity)

// 确定ArrarList的容量。 // 若ArrayList的容量不足以容纳当前的全部元素，设置 新的容量=“(原始容量x3)/2 + 1” public void ensureCapacity(int minCapacity) { // 将“修改统计数”+1 modCount++; int oldCapacity = elementData.length; // 若当前容量不足以容纳当前的元素个数，设置 新的容量=“(原始容量x3)/2 + 1” if (minCapacity > oldCapacity) { Object oldData[] = elementData; int newCapacity = (oldCapacity * 3)/2 + 1; if (newCapacity < minCapacity) newCapacity = minCapacity; elementData = Arrays.copyOf(elementData, newCapacity);//复制指定的数组，用空值截断或填充（如有必要），以便复制具有指定的长度 } }

modCount是什么 modCount是父类AbstractList的成员变量，这个变量记录着集合的修改次数，在迭代器里会用到，因为ArrayList是线程不安全的，所以需要这个变量(后面会详讲)

② boolean add(E)(jdk1.8)

public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } 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; } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - 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); }

在扩容的时候，老版本的jdk和8以后的版本是有区别的，8之后的效率更高了，采用了位运算，右移一位，其实就是除以2这个操作。 1.7的时候*3/2+1 ，1.8直接就是*3/2'

③ void add(int，E)；在特定位置添加元素

public void add(int index, E element) { rangeCheckForAdd(index); modCount++; final int s; Object[] elementData; if ((s = size) == (elementData = this.elementData).length) elementData = grow(); System.arraycopy(elementData, index, elementData, index + 1, s - index); elementData[index] = element; size = s + 1; }

其中的System.arraycopy(elementData, index, elementData, index + 1, s - index)：就是将elementData在插入位置后的所有元素往后面移一位

public static void arraycopy(Object src,//src：源对象 int srcPos,//srcPos：源对象对象的起始位置 Object dest,//dest：目标对象 int destPos,//destPost：目标对象的起始位置 int length)//length：从起始位置往后复制的长度。 //复制src到dest，复制的位置是从src的srcPost开始，到srcPost+length-1的位置结束，复制到destPost上，从destPost开始到destPost+length-1的位置上，

2⃣️ remove(Object o)

ArrayList是允许加入null值的，所以删除也要先对null进行校验

public boolean remove(Object o) { // 如果要删除的值是 null，找到第一个值是 null 的删除 if (o == null) { for (int index = 0; index < size; index++) if (elementData[index] == null) { fastRemove(index); return true; } } else { // 如果要删除的值不为 null，找到第一个和要删除的值相等的删除 for (int index = 0; index < size; index++) // 这里是根据 equals 来判断值相等的，相等后再根据索引位置进行删除 if (o.equals(elementData[index])) { fastRemove(index); return true; } } return false; }

其中fastRemove(int index)，要记录一次list的改变（modCound++） numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去

private void fastRemove(int index) { // 记录数组的结构要发生变动了 modCount++; // numMoved 表示删除 index 位置的元素后，需要从 index 后移动多少个元素到前面去 // 减 1 的原因，是因为 size 从 1 开始算起，index 从 0开始算起 int numMoved = size - index - 1; if (numMoved > 0) // 从 index +1 位置开始被拷贝，拷贝的起始位置是 index，长度是 numMoved System.arraycopy(elementData, index+1, elementData, index, numMoved); //数组最后一个位置赋值 null，帮助 GC elementData[--size] = null; }

而迭代器的remove()方法再删除后会同步modCount

因为上面的赋复制的过程花销很大，所以ArrayList不做队列合适么，队列一般是FIFO（先入先出）的，如果用ArrayList做队列，就需要在数组尾部追加数据，数组头部删除数组

3⃣️ clear()

将elementData中每个元素都赋值为null，等待垃圾回收将这个给回收掉，所以叫clear

public void clear() { modCount++; // clear to let GC do its work for (int i = 0; i < size; i++) elementData[i] = null; size = 0; }

4⃣️ indexOf()方法

// 从首开始查找数组里面是否存在指定元素 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; }

5⃣️ get()方法

public E get(int index) { // 检验索引是否合法 rangeCheck(index); return elementData(index); }

5.4 modCount与线程安全问题

1⃣️ fali - fast

ArrayList 有线程安全问题的本质，是因为 ArrayList 自身的 elementData、size、modConut 在进行各种操作时，都没有加锁，而且这些变量的类型并非是可见（volatile）的，所以如果多个线程对这些变量进行操作时，可能会有值被覆盖的情况

modCount是父类AbstractList的成员变量，这个变量记录着集合的修改次数，在迭代器里会用到，用来保证迭代时的线程安全，当多个线程对同一个集合的内容进行操作时，就可能会产生线程安全问题，触发java集合的fail-fast错误机制

例如：当某一个线程A通过iterator去遍历某集合的过程中，若该集合的内容被其他线程所改变了；那么线程A访问集合时，就会抛出ConcurrentModificationException异常，产生fail-fast事件

或者你在单个线程对ArrayList边遍历边修改也会报错

@Test public void collectionTest(){ List list = new ArrayList<Integer>(); list.add(1); list.add(2); Iterator<Integer> iterator = list.iterator(); while (iterator.hasNext()){ Integer next = iterator.next(); if(next == 2){ list.remove(next); } } }

2⃣️ fail-fast原理

记得看remove()的源码时，发现remove的时候，modCount的值会改变 而在迭代器遍历的时候都会比较expectedModCount和modCount是否相等

public Iterator<E> iterator() { return new Itr(); } private class Itr implements Iterator<E> { int cursor; // index of next element to return int lastRet = -1; // index of last element returned; -1 if no such int expectedModCount = modCount; // prevent creating a synthetic constructor Itr() {} public boolean hasNext() { return cursor != size; } @SuppressWarnings("unchecked") public E next() { checkForComodification(); int i = cursor; if (i >= size) throw new NoSuchElementException(); Object[] elementData = ArrayList.this.elementData; if (i >= elementData.length) throw new ConcurrentModificationException(); cursor = i + 1; return (E) elementData[lastRet = i]; } public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } final void checkForComodification() { if (modCount != expectedModCount) throw new ConcurrentModificationException(); } }

不相等就会抛出ConcurrentModificationException()异常（add()、remove()，clear()，和其他涉及到修改集合中的元素个数的方法同理）

3⃣️ 如何解决

如果是在单线程里想要一边遍历一遍去删除ArrayList的元素，可以使用迭代器的remove()方法，因为他会同步expectedModCount和modCount public void remove() { if (lastRet < 0) throw new IllegalStateException(); checkForComodification(); try { ArrayList.this.remove(lastRet); cursor = lastRet; lastRet = -1; expectedModCount = modCount; } catch (IndexOutOfBoundsException ex) { throw new ConcurrentModificationException(); } } java.util.concurrent包中使用CopyOnWriteArrayList解决fail-fast ① 和ArrayList继承于AbstractList不同，CopyOnWriteArrayList没有继承于AbstractList，它仅仅只是实现了List接口。 ② ArrayList的iterator()函数返回的Iterator是在AbstractList中实现的；而CopyOnWriteArrayList是自己实现Iterator。 ③ ArrayList的Iterator实现类中调用next()时，会“调用checkForComodification()比较‘expectedModCount’和‘modCount’的大小”；但是，CopyOnWriteArrayList的Iterator实现类中，没有所谓的checkForComodification()，更不会抛出ConcurrentModificationException异常！

6. Arrays.asList()方法

Arrays.asList分析 浅谈Arrays.asList()方法的使用 首先，该方法是将数组转化为list。有以下几点需要注意：

该方法不适用于基本数据类型（byte,short,int,long,float,double,boolean）

该方法将数组与列表链接起来，当更新其中之一时，另一个自动更新

不支持add和remove方法

通过查看Arrays类的源码可以知道,asList返回的List是Array中的实现的内部类,而该类并没有定义add和remove方法.另外,为什么修改其中一个,另一个也自动获得更新了,因为asList获得List实际引用的就是数组

public class AsllistTest { public static void main(String[] args) { String[] s = {"aa","bb","cc"}; List<String> strlist = Arrays.asList(s); for(String str:strlist){ System.out.println(str); } System.out.println("------------------------"); //基本数据类型结果打印为一个元素 int[] i ={11,22,33}; List intlist = Arrays.asList(i); for(Object o:intlist){ System.out.println(o.toString()); } System.out.println("------------------------"); Integer[] ob = {11,22,33}; List<Integer> oblist = Arrays.asList(ob); for(int a:oblist){ System.out.println(a); } System.out.println("------------------------"); } } aa bb cc ---------------- [I@2524e205 ---------分割线---------- 22 --------------------

7. ArrayList和LinkedList哪个占用空间更大？

当面试官问我ArrayList和LinkedList哪个更占空间时，我这么答让他眼前一亮 ① LinkedList的Node节点占据空间更大 ② ArrayList每次扩容后为原来的1.5倍，可能有空间浪费 ③ ArrayList序列化的时候对Object[]数组是单独特殊处理的