ArrayList
ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制
底层数据结构
RandomAccess是一个标志接口，表明实现这个接口的List集合是支持快速随机访问的。在ArrayList中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问ArrayList实现了Cloneable接口 ，即覆盖了函数clone()，能被克隆ArrayList实现了java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
/**
* Default initial capacity.
* 初始化默认容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.
* 指定该 ArrayList 容量为 0 时，返回该空数组
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* Shared empty array instance used for default sized empty instances. We
* distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
* first element is added.
* 调用无参构造方法时，返回该数组。
* 与 EMPTY_ELEMENTDATA 的区别在于添加第一个元素时，我们能知道如何赋初始容量
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
* ArrayList 的容量大小就是该数组的长度
* 标记为transient，在对象被序列化的时候不会被序列化
* ArrayList 自定义了它的序列化和反序列化方式。详情请查看 writeObject(java.io.ObjectOutputStream s) 和 readObject(java.io.ObjectOutputStream s) 方法
*/
transient Object[] elementData; // non-private to simplify nested class access
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
* ArrayList的实际大小（数组包含的元素个数）
*/
private int size;
}
构造方法
ArrayList 提供了三种构造方法：
ArrayList()：构造一个默认容量为10的空列表ArrayList(int initialCapacity)：构造一个指定容量为initialCapacity的空列表ArrayList(Collection<? extends E> c)：构造一个包含指定collection的元素的列表，这些元素是按照该collection的迭代器返回它们的顺序排列的
ArrayList()
直接赋值 DEFAULTCAPACITY_EMPTY_ELEMENTDATA，表明这是一个默认容量为 10 的空列表
/**
* Constructs an empty list with an initial capacity of ten.
* 构造一个默认容量为 10 的空列表
* 等到后续 add 元素时候才会扩容赋值容量为 10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}ArrayList(int initialCapacity)
如果指定初始容量大于
0，则直接赋值一个指定大小的Object数组如果指定初始容量等于
0，则赋值为空数组EMPTY_ELEMENTDATA，与默认容量的空数组DEFAULTCAPACITY_EMPTY_ELEMENTDATA区分开来如果指定初始容量为负，则抛出非法参数异常
/**
* 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
* @throws IllegalArgumentException
* 如果指定的初始容量为负，则抛出这个异常
*/
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);
}
}ArrayList(Collection<? extends E> c)
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
* 构造一个包含指定 Collection 元素的列表，这些元素按照 Colletion 的迭代器返回顺序排列的
*
* @param c the collection whose elements are to be placed into this list
* @param c 其元素要放入此列表的集合
* @throws NullPointerException if the specified collection is null
*/
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;
}
}核心方法
| 方法名 | 时间复杂度 |
|---|---|
get(int index) | O(1) |
add(E e) | O(1) |
add(int index, E element) | O(n) |
remove(int index) | O(n) |
set(int index, E element) | O(1) |
get(int index)
ArrayList 底层是数组，所以它的 get 方法逻辑简单：
1、判断索引是否越界
2、直接通过数组下标获取元素
/**
* 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} 如果索引超出 size 则抛出越界异常
*/
public E get(int index) {
// 越界检查
rangeCheck(index);
// 返回索引为 index 的元素
return elementData(index);
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
* 检查给出的索引 index 是否在范围内。如果不在，抛出一个适当的运行时异常
* 这个方法并不检查index是否为负
* 如果给的索引 index >= size，则抛出一个越界异常
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}add(E e)
add(E e) 有两个步骤：
容量检查，是否需要扩容
插入元素
/**
* Appends the specified element to the end of this 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) {
// 确保 list 容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}容量检查、扩容逻辑：
1、进行容量检查，确定所需最小容量大小，判断是否需要扩容
2、第一次确定扩容容量，是原有容量的
1.5倍int newCapacity = oldCapacity + (oldCapacity >> 1)3、第二次确定扩容容量，如果第一次确定的扩容容量如果小于所需最小容量（
minCapacity），那就将容量大小变为所需最小容量（minCapacity）4、对确定的扩容容量大小进行判断，如果大于了最大容量
MAX_ARRAY_SIZE，则将容量设置为Integer类的最大值MAX_VALUE = 0x7fffffff
为什么进行二次容量确认？
为了确保扩容的容量足够
比如初始化ArrayList之后第一次添加数据，原数组长度为0，那么就算扩容后也还是0，所以扩容容量为所需最小容量
比如调用addAll()方法时，添加的集合很大，就算扩容为原数组1.5倍的容量也是不够的，甚至可能超过最大容量限制
/**
* 数组容量检查：确定所需最小容量大小
*/
private void ensureCapacityInternal(int minCapacity) {
// 调用无参构造方法创建 ArrayList 时，this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
// 也仅仅是初始化 ArrayList 后第一次添加元素才会有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
// 确定初始化最小容量，DEFAULT_CAPACITY 大小为 10，minCapacity 为添加元素最少需要的容量
// 采用 Math.max 比较是因为，addAll() 方法也是调用这个方法，如果第一次添加所需最小容量比 10 大，自然需要初始化容量为 minCapacity
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
/**
* 数组容量检查：判断数组是否需要扩容
*/
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
// 最小容量比当前数组长度大，则进行扩容
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* 分派给arrays的最大容量为什么要减去 8 呢？
* 因为某些VM会在数组中保留一些头字，尝试分配这个最大存储容量，可能会导致 array 容量大于 VM 的 limit，最终导致 OutOfMemoryError。
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
* 扩容，保证 ArrayList 至少能存储 minCapacity 个元素
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
// 获取当前数组容量
int oldCapacity = elementData.length;
// 新数组容量 = 当前数组容量 + 当前数组容量/2
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}Integer 类
public final class Integer extends Number implements Comparable<Integer> {
/**
* A constant holding the minimum value an {@code int} can
* have, -2<sup>31</sup>.
*/
@Native public static final int MIN_VALUE = 0x80000000;
/**
* A constant holding the maximum value an {@code int} can
* have, 2<sup>31</sup>-1.
*/
@Native public static final int MAX_VALUE = 0x7fffffff;
}add(int index, E element)
1、越界检查
2、确保容量足够
3、将指定下标以及后续位置元素往右挪一位
4、指定索引位置赋值元素
/**
* 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).
*
* 在列表中指定位置插入指定元素
* 将当前位置元素（如果存在）以及后续元素向右移动（将它们下标 +1）
*
* @param index index at which the specified element is to be inserted
* 要插入指定元素的索引
* @param element element to be inserted
* 要插入的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
* 如果索引超出 size，则抛出数组越界异常
*/
public void add(int index, E element) {
// 越界检查
rangeCheckForAdd(index);
// 确保数组内部容量足够
ensureCapacityInternal(size + 1); // Increments modCount!!
// 对数组进行复制处理，将 index 位置以及后续元素位移一个位置，空出 index 的位置后续插入 element
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 将指定的 index 位置赋值为 element
elementData[index] = element;
// 数组实际容量 ＋1
size++;
}
/**
* A version of rangeCheck used by add and addAll.
* add、addAll 方法使用时调用的越界检查版本
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}remove(int index)
1、检查索引是否越界。如果参数指定索引
index >= size，抛出一个越界异常2、将索引大于
index的元素左移一位（左移后，该删除的元素就被覆盖了，相当于被删除了）3、将索引为
size-1处的元素置为null（为了让GC起作用）
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* 移除列表中指定位置的元素
* 将后续元素向左移动（将它们下标 -1）
*
* @param index the index of the element to be removed
* 要移除元素的索引
* @return the element that was removed from the list
* 列表中移除的元素
* @throws IndexOutOfBoundsException {@inheritDoc}
* 指定索引 index >= size，则抛出越界异常
*/
public E remove(int index) {
// 越界检查
rangeCheck(index);
// 修改次数+1
modCount++;
// 获取移除索引元素
E oldValue = elementData(index);
// 删除指定元素后，需要左移元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// size-1，并将 size-1 处的元素置为 null。为了让 GC 起作用，显式将最后一个位置值设为 null
elementData[--size] = null; // clear to let GC do its work
// 返回被删除的元素
return oldValue;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*
* 越界检查
* 检查给出的索引 index 是否在范围内。如果不在，抛出一个适当的运行时异常
* 这个方法并不检查index是否为负
* 如果给的索引 index >= size，则抛出一个越界异常
*
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}set(int index, E element)
1、越界检查
2、记录被替换元素
3、替换元素（直接给指定索引位置元素赋新值）
4、返回被替换元素
/**
* 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}
* 指定索引 index >= size，则抛出越界异常
*/
public E set(int index, E element) {
// 越界检查
rangeCheck(index);
// 记录被替换元素
E oldValue = elementData(index);
// 替换元素
elementData[index] = element;
// 返回被替换元素
return oldValue;
}
/**
* Checks if the given index is in range. If not, throws an appropriate
* runtime exception. This method does *not* check if the index is
* negative: It is always used immediately prior to an array access,
* which throws an ArrayIndexOutOfBoundsException if index is negative.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}Fail-Fast 机制
ArrayList 也采用了快速失败的机制，通过记录 modCount 参数来实现。在面对并发的修改时，迭代器很快就会完全失败，而不是冒着在将来某个不确定时间发生任意不确定行为的风险