JDK13源码学习笔记——ArrayList
- 时间:
- 浏览:0
- 来源:跟我学网络
JDK版本：13
1 类图
1.1 实现接口
java.util.List：提供增删改查等基本操作java.io.Serializable：标记接口，表示支持序列化java.lang.Cloneable：标记接口，表示支持克隆java.util.RandomAccess：这个接口可能很少注意到，其实也是一个标记接口，表示能够随机访问元素，简单来说就是底层是数组实现的集合。参考：RandomAccess 这个空架子有何用？
1.2 继承
java.util.AbstractList：抽象类，从注释中可以看到，它提供了List接口的基本实现，以最大程度地减少迭代遍历相关操作的实现。不过ArrayList基本都重写了AbstractList提供的实现。
2 属性
int elementData：储存元素的数组，ArrayList的真实大小int size：elementData中实际存放元素的数量，我们经常调用的size()方法返回的也就是它
3 构造方法
3.1 ArrayList(int initialCapacity)
private static final Object[] EMPTY_ELEMENTDATA = {};
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，合理使用内存，避免数组扩容耗费性能。
3.2 ArrayList()
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
3.3 ArrayList(Collection<? extends E> c)
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
this.elementData = EMPTY_ELEMENTDATA;
}
}
4 主要方法
4.1 添加一个元素
boolean add(E e) 添加到尾部
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;
}
void add(int index, E element) 添加到指定位置
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;
}
4.2 扩容
Object[] grow()
private Object[] grow() {
return grow(size + 1);
}
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)];
}
}
4.3 添加多个元素
boolean addAll(Collection<? extends E> c) 向末尾添加
public boolean addAll(Collection<? extends E> c) {
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);
System.arraycopy(a, 0, elementData, s, numNew);
size = s + numNew;
return true;
}
boolean addAll(int index, Collection<? extends E> c) 向指定位置添加
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;
}
4.4 移除单个元素
E remove(int index) 移除指定位置的元素，并返回该元素
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;
}
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;
}
boolean remove(Object o) 移除首个为o的元素，返回是否移除
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;
}
4.5 移除多个元素
boolean removeAll(Collection<?> c) 如果元素在集合 c 中就移除
public boolean removeAll(Collection<?> c) {
return batchRemove(c, false, 0, size);
}
boolean batchRemove(Collection<?> c, boolean complement, final int from, final int end) 批量移除或保留元素
这个方法有点绕。先来看参数 complement，它表示如果一个元素在集合c中，他是保留还是删除。结合另一个方法
public boolean retainAll(Collection<?> c) { return batchRemove(c, true, 0, size); } 就很容易理解了，当complement为false时，是移除的逻辑。而为true时，是求两个集合的交集。
这个方法的大致逻辑是：（以移除为例）先找到第一个要移除的元素索引，记为w，它的下一位记为r。然后从r的位置开始遍历，如果是要删除的元素就跳过，如果是要保留的元素，就将它写到w指向的位置，覆盖之前的元素，再把w挪向下一位，继续遍历判断。最后再把数组末尾无用的元素置为null。下文代码后我贴了一张手绘图，可以结合起来理解。或者debug调试几次。
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;
}
private void shiftTailOverGap(Object[] es, int lo, int hi) {
System.arraycopy(es, hi, es, lo, size - hi);
for (int to = size, i = (size -= hi - lo); i < to; i++)
es[i] = null;
}
批量移除给定范围内的多个元素 void removeRange(int fromIndex, int toIndex)
protected void removeRange(int fromIndex, int toIndex) {
if (fromIndex > toIndex) {
throw new IndexOutOfBoundsException(
outOfBoundsMsg(fromIndex, toIndex));
}
modCount++;
shiftTailOverGap(elementData, fromIndex, toIndex);
}
根据条件移除元素 boolean removeIf(Predicate<? super E> filter)
略…
4.6 查找单个元素
int indexOf(Object o) 查找第一个指定元素的索引
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
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;
}
int indexOf(Object o) 查找最后一个指定元素的索引
public int lastIndexOf(Object o) {
return lastIndexOfRange(o, 0, size);
}
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;
}
int indexOf(Object o) 获得指定位置的元素
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
4.7 设置指定位置的元素
E set(int index, E element)
public E set(int index, E element) {
Objects.checkIndex(index, size);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
5 其他方法
5.1 转换为数组
Object[] toArray() 转换为Object[]
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
public static <T> T[] copyOf(T[] original, int newLength) {
return (T[]) copyOf(original, newLength, original.getClass());
}
Object[] toArray() 转换为给定泛型的数组
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;
}
对中间a[size] = null的疑惑作者在方法注释中有写到：
* <p>If the list fits in the specified array with room to spare
* (i.e., the array has more elements than the list), the element in
* the array immediately following the end of the collection is set to
* {@code null}. (This is useful in determining the length of the
* list <i>only</i> if the caller knows that the list does not contain
* any null elements.)
如果调用者明确知道数组中没有空元素，那么这对于确定list的length很有帮助。emmm…插入null值作为一个标记…或许调用者可以在遍历数组时判断元素为空就不再遍历了？？
5.2 求哈希值
int hashCode()
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;
}
private void checkForComodification(final int expectedModCount) {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
参考资料：田小波的技术博客——科普：String hashCode 方法为什么选择数字31作为乘子
5.3 判断相等
boolean equals(Object o)
public boolean equals(Object o) {
if (o == this) {
return true;
}
if (!(o instanceof List)) {
return false;
}
final int expectedModCount = modCount;
boolean equal = (o.getClass() == ArrayList.class)
? equalsArrayList((ArrayList<?>) o)
: equalsRange((List<?>) o, 0, size);
checkForComodification(expectedModCount);
return equal;
}
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;
}
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();
}
5.4 克隆
Object clone()
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);
}
}
5.5 清空
void clear()
public void clear() {
modCount++;
final Object[] es = elementData;
for (int to = size, i = size = 0; i < to; i++)
es[i] = null;
}
5.6 序列化与反序列化
void writeObject(java.io.ObjectOutputStream s) 序列化
@java.io.Serial
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
int expectedModCount = modCount;
s.defaultWriteObject();
s.writeInt(size);
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
elementData是加了transient关键字的，序列化时会只序列化size大小的真实使用的数组，不会序列化elementData预留出的那一部分。节省时间和空间。
void readObject(java.io.ObjectOutputStream s)
@java.io.Serial
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
s.defaultReadObject();
s.readInt();
if (size > 0) {
SharedSecrets.getJavaObjectInputStreamAccess().checkArray(s, Object[].class, size);
Object[] elements = new Object[size];
for (int i = 0; i < size; i++) {
elements[i] = s.readObject();
}
elementData = elements;
} else if (size == 0) {
elementData = EMPTY_ELEMENTDATA;
} else {
throw new java.io.InvalidObjectException("Invalid size: " + size);
}
}
6 End
省略了一些不常用的或简单的方法，以及逻辑重点不在ArrayList中的方法（比如sort()排序）。