1. 简介 ArrayList 是可以动态增长和缩减的索引序列，它是基于数组实现的 List 类。
该类封装了一个动态再分配的 Object[] 数组，每一个类对象都有一个 capacity 属性，表示它们所封装的 Object[] 数组的长度，当向 ArrayList 中添加元素时，该属性值会自动增加。如果向 ArrayList 中添加大量元素，可使用 ensureCapacity 方法一次性增加 capacity ，可以减少增加重分配的次数提高性能。
ArrayList 的用法和 Vector 相类似，但是 Vector 是一个较老的集合，具有很多缺点，不建议使用。另外，ArrayList 和 Vector 的区别是：ArrayList 是线程不安全的，当多条线程访问同一个 ArrayList 集合时，程序需要手动保证该集合的同步性，而 Vector 则是线程安全的。
【java源码赏析--java.util.ArrayList】size、isEmpty、get、set、iterator和listIterator操作的运行时间是常量。add操作对于添加n个元素，需要O(n)的时间。其他的操作需要线性时间。
1.1 继承关系

文章图片

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

• 继承 AbstractList 抽象父类，AbstractList提供了List接口的默认实现（个别方法为抽象方法）。
  
• 实现了 List 接口（规定了 List 的操作规范），List接口（extends Collection）定义了列表必须实现的方法。
  
• RandomAccess（可随机访问），是一个标记接口，用来标记可适用与随机访问算法的类。
  
• Cloneable（可拷贝），可以调用Object.clone方法返回该对象的浅拷贝。
  
• Serializable（可序列化）。
  

2. 源码分析 2.1 属性

//默认初始容量 private static final int DEFAULT_CAPACITY = 10; //空数组 private static final Object[] EMPTY_ELEMENTDATA = https://www.it610.com/article/{}; //默认空数组 private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; // 不会被序列化 transient Object[] elementData; //ArrayList实际元素容量 private int size; //最大容量 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

• ArrayList的默认容量DEFAULT_CAPACITY为10。
  
• 数据存放在elementData中，且访问级别为包内私有，是为了使内部类能够访问到其中的元素。并且被标记为transient，也就意味着在序列化的时候，此字段是不会被序列化的。
  
• size表示数组中元素的个数
  
• EMPTY_ELEMENTDATA与DEFAULTCAPACITY_EMPTY_ELEMENTDATA是为了在构造函数中初始化elementData使用的。
  
• MAX_ARRAY_SIZE为ArrayList最大分配容量。
  

2.2 构造函数

public ArrayList() { this.elementData = https://www.it610.com/article/DEFAULTCAPACITY_EMPTY_ELEMENTDATA; }

无参构造函数，elementData中没有元素，size为0，且elementData的长度也为0。使用DEFAULTCAPACITY_EMPTY_ELEMENTDATA为elementData赋值。

public ArrayList(int initialCapacity) { if (initialCapacity > 0) { this.elementData = https://www.it610.com/article/new Object[initialCapacity]; } else if (initialCapacity == 0) { this.elementData = EMPTY_ELEMENTDATA; } else { throw new IllegalArgumentException("Illegal Capacity: " + initialCapacity); } }

elementData中没有元素，size为0，不过elementData的长度有可能不同。使用EMPTY_ELEMENTDATA为elementData赋值。

public ArrayList(Collection c) { elementData = https://www.it610.com/article/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转化为数组，然后检查转化的类型，如果不是 Object[] 类型，使用 Arrays 类中的 copyOf 方法进行复制；同时，如果 c 中没有元素，使用 EMPTY_ELEMENTDATA 初始化。
2.3 主要方法
2.3.1 boolean add(E e) 确保容量足够后，在尾部添加一个元素

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

动态扩容 ensureCapacityInternal 在 Arraylist 中多次使用，着重理解。

private void ensureCapacityInternal(int minCapacity) {//第一次添加元素时，如果是无参构造函数构造而来，那么所需最小容量为DEFAULT_CAPACITY if (elementData =https://www.it610.com/article/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); }ensureExplicitCapacity(minCapacity); }

上面代码中if判断为了区分对象是由哪一种构造函数构造而来。第一次添加元素时需要确定最小扩容容量。而DEFAULTCAPACITY_EMPTY_ELEMENTDATA 与 EMPTY_ELEMENTDATA用来区分三个构造函数。

private void ensureExplicitCapacity(int minCapacity) { modCount++; //列表修改次数加1//如果所需最小容量大于数组长度时，才许真正扩容。 if (minCapacity - elementData.length > 0){ grow(minCapacity); } }

private void grow(int minCapacity) { 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 = https://www.it610.com/article/Arrays.copyOf(elementData, newCapacity); }

一般正常情况下，新的容量一般为旧容量的1.5倍(oldCapacity + (oldCapacity >> 1))。

private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) {// 这种情况，如何出现？ throw new OutOfMemoryError(); } return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE :MAX_ARRAY_SIZE; }

minCapacity 在超出最大限制时允许达到 Integer.MAX_VALUE，而不仅仅是Integer.MAX_VALUE - 8
2.3.2 void ensureCapacity(int minCapacity) 供外部调用的扩容方法。
在大致了解List大小时，可用此方法一次性增加minCapacity，这可以减少重分配次数，从而提高性能。

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

• 如果是通过无参构造函数构造且elementData中没有元素，则不需要扩容。
  
• 在ensureExplicitCapacity方法中，如果扩容大小小于elementData长度，则不需要扩容。
  

2.3.3 void add(int index, E element)

public void add(int index, E element) { rangeCheckForAdd(index); ensureCapacityInternal(size + 1); // System.arraycopy(elementData, index, elementData, index + 1, size - index); elementData[index] = element; size++; }

检查 index 是否数组越界。

private void rangeCheckForAdd(int index) { if (index > size || index < 0) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }private String outOfBoundsMsg(int index) { return "Index: "+index+", Size: "+size; }

1. 先调用 rangeCheckForAdd 检查索引是否合法。
2. 合法再调用上面讲过的 ensureCapacityInternal 执行扩容。
3. 调用系统的 arraycopy 函数将索引处及其后的元素后移一位。
4. 在 index 处插入该元素。

add(int index, E element)方法太耗时，主要体现在arraycopy上，一般别用。
2.3.4 boolean addAll(Collection c)

public boolean addAll(Collection 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; }

1. 将 c 转换为数组 a。
2. 调用 ensureCapacityInternal 动态扩容。
3. 调用系统函数 arraycopy。
4. 增加 elementData 的 size。
5. 有意思的小细节，numNew != 0，则返回 true。

疑惑点

• 为什么不从一开始就判断 numNew 的值呢，如果等于0，直接返回，后面的函数也就不用执行了？

2.3.5 boolean addAll(int index, Collection c)

public boolean addAll(int index, Collection c) { rangeCheckForAdd(index); Object[] a = c.toArray(); int numNew = a.length; ensureCapacityInternal(size + numNew); // Increments modCountint numMoved = size - index; if (numMoved > 0){ System.arraycopy(elementData, index, elementData, index + numNew, numMoved); }System.arraycopy(a, 0, elementData, index, numNew); size += numNew; return numNew != 0; }

1. 和 add(int index, E element) 一样，先调用 rangeCheckForAdd 检查索引合法性。
2. 将 c 转换为数组 a。
3. 调用 ensureCapacityInternal 扩容。
4. 如果插入位置不是 Arraylist 的末尾，则调用 arraycopy 将索引及其后的元素后移。
5. 将 a 的元素 arraycopy 到 elementData 中。
6. 增加 size。
7. numNew != 0，则返回true。

2.3.5 E get(int index)

public E get(int index) { rangeCheck(index); return elementData(index); }

注意和 rangeCheckForAdd的不同之处。

private void rangeCheck(int index) { if (index >= size) { throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); } }

1. 检查索引合法性。
2. 返回指定数据。

2.3.6 void clear()

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

1. 从结构上修改 此列表的次数加1；
2. for循环将每个元素置空；
3. size 置为0，elementData 的长度并没有修改，如果确定不再修改 list 内容之后最好调用 trimToSize 来释放掉一些空间）。

2.3.7 void trimToSize() 返回一个新数组，新数组不含null，数组的 size 和 elementData.length 相等，以节省空间。此函数可避免 size 很小但 elementData.length 很大的情况。

public void trimToSize() { modCount++; if (size < elementData.length) { elementData = https://www.it610.com/article/(size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }

2.3.8 int indexOf(Object o)

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

ArrayList 中可以添加 null，且可以在任意位置。
2.3.9 boolean contains(Object o)

public boolean contains(Object o) { return indexOf(o) >= 0; }

不建议使用 contains(Object o) 方法。效率极差。原因是通过for循环分别 equals
2.3.10 boolean containsAll(Collection c) 继承java.util.AbstractCollection 的 containsAll

public boolean containsAll(Collection c) { for (Object e : c) { if (!contains(e)) { return false; } } return true; }

不建议使用，效率更差。
2.3.11 int hashCode() 继承 java.util.AbstractList 的 hashCode

public int hashCode() { int hashCode = 1; for (E e : this) { hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); } return hashCode; }

2.3.12 Object clone() 返回ArrayList实例的浅拷贝

public Object clone() { try { ArrayList v = (ArrayList) super.clone(); v.elementData = https://www.it610.com/article/Arrays.copyOf(elementData, size); v.modCount = 0; return v; } catch (CloneNotSupportedException e) { // this shouldn't happen, since we are Cloneable throw new InternalError(e); } }

2.3.13 boolean remove(int index)

public E remove(int index) { rangeCheck(index); modCount++; E oldValue = https://www.it610.com/article/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 workreturn oldValue; }

• 检查索引合法性
• 通过 System.arraycopy 挪动数组
• size减一，并将elementData最后设为null

2.3.14 boolean remove(Object o)

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

由于 ArrayList 中可以存储 null，所以需要判断参数 o 是否为空的判断。
直观从代码上看，不建议使用此方法删除对象，性能太差。建议使用 boolean remove(int index)删除元素。

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 }

需要注意 fastRemove(int index) 与 boolean remove(int index)的区别，仅仅是没有返回值，作者为什么将相同的代码写两遍呢？
2.3.15 boolean removeAll(Collection c)

public boolean removeAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, false); }

判断对象是否为空

public static T requireNonNull(T obj) { if (obj == null){ throw new NullPointerException(); } return obj; }

batchRemove 这个类中最精妙的代码

private boolean batchRemove(Collection c, boolean complement) { final Object[] elementData = https://www.it610.com/article/this.elementData; int r = 0, w = 0; // r 用来遍历整个数组的索引w 用来标记需要替换的索引 boolean modified = false; try { for (; r < size; r++) { if (c.contains(elementData[r]) == complement) { elementData[w++] = elementData[r]; } } } finally { // Preserve behavioral compatibility with AbstractCollection, // even if c.contains() throws. if (r != size) { //一般情况下，不会出现这种情况。如果出现，则将拷贝数组。 System.arraycopy(elementData, r, elementData, w, size - r); w += size - r; } if (w != size) { // 如果 w != size， 则说明 w之后的元素都是需要丢弃掉的。而如果 w == size， 则说明没有发生替换，不需要删除。 // clear to let GC do its work for (int i = w; i < size; i++) { elementData[i] = null; } modCount += size - w; //本次修改次数就应该是 size - w size = w; //替换次数 = size modified = true; } } return modified; }

2.3.16 boolean retainAll(Collection c) 保留 c 中的元素，与 remoteAll 的区别在于 batchRemove(c, complement)。

public boolean retainAll(Collection c) { Objects.requireNonNull(c); return batchRemove(c, true); }

2.3.17 E set(int index, E element) 替换对应索引的元素

public E set(int index, E element) { rangeCheck(index); E oldValue = https://www.it610.com/article/elementData(index); elementData[index] = element; return oldValue; }

2.3.18 Object[] toArray() 浅拷贝

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

2.3.19 T[] toArray(T[] a)

public T[] toArray(T[] a) { if (a.length < size){ // Make a new array of a's runtime type, but my contents: return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } System.arraycopy(elementData, 0, a, 0, size); if (a.length > size){ a[size] = null; } return a; }

2.3.20 void sort(Comparator c)

public void sort(Comparator c) { final int expectedModCount = modCount; Arrays.sort((E[]) elementData, 0, size, c); if (modCount != expectedModCount) { throw new ConcurrentModificationException(); } modCount++; }

ConcurrentModificationException 是用来判断在数组排序时是否被修改。

推荐阅读

• 

  领克02空气滤芯多久换
• 

  奥迪a4轮胎规格 2015款奥迪a4轮胎规格
• 

  标签打印机连接手机 标签打印机连接mysql
• 

  马尔代夫玩什么
• 

  牛黄清心丸适合什么人吃 同仁堂牛黄清心丸
• 

  姜夔最著名的咏物词是什么
• 

  已经处理过的牛百叶怎么清洗 牛百叶应该怎么清洗
• 

  划水是什么意思
• 

  杨桃西米羹——健脾养胃利尿消肿
• 

  咸丰的皇后叫什么名字 咸丰皇帝的皇后
• 

  怪物猎人世界黑暗左右配装介绍 怪物猎人世界黑暗左右配装介绍视频
• 

  女生生日快乐祝福语 年轻女生生日快乐祝福语
• 

  2020开学后小饭桌还能开吗
• 

  天花板配置的2款手机,价格相差7600元,华为、苹果谁更值得买？
• 

  什么是生态水族缸？ 生态水族箱
• 

  可视域分析
• 

  泰日天是什么意思
• 

  儿童早睡早起顺口溜
• 

  日系二次元卡牌游戏有哪些游戏 日系二次元卡牌游戏有哪些
• 

  手机查车违章12123 12123怎么查违章

• JAVA（抽象类与接口的区别&重载与重写&内存泄漏）
• 事件代理
• Java|Java OpenCV图像处理之SIFT角点检测详解
• java中如何实现重建二叉树
• 数组常用方法一
• 【Hadoop踩雷】Mac下安装Hadoop3以及Java版本问题
• Android事件传递源码分析
• Java|Java基础——数组
• RxJava|RxJava 在Android项目中的使用（一）
• java之static、static|java之static、static final、final的区别与应用