一、介绍 ArrayList 是 List 接口的可调整大小数组实现。实现了所有可选的 List 操作，并允许存储所有元素（包括 null）。除了实现 List 接口外，此类还提供了用于操作内部存储列表的数组大小的方法。
此类大致等同于 Vector，但它是非同步的。
size、isEmpty、get、set、iterator 和 listIterator 操作的运行时间是常数。add 操作的运行时间是摊销常数时间，即添加 n 个元素需要 O(n) 时间。其他所有操作的运行时间都是线性的（大致而言）。与 LinkedList 实现相比，常数因子较低。
什么是“摊销常数时间”（amortized constant time）？
摊销常数时间是一种算法分析中的术语，表示在某一系列操作的平均情况下，每个操作的时间复杂度是常数时间，即 O(1)，即使某些操作可能在最坏情况下花费更多时间。
在这种情况下，“摊销”意味着虽然某些操作可能需要较长时间（比如数组扩展），但如果把它和其他较快的操作平均分摊开来，整体的时间复杂度是常数。
每个 ArrayList 实例都有一个容量。容量是用于存储列表中元素的数组的大小。容量始终至少与列表大小相等。当元素添加到 ArrayList 时，其容量会自动增长。除了添加元素具有常数摊销时间成本外，增长策略的细节没有具体说明。
应用程序可以在添加大量元素之前使用 ensureCapacity 操作来增加 ArrayList 实例的容量。这样可以减少增量重新分配的次数。
此实现是非同步的 。如果多个线程同时访问一个 ArrayList 实例，并且至少有一个线程对列表进行结构性修改，则必须在外部进行同步。结构性修改是指添加或删除一个或多个元素，或显式调整支持数组的大小；仅设置元素的值不属于结构性修改。通常通过在某个封装列表的对象上进行同步来完成此操作。如果不存在这样的对象，则应使用 Collections.synchronizedList 方法将列表“包装”起来。最好在创建时进行此操作，以防止列表被意外地非同步访问：
1 List list = Collections.synchronizedList(new ArrayList (...));
此类的 iterator 和 listIterator 方法返回的迭代器是快速失败的：如果在创建迭代器后对列表进行了结构性修改，除非通过迭代器自身的 remove 或 add 方法进行修改，否则迭代器将抛出 ConcurrentModificationException。因此，在面对并发修改时，迭代器会快速且干净地失败，而不是在未来某个不确定的时间面临任意的、不确定的行为。
请注意，迭代器的快速失败行为不能得到保证，因为通常来说，在存在未同步的并发修改时不可能做出任何严格的保证。快速失败的迭代器会尽最大努力抛出 ConcurrentModificationException。因此，依赖此异常来保证程序的正确性是错误的：迭代器的快速失败行为应仅用于检测程序中的错误。
二、源码 1 2 3 4 5 public class ArrayList <E> extends AbstractList <E> implements List <E>, RandomAccess, Cloneable, java.io.Serializable { @java .io.Serial private static final long serialVersionUID = 8683452581122892189L ; }
1、属性 1 2 3 4 5 6 7 8 9 10 private static final int DEFAULT_CAPACITY = 10 ;private static final Object[] EMPTY_ELEMENTDATA = {};private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};transient Object[] elementData;private int size;
DEFAULT_CAPACITY，默认初始容量。
EMPTY_ELEMENTDATA，用于空实例的共享空数组实例。
DEFAULTCAPACITY_EMPTY_ELEMENTDATA，共享空数组实例用于默认大小的空实例。将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少。
elementData，存储 ArrayList 元素的数组缓冲区。ArrayList 的容量是此数组缓冲区的长度。添加第一个元素时，任何具有 elementData==DEFAULTCAPACITY_EMMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY。声明为非 private 的以便于简化嵌套类访问
size，ArrayList 的大小（它包含的元素数量）。
2、构造方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 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); } } public ArrayList () { this .elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; } public ArrayList (Collection<? extends E> c) { Object[] a = c.toArray(); if ((size = a.length) != 0 ) { if (c.getClass() == ArrayList.class) { elementData = a; } else { elementData = Arrays.copyOf(a, size, Object[].class); } } else { elementData = EMPTY_ELEMENTDATA; } }
提供了三个构造方法，分别为：
ArrayList(int initialCapacity)，构造一个具有指定初始容量的空列表。ArrayList()，构造一个初始容量为 10 的空列表。ArrayList(Collection<? extends E> c)，按照入参集合迭代器返回的顺序构造一个包含入参集合元素的列表。
3、位置访问操作 1 2 3 4 5 6 7 E get (int index) ; E set (int index, E element) ; void add (int index, E element) ;E remove (int index) ;
根据索引位置获取列表中的元素。
基础支持方法 elementData，只是简单地根据参数中的索引位置来从 ArrayList 的底层数组 elementData 中获取元素。
1 2 3 4 @SuppressWarnings("unchecked") E elementData (int index) { return (E) elementData[index]; }
3.1 get 1 2 3 4 public E get (int index) { Objects.checkIndex(index, size); return elementData(index); }
3.2 set 1 2 3 4 5 6 public E set (int index, E element) { Objects.checkIndex(index, size); E oldValue = elementData(index); elementData[index] = element; return oldValue; }
该方法将列表中指定位置的元素替换为指定元素，并返回该位置先前的元素。
3.3 add void add(int index, E element) 方法为对 List 接口中定义方法的实现，该方法会在此列表中的指定位置插入指定元素。将当前位于该位置的元素（如果有的话）和后续元素向右移动（将其索引加一）。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 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 ; }
3.4 remove 3.4.1 remove(int index) 1 2 3 4 5 6 7 8 9 10 11 public E remove (int index) { Objects.checkIndex(index, size); final Object[] es = elementData; @SuppressWarnings("unchecked") E oldValue = (E) es[index]; fastRemove(es, index); return oldValue; }
E remove(int index); 方法
该方法会删除此列表中指定位置的元素（可选操作）。将任何后续元素向左移动（从其索引中减去一）。并返回从列表中删除的元素。
3.4.2 私有方法 fastRemove 1 2 3 4 5 6 7 8 9 10 11 12 13 private void fastRemove (Object[] es, int i) { modCount++; final int newSize; if ((newSize = size - 1 ) > i) { System.arraycopy(es, i + 1 , es, i, newSize - i); } es[size = newSize] = null ; }
跳过边界检查且不返回已删除值的私有 remove 方法。
4、搜索元素操作 1 2 3 4 5 int indexOf (Object o) ;int lastIndexOf (Object o) ;
4.1 indexOf 1 2 3 public int indexOf (Object o) { return indexOfRange(o, 0 , size); }
int indexOf(Object o) 方法，返回此列表中指定元素第一次出现的索引，如果列表不包含该元素，则返回 -1。
更正式地说，返回满足 Objects.equals(o, get(i)) 的最低索引 i，如果没有这样的索引，则返回 -1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 int indexOfRange (Object o, int start, int end) { Object[] es = elementData; if (o == null ) { for (int i = start; i < end; i++) { if (es[i] == null ) { return i; } } } else { for (int i = start; i < end; i++) { if (o.equals(es[i])) { return i; } } } return -1 ; }
从上面的方法中可知，ArrayList 中的 indexOf 方法，是通过 for 循环遍历一遍列表来搜索元素的。
4.2 lastIndexOf 1 2 3 public int lastIndexOf (Object o) { return lastIndexOfRange(o, 0 , size); }
int lastIndexOf(Object o) 方法，返回此列表中指定元素最后一次出现的索引，如果列表不包含该元素，则返回 -1。
更正式地说，返回满足 Objects.equals(o, get(i)) 的最高索引 i，如果没有这样的索引，则返回 -1。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int lastIndexOfRange (Object o, int start, int end) { Object[] es = elementData; if (o == null ) { for (int i = end - 1 ; i >= start; i--) { if (es[i] == null ) { return i; } } } else { for (int i = end - 1 ; i >= start; i--) { if (o.equals(es[i])) { return i; } } } return -1 ; }
从上面的方法中可知，ArrayList 中的 lastIndexOf 方法，是通过 for 循环遍历一遍列表来搜索元素的，而遍历顺序是从后向前遍历，而 indexOf 方法为从前往后遍历。
5、迭代器 ArrayList 中定义了两个迭代器，分别是对 Iterator 和 ListIterator 接口的实现。两者的区别是：
Iterator 只能从前往后遍历集合，而 ListIterator 支持双向遍历ListIterator 支持添加元素，而 Iterator 不支持ListIterator 可以用 set 方法替换元素，而 Iterator 不支持ListIterator 可以获取元素索引
关于列表迭代器，请查看 迭代器 ListIterator | z2huo 文章中的内容。
关于迭代器，请查看 迭代器 Iterator | z2huo 文章中的内容。
6、实现 Collection 接口的方法 实现 Collection 接口的方法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 int size () ;boolean isEmpty () ;boolean contains (Object o) ;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 removeAll (Collection<?> c) ;boolean retainAll (Collection<?> c) ;void clear () ;
6.1 contains 方法 该方法用来判断列表中是否包含入参指定的元素，包含则返回 true
ArrayList 类中对 boolean contains(Object o); 方法的实现，是通过调用 ArrayList 中的 indexOf 方法来实现的，
1 2 3 public boolean contains (Object o) { return indexOf(o) >= 0 ; }
6.2 toArray 方法 返回一个数组，该数组中元素的顺序与列表中元素顺序相同（从第一个元素到最后一个元素）。
返回的数组将是 “安全的”，因为此列表不会维护对它的任何引用。（换句话说，此方法必须分配一个新数组）。因此，调用者可以自由地修改返回的数组。
1 2 3 public Object[] toArray() { return Arrays.copyOf(elementData, size); }
另一个 <T> T[] toArray(T[] a) 方法源码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 public <T> T[] toArray(T[] a) { if (a.length < size) { return (T[]) Arrays.copyOf(elementData, size, a.getClass()); } System.arraycopy(elementData, 0 , a, 0 , size); if (a.length > size) { a[size] = null ; } return a; }
需要注意入参数组长度大于等于列表大小的情况，下面有一个示例：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 public class SubListTest { public static void main (String[] args) { List<String> list = new ArrayList <>(List.of("1" , "2" , "3" , "5" , "6" , "9" )); String[] array = new String [8 ]; array[0 ] = "a" ; array[1 ] = "b" ; array[2 ] = "c" ; array[3 ] = "d" ; array[4 ] = "e" ; array[5 ] = "f" ; array[6 ] = "g" ; array[7 ] = "h" ; System.out.println(list); System.out.println(Arrays.toString(array)); System.out.println(array.getClass()); System.out.println(array); String[] listArray = list.toArray(array); System.out.println(Arrays.toString(listArray)); System.out.println(listArray); } }
输出结果如下：
1 2 3 4 5 6 [1, 2, 3, 5, 6, 9] [a, b, c, d, e, f, g, h] class [Ljava.lang.String; [Ljava.lang.String;@133314b [1, 2, 3, 5, 6, 9, null, h] [Ljava.lang.String;@133314b
可以看到，方法最后返回的数组还是原来的数组，替换了数组中的内容，将在列表容量范围内的元素替换为了列表中的元素，而超出列表范围的第一个元素赋值为 null，数组中之后的元素，则还为数组中的原始值。
6.3 add 方法 1 2 3 4 5 6 7 8 9 10 11 12 public boolean add (E e) { modCount++; add(e, elementData, size); return true ; } private void add (E e, Object[] elementData, int s) { if (s == elementData.length) elementData = grow(); elementData[s] = e; size = s + 1 ; }
boolean add(E e) 方法为对 Collection 接口中定义方法的实现，该方法会在列表的末尾添加元素。
6.4 remove 方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 public boolean remove (Object o) { final Object[] es = elementData; final int size = this .size; int i = 0 ; found: { if (o == null ) { for (; i < size; i++) { if (es[i] == null ) { break found; } } } else { for (; i < size; i++) { if (o.equals(es[i])) { break found; } } } return false ; } fastRemove(es, i); return true ; }
boolean remove(Object o) 方法是对 Collection 接口中定义方法的实现。该方法会从列表中移除查找到的第一次出现的指定元素。如果列表不包含该元素，则列表保持不变。
移除满足 Objects.equals(o, get(i)) 的最低索引 i 处的元素（如果存在这样的元素）。如果此列表包含指定元素则返回 true（或者等效地，如果此列表因该调用而发生改变）。
6.5 containAll 方法 boolean containsAll(Collection<?> c); 方法在此列表中包含入参集合中的所有元素时会返回 true
ArrayList 中的该方法继承自 AbstractCollection 抽象类
1 2 3 4 5 6 7 8 9 10 11 public abstract class AbstractCollection <E> implements Collection <E> { public boolean containsAll (Collection<?> c) { for (Object e : c) { if (!contains(e)) { return false ; } } return true ; } }
6.6 addAll 方法 boolean addAll(Collection<? extends E> c) 方法，该方法为对 Collection 接口中方法的实现。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 public boolean addAll (Collection<? extends E> c) { Object[] a = c.toArray(); modCount++; int numNew = a.length; return false ; } Object[] elementData; final int s; if (numNew > (elementData = this .elementData).length - (s = size)) { elementData = grow(s + numNew); } System.arraycopy(a, 0 , elementData, s, numNew); size = s + numNew; return true ; }
6.7 removeAll 方法 boolean removeAll(Collection<?> c)，该方法从此列表中删除入参指定集合中包含的所有元素。
1 2 3 public boolean removeAll (Collection<?> c) { return batchRemove(c, false , 0 , size); }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 boolean batchRemove (Collection<?> c, boolean complement, final int from, final int end) { Objects.requireNonNull(c); final Object[] es = elementData; int r; for (r = from;; r++) { if (r == end) { return false ; } if (c.contains(es[r]) != complement) { break ; } } int w = r++; try { for (Object e; r < end; r++) { if (c.contains(e = es[r]) == complement) { es[w++] = e; } } } catch (Throwable ex) { System.arraycopy(es, r, es, w, end - r); w += end - r; throw ex; } finally { modCount += end - w; shiftTailOverGap(es, w, end); } return true ; }
1 2 3 4 5 6 7 8 private void shiftTailOverGap (Object[] es, int lo, int hi) { System.arraycopy(es, hi, es, lo, size - hi); es[i] = null ; } }
6.8 retainAll 方法 1 2 3 public boolean retainAll (Collection<?> c) { return batchRemove(c, true , 0 , size); }
retainAll 方法与 removeAll 方法的不同之处在于，后者为从列表中删除入参集合中的元素，而前者为保留入参集合中的元素但删除未在入参集合中的元素。
两者都调用了 batchRemove 方法，只是因为 complement 参数的不同，而产生不同的遍历结果。
6.9 clear 方法 1 2 3 4 5 6 7 8 public void clear () { modCount++; final Object[] es = elementData; for (int to = size, i = size = 0 ; i < to; i++) { es[i] = null ; } }
clear() 方法会删除此列表中的所有元素。调用此方法之后，列表将会为空列表。
clear 方法会循环遍历列表，将列表中的每一个元素都赋值为 null，并且还会修改列表的 size 属性将其赋值为 0
7、子列表 SubList 1 2 3 4 5 public List<E> subList (int fromIndex, int toIndex) { subListRangeCheck(fromIndex, toIndex, size); return new SubList <>(this , fromIndex, toIndex); }
返回此列表中从 fromIndex（包含）到 toIndex（不包含）之间部分的视图。如果 fromIndex 和 toIndex 相等，则返回的列表为空。返回的子列表由基础列表支持，因此在返回列表中进行的非结构性更改会反映在基础列表中，反之亦然。返回的列表也支持所有可选的列表操作。
此方法消除了对显式范围操作的需要（这类操作通常存在于数组中）。对列表的操作都可以通过传递子列表视图而不是整个列表来进行范围操作。例如，以下用法可以从列表中删除一部分元素：
1 list.subList(from, to).clear();
类似的惯用法可以用于 indexOf(Object) 和 lastIndexOf(Object)，并且 Collections 类中的所有算法都可以应用于 subList。
如果通过返回的列表以外的方式对基础列表（即此列表）进行了结构性修改，则此方法返回的列表可能会出问题。结构性修改是指那些改变此列表大小的修改，或者以其他方式扰乱列表，使正在进行的迭代可能产生不正确的结果。
SubList 类的类层次图如下：
源码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 private static class SubList <E> extends AbstractList <E> implements RandomAccess { private final ArrayList<E> root; private final SubList<E> parent; private final int offset; private int size; public SubList (ArrayList<E> root, int fromIndex, int toIndex) { this .root = root; this .parent = null ; this .offset = fromIndex; this .size = toIndex - fromIndex; this .modCount = root.modCount; } }
SubList 类中定义的属性四个属性：
root，基础 ArrayList 列表的引用parent，子列表的父列表的引用（父列表也是 SubList），在子列表上调用 subList 方法时使用offset，子列表中第一个元素在基础列表 ArrayList 中的索引位置，也就是相对于基础列表的索引偏移量size，子列表的大小
以 get 方法为例，在调用子列表的方法时，实际上是根据 SubList 中存储的偏移量 offset 将对 SubList 的操作，转换为对基础列表 ArrayList 的操作。
1 2 3 4 5 public E get (int index) { Objects.checkIndex(index, size); checkForComodification(); return root.elementData(offset + index); }
8、批量操作之 addAll boolean addAll(int index, Collection<? extends E> c);
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public boolean addAll (int index, Collection<? extends E> c) { rangeCheckForAdd(index); Object[] a = c.toArray(); modCount++; int numNew = a.length; if (numNew == 0 ) { return false ; } Object[] elementData; final int s; if (numNew > (elementData = this .elementData).length - (s = size)) { elementData = grow(s + numNew); } int numMoved = s - index; if (numMoved > 0 ) { System.arraycopy(elementData, index, elementData, index + numNew, numMoved); } System.arraycopy(a, 0 , elementData, index, numNew); size = s + numNew; return true ; }
9、扩容操作 ArrayList 类中定义了 grow 方法，用来对列表进行扩容。方法在调用 add 方法或 addAll 方法时调用。
1 2 3 private Object[] grow() { return grow(size + 1 ); }
增加容量，以确保它至少可以容纳最小容量参数指定的元素数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 private Object[] grow(int minCapacity) { int oldCapacity = elementData.length; if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { int newCapacity = ArraysSupport.newLength(oldCapacity, minCapacity - oldCapacity, oldCapacity >> 1 ); return elementData = Arrays.copyOf(elementData, newCapacity); } else { return elementData = new Object [Math.max(DEFAULT_CAPACITY, minCapacity)]; } }
ArrayList 中使用的扩容方式是增量扩容，上面的代码中，oldCapacity >> 1 为旧容量大小除以 2，扩容时扩容为当前容量的 1.5 倍。
9.1 ArraysSupport.newLength 根据给定数组的当前长度、最小增长量和首选增长量来计算一个新的数组长度。该方法的计算是防止溢出的。
此方法由包含数组的对象使用，该数组可能需要增长以满足某些即使需求（即最小增长量），但也希望为未来的潜在需求预留更多空间（即首选增长量）。返回的长度通常限制在“软最大长度”内，以避免触及 JVM 的实现限制。然而，如果最小增长量要求超过“软最大长度”，“软最大长度”将被突破。如果首选增长量小于最小增长量，则使用最小增长量作为首选增长量。
首选长度是通过将首选增长量加到当前长度来确定的。如果首选长度未超过“软最大长度”（SOFT_MAX_ARRAY_LENGTH），则返回首选长度。如果首选长度超过了“软最大长度”，则使用最小增长量。最小所需长度是通过将最小增长量加到当前长度来确定的。如果最小所需长度超过了 Integer.MAX_VALUE，则此方法抛出 OutOfMemoryError。否则，此方法返回“软最大长度”或最小所需长度中的较大者。
需要注意的是，此方法本身不进行数组分配；它只执行数组长度的增长计算 。然而，正如上面所述，它仍会抛出 OutOfMemoryError。还要注意，此方法无法检测 JVM 的实现限制，它可能会计算并返回一个长度值，最大可达 Integer.MAX_VALUE，但该长度可能超过 JVM 的实现限制。在这种情况下，调用者可能会尝试以该长度进行数组分配，进而遇到 OutOfMemoryError。当然，不论此方法返回的长度是多少，如果堆空间不足以满足请求，调用者都可能遇到 OutOfMemoryError。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 public class ArraysSupport { public static final int SOFT_MAX_ARRAY_LENGTH = Integer.MAX_VALUE - 8 ; public static int newLength (int oldLength, int minGrowth, int prefGrowth) { int prefLength = oldLength + Math.max(minGrowth, prefGrowth); if (0 < prefLength && prefLength <= SOFT_MAX_ARRAY_LENGTH) { return prefLength; } else { int minLength = oldLength + minGrowth; if (minLength < 0 ) { throw new OutOfMemoryError ("Required array length " + oldLength + " + " + minGrowth + " is too large" ); } else if (minLength <= SOFT_MAX_ARRAY_LENGTH) { return SOFT_MAX_ARRAY_LENGTH; } else { return minLength; } } } }
9.2 Arrays.copyOf 1 2 3 4 5 6 7 8 public static <T> T[] copyOf(T[] original, int newLength) { return (T[]) copyOf(original, newLength, original.getClass()); }
该方法会复制入参中指定的数组，必要时进行截断或用 null 填充，以使复制后的数组具有指定的长度。对于在原数组和复制数组中都有效的索引，两者将包含相同的值。对于在复制数组中有效但在原数组中无效的索引，复制数组将包含 null。这种情况仅在指定长度大于原数组长度时出现。结果数组的类型与原数组完全相同。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 @IntrinsicCandidate public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T []> newType) { @SuppressWarnings("unchecked") T[] copy; if ((Object)newType == (Object)Object[].class) { copy = (T[]) new Object [newLength]; } else { copy = (T[]) Array.newInstance(newType.getComponentType(), newLength); } System.arraycopy(original, 0 , copy, 0 , Math.min(original.length, newLength)); return copy; }
9.3 手动扩容 扩容涉及到数组的重新分配和数据的复制，因此频繁扩容可能导致性能下降。在某些情况下，如果你知道会往 ArrayList 中添加大量元素，可以通过调用 ensureCapacity(int minCapacity) 方法来手动增加 ArrayList 的容量，避免频繁的扩容操作。
ensureCapacity 方法会增加此 ArrayList 实例的容量（如果有必要），以确保它至少能够容纳由 minimum capacity 参数指定的元素数量。
1 2 3 4 5 6 7 public void ensureCapacity (int minCapacity) { if (minCapacity > elementData.length && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA && minCapacity <= DEFAULT_CAPACITY)) { modCount++; grow(minCapacity); } }
10、来自 SequencedCollection 的方法 从 Java 21 开始，继承自 SequencedCollection 接口的方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 public void addFirst (E element) { add(0 , element); } public void addLast (E element) { add(element); } public E removeFirst () { if (size == 0 ) { throw new NoSuchElementException (); } else { Object[] es = elementData; @SuppressWarnings("unchecked") E oldValue = (E) es[0 ]; fastRemove(es, 0 ); return oldValue; } } public E removeLast () { int last = size - 1 ; if (last < 0 ) { throw new NoSuchElementException (); } else { Object[] es = elementData; @SuppressWarnings("unchecked") E oldValue = (E) es[last]; fastRemove(es, last); return oldValue; } }
11、equals 方法和 hashCode 方法 11.1 equals 方法 将指定的对象与此列表进行比较以确定是否相等。当且仅当指定对象也是一个列表，且两个列表的大小相同，并且两个列表中所有对应的元素对都相等时，返回 true。（如果 e1 和 e2 满足 Objects.equals(e1, e2)，则两个元素 e1 和 e2 被认为是相等的。）换句话说，如果两个列表包含相同顺序的相同元素，则它们被定义为相等。该定义确保 equals 方法在不同的 List 接口实现之间能够正常工作。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 public boolean equals (Object o) { if (o == this ) { return true ; } if (!(o instanceof List)) { return false ; } final int expectedModCount = modCount; if (o.getClass() == ArrayList.class) { equal = equalsArrayList((ArrayList<?>) o); } else { equal = equalsRange((List<?>) o, 0 , size); } checkForComodification(expectedModCount); return equal; }
equalsRange 方法代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 boolean equalsRange (List<?> other, int from, int to) { final Object[] es = elementData; if (to > es.length) { throw new ConcurrentModificationException (); } var oit = other.iterator(); for (; from < to; from++) { if (!oit.hasNext() || !Objects.equals(es[from], oit.next())) { return false ; } } return !oit.hasNext(); }
equalsArrayList 方法代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 private boolean equalsArrayList (ArrayList<?> other) { final int otherModCount = other.modCount; final int s = size; boolean equal; if (equal = (s == other.size)) { final Object[] otherEs = other.elementData; final Object[] es = elementData; if (s > es.length || s > otherEs.length) { throw new ConcurrentModificationException (); } for (int i = 0 ; i < s; i++) { if (!Objects.equals(es[i], otherEs[i])) { equal = false ; break ; } } } other.checkForComodification(otherModCount); return equal; }
11.2 hashCode 方法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 public int hashCode () { int expectedModCount = modCount; int hash = hashCodeRange(0 , size); checkForComodification(expectedModCount); return hash; } int hashCodeRange (int from, int to) { final Object[] es = elementData; if (to > es.length) { throw new ConcurrentModificationException (); } int hashCode = 1 ; for (int i = from; i < to; i++) { Object e = es[i]; hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); } return hashCode; }
上面有一个数字 31，为什么是 31 呢？
31 是一个质数。质数的选择可以减少哈希碰撞的可能性。质数有助于生成更均匀分布的哈希值，从而减少多个对象产生相同哈希值的概率，提高哈希算法的效率。
31 有优化的计算方式。在大多数处理器架构中，31 * i 可以被编译器优化为 i << 5 - i（即将 i 左移 5 位再减去 i）。这个优化减少了乘法的开销，提升了计算速度。
31 是一种经典且久经考验的选择。不仅仅是 ArrayList，在 Java 的 String 类的 hashCode 实现中也使用了 31 作为乘数。这种选择经过长时间的使用和研究，证明在多种情况下都表现良好。
12、clone 方法 clone 方法会返回此 ArrayList 实例的浅层拷贝副本，元素本身是不会被复制的。
1 2 3 4 5 6 7 8 9 10 11 public Object clone () { try { ArrayList<?> v = (ArrayList<?>) super .clone(); v.elementData = Arrays.copyOf(elementData, size); v.modCount = 0 ; return v; } catch (CloneNotSupportedException e) { throw new InternalError (e); } }
三、其他问题 1、列表中的 null 的问题 有下面这么一段代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 public class ClearTest { public static void main (String[] args) { List<String> list = new ArrayList <>(List.of("12" , "abc" , "dddd" , "dcc" )); System.out.println(list); list.clear(); System.out.println(list); List<String> list2 = new ArrayList <>(); list2.add(null ); list2.add(null ); list2.add(null ); list2.add(null ); System.out.println(list2); list2.clear(); System.out.println(list2); } }
上面程序的输出结果为：
1 2 3 4 [12, abc, dddd, dcc] [] [null, null, null, null] []
可以看到，ArrayList 中是可以添加进去 null 元素的。
1 2 3 4 5 6 7 public void clear () { modCount++; final Object[] es = elementData; for (int to = size, i = size = 0 ; i < to; i++) { es[i] = null ; } }
clear 方法在遍历列表并将每一个元素置为 null 的，也修改了列表的 size 属性为 0，这样在迭代器从列表中获取元素时，因判断 size 属性导致不会获取到元素，所以打印出来的是空列表。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 public abstract class AbstractCollection <E> implements Collection <E> { public String toString () { Iterator<E> it = iterator(); if (!it.hasNext()) { return "[]" ; } StringBuilder sb = new StringBuilder (); sb.append('[' ); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (!it.hasNext()) { return sb.append(']' ).toString(); } sb.append(',' ).append(' ' ); } } }
2、是否会缩小容量？ ArrayList 在添加元素时会扩大容量，实际上就是扩大底层数组的长度。但是在删除元素时，不会将底层数组的长度减小，删除时是将数组中的元素赋值为 null。
如果希望在删除大量元素后释放多余的内存，可以手动调用 trimToSize 方法。这个方法会将 ArrayList 的容量缩小到当前元素的数量，从而释放未使用的空间。
trimToSize 方法源码如下：
1 2 3 4 5 6 public void trimToSize () { modCount++; if (size < elementData.length) { elementData = (size == 0 ) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size); } }
相关链接 迭代器 Iterator | z2huo
迭代器 ListIterator | z2huo
OB links [[迭代器 Iterator]]
[[迭代器 ListIterator]]
#Java
