ArrayList 中的成员变量
elementData
ArrayList 数据存储在该数组中
transient Object[] elementData;
下文中 “数组” 一词指的就是 elementData
sizie
ArrayList 包含的元素个数
不是 elementData 的 length
private int size;
DEFAULT_CAPACITY
数组的默认初始容量大小。使用无参构造创建 ArrayList 时数组的默认容量
需要注意的的是，使用无参构造创建 ArrayList 后，只有当第一次往列表中添加元素时才会将数组容量扩容至 DEFAULT_CAPACITY
private static final int DEFAULT_CAPACITY = 10;
DEFAULTCAPACITY_EMPTY_ELEMENTDATA
用于默认大小的空实例的共享空数组实例
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
通俗讲就是：使用无参构造创建 ArrayList 时，elementData 的赋值
new ArrayList()
EMPTY_ELEMENTDATA
用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
通俗讲就是：使用有参构造创建 ArrayList 时，传入初始容量为 0 时，elementData 的赋值
new ArrayList(0)
MAX_ARRAY_SIZE
elementData 数组最大容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
预留 8 个比特，因为有些虚拟机会在数组中保存对象头信息
ArrayList 的构造器
无参构造
无参数构造直接将空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 赋值给 elementData
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
Q: 为什么源码注释中说构造一个长度为 10 的列表，而代码却是将空数组赋值给了
elementData?A: 使用无参构造创建 ArrayList 后，只有当第一次往列表中添加元素时才会将数组容量扩容至 10 （ DEFAULT_CAPACITY ）
有参数构造 ：指定初始容量
该构造器传入参数 initialCapacity ，指定 ArrayList 的初始容量
/**
* Constructs an empty list with the specified initial capacity.
*
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity is negative
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
// 如果传入初始容量大于 0，elementData 赋值为指定容量的数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
// 如果传入初始容量等于 0，elementData 赋值为空数组 EMPTY_ELEMENTDATA
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
有参数构造：包含指定集合元素
构造一个包含指定集合元素的列表，按集合的迭代器返回元素的顺序排列
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
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
elementData = EMPTY_ELEMENTDATA;
}
}
添加元素 add() 和扩容解析
public boolean add(E e) {
// 确保内部容量，需要时会进行扩容
ensureCapacityInternal(size + 1);
// 赋值
elementData[size++] = e;
return true;
}
add() 方法中，首先调用了 ensureCapacityInternal()方法，其作用是确保内部容量： 将当前用于存储 elementData 容量和执行 add() 方法后所需要的最小容量(size + 1, 即 ArrayList 元素个数 + 1)进行比较，判断是否需要扩容
查看 ensureCapacityInternal() 方法源码
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(
calculateCapacity(elementData, minCapacity)
);
}
在 ensureCapacityInternal() 方法中，调用了两个方法：
calculateCapacity(): 计算所需要的最小容量private static int calculateCapacity(Object[] elementData, int minCapacity) { /** * 若 elementData 为空数组 DEFAULTCAPACITY_EMPTY_ELEMENTDATA * 则最小需要空间至少为 DEFAULT_CAPACITY */ if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { return Math.max(DEFAULT_CAPACITY, minCapacity); } // 否则直接返回 minCapacity return minCapacity; }承接上文：使用无参构造创建 ArrayList 后，elementData 赋值为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA
当第一次往列表中添加元素时，才会将数组容量扩容至 10 （ DEFAULT_CAPACITY ）
ensureExplicitCapacity（）: 判断是否需要对elementData()进行扩容private void ensureExplicitCapacity(int minCapacity) { // 操作数 ++ modCount++; // 若最小需要容量大于当前 elementData 容量，则进行扩容 if (minCapacity - elementData.length > 0) grow(minCapacity); }
扩容方法 grow()
private void grow(int minCapacity) {
// 旧容量: elementData 容量
int oldCapacity = elementData.length;
// 新容量: 旧容量的 1.5 倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 新容量不满足最小所属容量，则新容量为最小所属容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 新容量大于最大容量，进入 hugeCapacity() 方法计算新容量
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 将数据拷贝到新数组，并重新赋值
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 最小所需容量大于最大容量，则新容量则为 Integer.MAX_VALUE，否则为 MAX_ARRAY_SIZE （）
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
add() 的重载
在指定的位置插入指定的元素，并将后续元素往右移 （下标 + 1）
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
// 检查 index 是否合法
rangeCheckForAdd(index);
// 确保内部容量，需要时会进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将指定位置原元素及其后续元素往右移
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 指定位置赋值
elementData[index] = element;
size++;
}
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
System.arraycopy()
一个本地方法，其作用是将一个数组中指定范围的元素 复制到指定数组中
/**
*
* @param src 源数组
* @param srcPos 源数组中的起始下标
* @param dest 目标数组
* @param destPos 目标数组中的起始下标
* @param length 需要复制的元素的个数
*/
public static native void arraycopy(Object src, int srcPos,
Object dest, int destPos,
int length);
批量添加元素 addAll()
将指定集合中的所有元素追加到 ArrayList 末尾
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(Collection<? extends E> 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;
}
从 ArrayList 的指定位置开始，将指定集合中的所有元素插入到 ArrayList 中。并将原来位于该位置的元素(如果有)和所有后续元素向右移动(增加它们的索引)
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {
// 检查索引合法性
rangeCheckForAdd(index);
// 将指定集合转数组
Object[] a = c.toArray();
// 确保内部容量，需要时会进行扩容
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
// 将原来位于 index 位置的元素(如果有)和所有后续元素右移
int 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;
}
获取元素get()
获取 ArrayList 指定位置元素
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
// 检查下标志是否合法
rangeCheck(index);
// 返回指定位置元素
return elementData(index);
}
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
替换元素 set()
替换 ArrayList 中指定位置的元素
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
// 检查下标值合法性
rangeCheck(index);
// 保存旧值
E oldValue = elementData(index);
// 替换新值
elementData[index] = element;
// 返回旧值
return oldValue;
}
删除元素 remove()
删除指定下标元素
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
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;
}
从列表中删除第一个出现的指定元素，如果不存在则列表不变
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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;
}
fastRemove()
跳过边界检查直接删除元素
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
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
}
批量删除元素 removeAll()
从 ArrayList 中移除指定集合中包含的所有元素。
/**
* Removes from this list all of its elements that are contained in the
* specified collection.
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {
// 校验传入参数是否为 null，为 null 抛出异常
Objects.requireNonNull(c);
// 移除元素
return batchRemove(c, false);
}
保留指定元素 retainAll()
从 ArrayList 中删除指定集合中不包含的所有元素
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {
// 校验传入参数是否为 null，为 null 抛出异常
Objects.requireNonNull(c);
// 移除元素
return batchRemove(c, true);
}
集合排序 sort()
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
// 期望操作数
final int expectedModCount = modCount;
// 调用 Arrays.sort() 方法进行排序
Arrays.sort((E[]) elementData, 0, size, c);
// 当前操作数与期望操作数不一致，快速失败（fail-fast）机制抛出并发修改异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// 操作数 ++
modCount++;
}
子列表视图 subList()
ArrayList的**subList()（它返回原来 list 的从 [fromIndex, toIndex) 之间这一部分的视图）**结果不可强转成ArrayList
因为该方法返回的是 ArrayList 的内部类
SubList, 并不是一个List而是一个视图，对 subList 的所有操作最终会反映到原列表上
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
清空列表 clear()
删除 ArrayList 中所有元素
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.
*/
public void clear() {
// 操作数 ++
modCount++;
// elementData 中所有值置 null，让 GC 回收
for (int i = 0; i < size; i++)
elementData[i] = null;
// 元素个数设置 0
size = 0;
}
获取元素个数 size()
public int size() {
return size;
}
判断空列表 isEmpty()
public boolean isEmpty() {
return size == 0;
}
获取列表中第一个匹配的元素下标 indexOf()
获取列表中第一个匹配元素的下标值，若无匹配元素则返回 -1
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
获取列表中最后一个匹配的元素下标 lastIndexOf()
返回指定元素最后一次出现的下标值，若无匹配元素则返回 -1
/**
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int lastIndexOf(Object o) {
if (o == null) {
for (int i = size-1; i >= 0; i--)
if (elementData[i]==null)
return i;
} else {
for (int i = size-1; i >= 0; i--)
if (o.equals(elementData[i]))
return i;
}
return -1;
}
是否包含指定元素 contains()
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
修剪列表 trimToSize()
将ArrayList 实例的容量 (即 elementData 容量) 修剪为 列表的当前大小(size)
应用程序可以使用此操作最小化 ArrayList 实例的存储
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
设置实际容量 ensureCapacity()
如果需要，增加这个 ArrayList 实例的容量，以确保它至少可以容纳最小容量参数指定的元素数量。
在往 ArrayList 添加大量元素之前，可以使用该方法设置容量，减少多次扩容带来的开销
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
浅拷贝 clone()
ArrayList 实现了 Cloneable 接口，覆盖了克隆方法 clone()，能被克隆
clone 方法返回 ArrayList 实例的浅拷贝副本
ArrayList 的浅拷贝：只拷贝元素的引用，不拷贝元素本身
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone();
v.elementData = Arrays.copyOf(elementData, size);
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}
集合转数组 toArray()
返回 ArrayList 中所有元素的数组
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public <T> 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;
}
阿里开发规范：使用集合转数组必须使用集合的toArray(T[] array)，传入的是类型完全一致，长度为0 的空数组（直接使用 toArray 无参方法存在问题，此方法返回值只能是 Object[]类，若强转其它类型数组将出现错误）
list.toArray(new Long[0])
过滤集合 removeIf()
条件过滤集合
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
int removeCount = 0;
final BitSet removeSet = new BitSet(size);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
if (filter.test(element)) {
removeSet.set(i);
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
i = removeSet.nextClearBit(i);
elementData[j] = elementData[i];
}
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
return anyToRemove;
}
示例
// 用户列表筛选管理员 list.removeIf(user -> user.isAdmin());
替换所有元素 replaceAll()
replaceAll() 方法用于将给定的操作内容替换掉数组中每一个元素
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
// 校验传入参数非空
Objects.requireNonNull(operator);
// 期望操作数
final int expectedModCount = modCount;
// 遍历集合，按照传入的规则对元素操作
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
// 当前操作数与期望操作数不一致，快速失败（fail-fast）机制抛出并发修改异常
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
示例
List<String> list = new ArrayList<>(); list.add("abc"); list.add("xyz"); list.add("cnm"); // 转大写 list.replaceAll(s -> s.toUpperCase());
本文含有隐藏内容，请 开通VIP 后查看