ArrayList
1、属性
//默认初始容量
private static final int DEFAULT_CAPACITY = 10;
//用于空实例的共享空数组实例。
private static final Object[] EMPTY_ELEMENTDATA = {};
//用于默认大小的空实例的共享空数组实例。我们将其与 EMPTY_ELEMENTDATA 区分开来，以了解添加第一个元素时要膨胀多少。
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//存储 ArrayList 元素的数组缓冲区。 ArrayList 的容量就是这个数组缓冲区的长度。当添加第一个元素时，任何具有 elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA 的空 ArrayList 都将扩展为 DEFAULT_CAPACITY。
transient Object[] elementData;
//ArrayList 的大小（它包含的元素数量）。
private int size;
2、构造器
//根据传入的初始化容量，创建 ArrayList 数组。如果我们在使用时，如果预先指到数组大小，一定要使用该构造方法，可以避免数组扩容提升性能，同时也是合理使用内存。
//比较特殊的是，如果初始化容量为 0 时，使用 EMPTY_ELEMENTDATA 空数组。在添加元素的时候，会进行扩容创建需要的数组。
public ArrayList(int initialCapacity) {
// 初始化容量大于 0 时，创建 Object 数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
// 初始化容量等于 0 时，使用 EMPTY_ELEMENTDATA 对象
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
// 初始化容量小于 0 时，抛出 IllegalArgumentException 异常
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
//构造一个初始容量为 10 的空列表(在第一次放数据add的时候才加载)
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
//使用传入的 c 集合，作为 ArrayList 的 elementData
public ArrayList(Collection c) {
// 将 c 转换成 Object 数组
elementData = c.toArray();
// 如果数组大小大于 0
if ((size = elementData.length) != 0) {
// 如果集合元素不是 Object[] 类型，则会创建新的 Object[] 数组，并将 elementData 赋值到其中
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
// 如果数组大小等于 0 ，则使用 EMPTY_ELEMENTDATA 。
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
3、添加单个元素
// 将指定的元素追加到此列表的末尾
public boolean add(E e) {
// 判断容量是否足够，不够进行扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将数据添加到尾部，并且size+1
elementData[size++] = e;
return true;
}
// 数组容量检查，不够时则进行扩容，只供类内部使用
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 返回需求的容量
private static int calculateCapacity(Object[] elementData, int minCapacity) {
// 若elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA，则取minCapacity为DEFAULT_CAPACITY和参数minCapacity之间的最大值。
// DEFAULT_CAPACITY在此之前已经定义为默认的初始化容量是10。
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 数组容量检查，不够时则进行扩容，只供类内部使用
// minCapacity 想要的最小容量
private void ensureExplicitCapacity(int minCapacity) {
// 记录数组操作次数
modCount++;
// overflow-conscious code
// 最小容量>数组缓冲区当前长度
if (minCapacity - elementData.length > 0)
// 扩容
grow(minCapacity);
}
// 扩容，保证ArrayList至少能存储minCapacity个元素
// 第一次扩容，逻辑为newCapacity = oldCapacity + (oldCapacity >> 1)右移1位，除以2;即在原有的容量基础上增加一半。
// 第一次扩容后，如果容量还是小于minCapacity，就将容量扩充为minCapacity。
private void grow(int minCapacity) {
// overflow-conscious code
// 获取当前数组的长度
int oldCapacity = elementData.length;
// 新容量等于原来的1.5倍(原值+原值右移1位，即0.5倍)
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 如果新容量小于最小需求容量
if (newCapacity - minCapacity < 0)
// 将新扩容容量扩容成最小需求容量
newCapacity = minCapacity;
// elementData就空数组的时候，length=0，那么oldCapacity=0，newCapacity=0，在这里就是真正的初始化elementData的大小了，就是为10.
// 如果扩容后的容量大于临界值，则进行大容量分配
if (newCapacity - MAX_ARRAY_SIZE > 0)
// 进行大容量分配
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
// 新的容量大小已经确定好了，就copy数组，改变容量大小。
// copyof(原数组，新的数组长度)
elementData = Arrays.copyOf(elementData, newCapacity);
}
//进行大容量分配
private static int hugeCapacity(int minCapacity) {
// 如果minCapacity<0，抛出异常
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
// 如果想要的容量大于MAX_ARRAY_SIZE，则分配Integer.MAX_VALUE(2147483647)，否则分配MAX_ARRAY_SIZE
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
// 插入单个元素到指定位置
public void add(int index, E element) {
// 检查当前位置是否合法
rangeCheckForAdd(index);
// 数组容量检查，不够时则进行扩容，只供类内部使用
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将 index + 1 位置开始的元素，进行往后挪
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 将数据放到指定位置
elementData[index] = element;
// size+1
size++;
}
// 检查当前位置是否合法
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//src 原数组
//srcPos 原数组起始位置下标
//dest 目标数组
//destPos 目标数组起始位置
//length 要复制的数组元素的数目
public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);
4、添加多个元素
// 批量添加多个元素。在我们明确知道会添加多个元素时，推荐使用该该方法而不是添加单个元素，避免可能多次扩容。
public boolean addAll(Collection c) {
// 将集合转成数组
Object[] a = c.toArray();
// 集合数量
int numNew = a.length;
// 数组容量检查，不够时则进行扩容, 操作数+1
ensureCapacityInternal(size + numNew); // Increments modCount
// 从原数组起始位置，复制到数据数组，从size开始
System.arraycopy(a, 0, elementData, size, numNew);
// size + numNew
size += numNew;
return numNew != 0;
}
// 在指定位置批量添加多个元素
public boolean addAll(int index, Collection c) {
// 检查当前位置是否合法
rangeCheckForAdd(index);
Object[] a = c.toArray();
int numNew = a.length;
// 数组容量检查，不够时则进行扩容, 操作数+1
ensureCapacityInternal(size + numNew); // Increments modCount
// 需要移动的数据个数
int numMoved = size - index;
if (numMoved > 0)
// 将index及之后的数据，移动到index + numNew的位置，一共numNewd个元素需要移动
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);
// 从原数组起始位置，复制到数据数组，从指定位置index开始
System.arraycopy(a, 0, elementData, index, numNew);
// size + numNew
size += numNew;
return numNew != 0;
}
5、删除单个元素
// 按照位置删除索引
public E remove(int index) {
// 检查当前位置是否合法
rangeCheck(index);
// 操作数+1
modCount++;
// 旧值
E oldValue = elementData(index);
// 需要移动的数量
int numMoved = size - index - 1;
if (numMoved > 0)
// 将index + 1开始的数据统一前移一位，及index的位置
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一位置null，size-1
elementData[--size] = null; // clear to let GC do its work
// 返回被删除的值
return oldValue;
}
// 按照值删除
public boolean remove(Object o) {
// o 为 null 的情况
if (o == null) {
// 遍历
for (int index = 0; index < size; index++)
if (elementData[index] == null) {
// 快速删除
fastRemove(index);
return true;
}
// o 不为 null 的情况
} else {
// 遍历
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
// 快速删除
fastRemove(index);
return true;
}
}
return false;
}
// 跳过边界检查且不返回值的删除方法
private void fastRemove(int index) {
// 操作次数+1
modCount++;
// 要移动的元素个数
int numMoved = size - index - 1;
if (numMoved > 0)
// 将index+1开始的numMoved个数的元素，移动到index开始
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
// 将最后一位置null，size-1
elementData[--size] = null; // clear to let GC do its work
}
6、删除多个元素
// 批量移除 [fromIndex, toIndex) 的多个元素,左闭右开
protected void removeRange(int fromIndex, int toIndex) {
// 操作次数+1
modCount++;
// 要移动的元素个数
int numMoved = size - toIndex;
// 将toIndex及之后的numMoved个元素，移动至formIndex开始
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
// 更新size
int newSize = size - (toIndex-fromIndex);
// 将删除掉的元素全部置null
for (int i = newSize; i < size; i++) {
elementData[i] = null;
}
// 返回删除元素的个数
size = newSize;
}
// 批量移除指定的多个元素
public boolean removeAll(Collection c) {
// 集合判空校验
Objects.requireNonNull(c);
// 批量删除
return batchRemove(c, false);
}
// 批量删除
private boolean batchRemove(Collection c, boolean complement) {
final Object[] elementData = this.elementData;
int r = 0, w = 0;
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.
// 当r和size不相等的时候(如果 contains 方法发生异常，则将剩下的数据从 r 位置的数据写入到从 w 开始的位置)
if (r != size) {
// 将r及之后的元素，复制到w及之后
System.arraycopy(elementData, r,
elementData, w,
size - r);
// w + (size - r)
w += size - r;
}
// 当w和size不相等的时候
if (w != size) {
// clear to let GC do its work
//将w及之后的数据全置空
for (int i = w; i < size; i++)
elementData[i] = null;
//操作次数
modCount += size - w;
// size改为w
size = w;
modified = true;
}
}
return modified;
}
// 清空数组
public void clear() {
// 操作数+1
modCount++;
// clear to let GC do its work
// for循环置空
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
7、查询操作
// 根据下标获取元素
public E get(int index) {
// 检查当前位置是否合法
rangeCheck(index);
// 返回
return elementData(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;
}
// 根据元素获取下标,遍历获取(获取最后一次出现的下标)
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;
}
// 设置指定下边的值,并返回旧值
public E set(int index, E element) {
// 检查当前位置是否合法
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
8、迭代器Iterator
//arrayList.iterator()
public Iterator iterator() {
return new Itr();
}
// 内部类AbstractList.Itr 的优化版本
private class Itr implements Iterator {
// 下一次访问元素的位置
int cursor; // index of next element to return
// 上一次访问元素的位置； 如果没有就返回-1
int lastRet = -1; // index of last element returned; -1 if no such
// 创建迭代器时，数组修改次数,如果这个过程中数组修改了 就会跑异常
int expectedModCount = modCount;
Itr() {}
// 判断是否还可以继续迭代
public boolean hasNext() {
// 判断下一次访问位置等于size吗
return cursor != size;
}
// 获取下一个元素
@SuppressWarnings("unchecked")
public E next() {
// 校验是否数组发生了变化
checkForComodification();
int i = cursor;
// 判断如果超过 size 范围，抛出 NoSuchElementException 异常
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
// 判断如果超过 elementData 大小，说明可能被修改了，抛出 ConcurrentModificationException 异常
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 指向下一个位置
cursor = i + 1;
// 返回当前位置的元素,lastRet指向当前位置
return (E) elementData[lastRet = i];
}
// 移除当前元素
public void remove() {
// 如果 lastRet 小于 0 ，说明没有指向任何元素，抛出 IllegalStateException 异常
if (lastRet < 0)
throw new IllegalStateException();
// 校验是否数组发生了变化
checkForComodification();
try {
// 移除 lastRet 位置的元素
ArrayList.this.remove(lastRet);
// cursor 指向 lastRet 位置，因为被移了，所以需要后退下
cursor = lastRet;
// lastRet 标记为 -1 ，因为当前元素被移除了
lastRet = -1;
// 更新数组的修改次数
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
// 就是对集合中剩余的元素进行操作，直到元素完毕或者抛出异常。这里重要的是剩余元素
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer consumer) {
// 判断
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
// 当有没有遍历的值且数组没有被修改过
while (i != size && modCount == expectedModCount) {
// 消费数据
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
// 在迭代结束时更新一次以减少堆写入流量
cursor = i;
lastRet = i - 1;
// 校验是否数组发生了变化
checkForComodification();
}
// 比较当前操作次数与创建时操作次数是否相同
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
