Created
August 6, 2018 08:05
-
-
Save fantasticmao/68258d17fe0dead18b816b5a750ba28c to your computer and use it in GitHub Desktop.
Comments for java.uitl.ArrayList base on JDK8
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package java.util; | |
...... | |
public class ArrayList<E> extends AbstractList<E> | |
implements List<E>, RandomAccess, Cloneable, java.io.Serializable | |
{ | |
// 内部数组的默认容量 | |
private static final int DEFAULT_CAPACITY = 10; | |
// 空数组,当 size == 0 时使用 | |
private static final Object[] EMPTY_ELEMENTDATA = {}; | |
// 空数组,当 size == DEFAULT_CAPACITY 时使用 | |
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; | |
// 内部数组,用于存放 ArrayList 元素 | |
transient Object[] elementData; | |
// 内部数组中的元素个数 | |
private int size; | |
// 记录链表的内部节点的改变次数 | |
// 用于抛出 ConcurrentModificationException,为了避免同时迭代和修改内部数组 | |
protected transient int modCount = 0; | |
public ArrayList(int initialCapacity) { | |
if (initialCapacity > 0) { | |
// new 内部数组 | |
this.elementData = new Object[initialCapacity]; | |
} else if (initialCapacity == 0) { | |
// 当 size == 0 时,替换内部数组为 EMPTY_ELEMENTDATA | |
this.elementData = EMPTY_ELEMENTDATA; | |
} else { | |
throw new IllegalArgumentException("Illegal Capacity: "+ | |
initialCapacity); | |
} | |
} | |
public ArrayList() { | |
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA; | |
} | |
public ArrayList(Collection<? extends E> c) { | |
elementData = c.toArray(); | |
if ((size = elementData.length) != 0) { | |
// 兼容 c.toArray() 可能没有(不正确地)返回 Object[] 情况 | |
if (elementData.getClass() != Object[].class) | |
elementData = Arrays.copyOf(elementData, size, Object[].class); | |
} else { | |
// 当 size == 0 时,替换内部数组为 EMPTY_ELEMENTDATA | |
this.elementData = EMPTY_ELEMENTDATA; | |
} | |
} | |
// ArrayList 扩容操作 | |
// 确认内部数组是否需要扩容 | |
public void ensureCapacity(int minCapacity) { | |
// 获当前取内部数组的容量 | |
// 若当前内部数组不是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,则容量为 DEFAULT_CAPACITY | |
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) | |
? 0 : DEFAULT_CAPACITY; | |
// 若当前内部数组的容量大于需要扩容的最小容量,则扩容内部数组 | |
if (minCapacity > minExpand) { | |
ensureExplicitCapacity(minCapacity); | |
} | |
} | |
// 计算内部数组需要扩容的容量 | |
private static int calculateCapacity(Object[] elementData, int minCapacity) { | |
// 若当前内部数组是 DEFAULTCAPACITY_EMPTY_ELEMENTDATA 时,则选择 DEFAULT_CAPACITY 和 minCapacity 的最大值 | |
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { | |
return Math.max(DEFAULT_CAPACITY, minCapacity); | |
} | |
return minCapacity; | |
} | |
private void ensureCapacityInternal(int minCapacity) { | |
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); | |
} | |
private void ensureExplicitCapacity(int minCapacity) { | |
modCount++; | |
if (minCapacity - elementData.length > 0) | |
grow(minCapacity); | |
} | |
private void grow(int minCapacity) { | |
// 新扩容的数组长度:旧数组长度 + 旧数组长度 / 2 | |
int oldCapacity = elementData.length; | |
int newCapacity = oldCapacity + (oldCapacity >> 1); | |
if (newCapacity - minCapacity < 0) | |
newCapacity = minCapacity; | |
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(); | |
return (minCapacity > MAX_ARRAY_SIZE) ? | |
Integer.MAX_VALUE : | |
MAX_ARRAY_SIZE; | |
} | |
// ArrayList 数组操作 | |
// 按升序判断元素在内部数组中的位置 | |
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; | |
} | |
// 按下标获取内部数组的元素 | |
@SuppressWarnings("unchecked") | |
E elementData(int index) { | |
return (E) elementData[index]; | |
} | |
// 按下标设置内部数组的元素,并返回旧元素值 | |
public E get(int index) { | |
// 校验参数 | |
rangeCheck(index); | |
return elementData(index); | |
} | |
// 按下标设置内部数组的元素,并返回旧元素值 | |
public E set(int index, E element) { | |
//校验参数 | |
rangeCheck(index); | |
E oldValue = elementData(index); | |
elementData[index] = element; | |
return oldValue; | |
} | |
// 添加新元素至内部数组的末尾位置 | |
public boolean add(E e) { | |
// 确认内部数组是否需要扩容 | |
ensureCapacityInternal(size + 1); // Increments modCount!! | |
elementData[size++] = e; | |
return true; | |
} | |
// 添加新元素至内部数组的指定下标位置 | |
public void add(int index, E element) { | |
// 校验参数 | |
rangeCheckForAdd(index); | |
// 确认内部数组是否需要扩容 | |
ensureCapacityInternal(size + 1); // Increments modCount!! | |
// 将内部数组 index 之后的元素向后移动一位 | |
System.arraycopy(elementData, index, elementData, index + 1, | |
size - index); | |
// 将新元素复制给内部数组的 index 下标位置 | |
elementData[index] = element; | |
// 更新 size | |
size++; | |
} | |
// 按下标删除内部数组的元素,并返回旧元素值 | |
public E remove(int index) { | |
// 校验参数 | |
rangeCheck(index); | |
modCount++; | |
E oldValue = elementData(index); | |
// 将内部数组 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; | |
} | |
// 按 o.equals() 匹配并删除内部数组的元素,并返回删除是否成功 | |
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; | |
} | |
// 移动内部数组 | |
private void fastRemove(int index) { | |
modCount++; | |
// 将内部数组 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 | |
} | |
// 集合的差集:删除内部数组中的指定元素 | |
public boolean removeAll(Collection<?> c) { | |
Objects.requireNonNull(c); | |
return batchRemove(c, false); | |
} | |
// 集合的交集:检索内部数组中的指定元素 | |
public boolean retainAll(Collection<?> c) { | |
Objects.requireNonNull(c); | |
return batchRemove(c, true); | |
} | |
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++) | |
// removeAll:将未匹配的元素保留下来 | |
// retainAll:将匹配的元素保留下来 | |
if (c.contains(elementData[r]) == complement) | |
elementData[w++] = elementData[r]; | |
} finally { | |
// Preserve behavioral compatibility with AbstractCollection, | |
// even if c.contains() throws. | |
if (r != size) { | |
System.arraycopy(elementData, r, | |
elementData, w, | |
size - r); | |
w += size - r; | |
} | |
if (w != size) { | |
// clear to let GC do its work | |
for (int i = w; i < size; i++) | |
elementData[i] = null; | |
modCount += size - w; | |
size = w; | |
modified = true; | |
} | |
} | |
return modified; | |
} | |
...... | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment