【Java】Java 源代码解析 | 集合类 | ArrayList
此篇主要解析 ArrayList 的源码处理逻辑
继承关系
几个有意思的参数
// 默认初始容量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;
为什么会有两个空数组
源代码中的解释：为了在添加第一个元素时，确定初始空间的大小。
此话怎讲？先从上述两变量的引用处说起。初始化一个 ArrayList 对象的构造函数有 3 个，分别如下
// 不带任何参数public ArrayList() {
// 当第一次添加元素时，元素个数小于10，初始容量置为10
this.elementData = DEFAULTCAPACITY_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);
}
}
// 从集合中添加
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;
}
}
可以看出，只有没有指明容量的情况下，才会使用 DEFAULTCAPACITY_EMPTY_ELEMENTDATA。且在添加第一个元素时，会进行相应的判断，如果为 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 就会使用默认的容量 10。
public boolean add(E e) {ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 由此看来，初始化的容量会因为上述两个空数组的不同而不同
ensureExplicitCapacity(minCapacity);
}
那为什么不能在 ArrayList() 中使用 EMPTY_ELEMENTDATA 呢？因为这样会与 ArrayList(int initialCapacity) 一样，但后者必须初始化成指定的容量，如 0。
为什么可以序列化却使用了transient修饰elementData
数组中所有的容量并非一直都被元素占用，可能会存在此数组大部分空间并未使用的情况，此时序列化所有的元素会比较浪费空间。因此在这里源码选择的是，将所有添加的元素，进行序列化。
private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
// ...
}
带参与不带参构造函数之间的差别是什么
添加第一个元素之后，容量不一样。
增加元素
增加元素到list当中，也就是我们常用的add()。有两种增加方式，一种是添加元素到尾端：
// 添加到列表的尾部public boolean add(E e) {
ensureCapacityInternal(size + 1);
// 此时elementData的长度已经被保证可以存下当前元素
elementData[size++] = e;
return true;
}
// 此函数的主要作用是确定列表初始容量
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}// 此处的解析如前面对初始容量那块所述
ensureExplicitCapacity(minCapacity);
}
// 检测是否需要扩容
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
//当前的minCapacity为size+1或10，所以当此条件成立时，说明再不扩容
//将有可能导致溢出
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 扩容
private void grow(int minCapacity) {
// 防止溢出
int oldCapacity = elementData.length;
// 右移1位，变成一半，因此此时的容量变成了之前的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
// 若新的容量比所需要的最小容量小，那么将新容量改成最小所需容量
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// 若新的容量比MAX_ARRAY_SIZE大
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// 分配新的数组，并将原数据拷贝到其中
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static int hugeCapacity(int minCapacity) {
// 此时已超过Integer.MAX_VALUE，变成负数，溢出
if (minCapacity < 0)
throw new OutOfMemoryError();
// 到这一步，有两个原因：
// 1. 通过扩容至原来的1.5倍，引起比MAX_ARRAY_SIZE大；
// 2. 此次加入的元素数量太多，以至于1.5倍的扩容也不能满足。
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :// 此处为第二种情况
MAX_ARRAY_SIZE;// 此处为第一种情况
}
一种是将元素添加元素到列表中的某一位置。
// 添加到列表中的某个位置public void add(int index, E element) {
rangeCheckForAdd(index);// 检查index是否合理，比如说超出当前size以及小于0
ensureCapacityInternal(size + 1); // 如前所述
// 将elementData中从index起的size-index个元素，依次拷贝到elementData中index+1起后续位置上
// 简而言之，就是从index位起，整体后移1位
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
// 复制到目标位置上
elementData[index] = element;
size++;
}
删除元素
删除确定元素（删除最先加入的那个元素，如果存在的话）
public boolean remove(Object o) {if (o == null) {// 为什么要做这个判断？为避免NullPointer
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;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
// 大于0说明：所删除的不是最后一项
// 因为其最多等于0，且为0时index为最后一项，即size - 1 == index.
if (numMoved > 0)// 从index+1项起，整体前移1位
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; //注意：此处置空的是最后一位。
}
删除指定下标的元素
public E remove(int index) {rangeCheck(index);//不要超过size
modCount++;
E oldValue = elementData(index);//先取出元素。为负数，如何处理？
int numMoved = size - index - 1;//计算其位置
if (numMoved > 0)
// 同前述
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // 同前述
return oldValue;//返回所删除的元素
}
批量删除元素。这两个函数的唯一差别在于传给batchRemove()的第二个参数，前者为false，后者为true。它们之间的差距，我们可以通过后续源码进行分析。
public boolean removeAll(Collection<?> c) {Objects.requireNonNull(c);// 处理为null情况
return batchRemove(c, false);
}
public boolean retainAll(Collection<?> c) {
Objects.requireNonNull(c);// 处理为null情况
return batchRemove(c, true);
}
批量处理删除
private boolean batchRemove(Collection<?> c, boolean complement) {final Object[] elementData = this.elementData;// 指向当前list元素数组
int r = 0, w = 0;
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
elementData[w++] = elementData[r];
// 体现差距的地方，就在这里：对于elementData中的每个元素，
// complement为true：c中存在，则将其移动到最前端；c中不存在，略过。
// 为false：c中存在，略过；c中不存在，保留。
} finally {
// r未达到size，说明中途遇到错误
if (r != size) {
// 将r到size的元素，保存到w后面
System.arraycopy(elementData, r,
elementData, w,
size - r);
w += size - r;
}
// w未达到size，说明需要删除某些元素；==size说明，全部保留，不作处理。
if (w != size) {
// 从w位开始，到size-1，全部置为空
for (int i = w; i < size; i++)
elementData[i] = null;
modCount += size - w;
size = w;
modified = true;
}
}
return modified;
}
清空列表
public void clear() {modCount++;
for (int i = 0; i < size; i++)
elementData[i] = null;// 全部置空
size = 0;
}
查询
访问非常便捷。
public E get(int index) {rangeCheck(index);
return elementData(index);
}
E elementData(int index) {
return (E) elementData[index];
}
修改
修改同样非常便捷。
public E set(int index, E element) {rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;//更新
return oldValue;//返回之前的值
}
关键的一些操作，感觉已经摸得差不多了。其它的一些查询、更新，都比较简单。
以上是 【Java】Java 源代码解析 | 集合类 | ArrayList 的全部内容， 来源链接： utcz.com/a/92085.html
