【java】Arraylist源码解读JDK1.8
程序员文章站
2022-06-04 18:56:46
...
本文旨在对Arraylist源码进行解读，对代码进行了逐行注释并且将遇到的问题做出说明。
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
import sun.misc.SharedSecrets;
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* Default initial capacity.默认初始容量。
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* Shared empty array instance used for empty instances.用于空实例的共享空数组实例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};//数组为空且数组长度为0
/**
* 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 = {};//数组为空但是数组长度为10
/**
* 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.
*/
transient Object[] elementData; // non-private to simplify nested class access非私有以简化嵌套类访问
// Object[]数组，就是储存元素的地方
/**
* The size of the ArrayList (the number of elements it contains).ArrayList的大小(它包含的元素的数量)。
*
* @serial
*/
private int size;//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
*/
public ArrayList(int initialCapacity) {//构造方法，elementData必定被赋值为一个Object数组
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];//创建一个Object数组其长度为initialCapacity，并将其首地址给elementData
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;//若initialCapacity长度等于0则直接用默认长度为0的空数组来初始化
} else {//长度为负数直接报异常
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* Constructs an empty list with an initial capacity of ten.构造一个初始容量为10的空列表
*/
public ArrayList() {//无参构造，要是外面没传递数组长度，则直接使用默认长度为10的空数组，elementData必定被赋值为一个Object数组
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.构造一个包含指定元素的列表
*集合，按照集合返回它们的顺序
*迭代器。
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public ArrayList(Collection<? extends E> c) {//构造，必定elementData为一个Object[]（根据c的长度区分）
elementData = c.toArray();//toArray后面会讲到，即把c转化成数组然后给elementData
if ((size = elementData.length) != 0) {//size是数组元素个数，即若数组元素个数等于数组长度但是不为0
// c.toArray might (incorrectly) not return Object[] (see 6260652)toArray可能(不正确地)不返回Object[](参见6260652)
if (elementData.getClass() != Object[].class)//若数组的类不是Object数组类
elementData = Arrays.copyOf(elementData, size, Object[].class);//复制出一个长度为元素个数，且类型为Object[]的数组
} else {//即若数组元素个数等于数组长度但是为0，则直接用默认长度为0的空数组来替代他
// replace with empty array.用空数组替换。
this.elementData = EMPTY_ELEMENTDATA;
}
}
//方法copyOf的源码：
/*public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {//参数分别是，原数组，新数组长度，新数组类型
@SuppressWarnings("unchecked")
// 若newType类型为Object[]类，则直接 new Object[newLength]
// 如果不是（即newType是泛型，那么三目判断条件不成立），则Array.newInstance(newType.getComponentType(), newLength);
T[] copy = ((Object)newType == (Object)Object[].class)
? (T[]) new Object[newLength]
// newType.getComponentType()可以得到数组类型
: (T[]) Array.newInstance(newType.getComponentType(), newLength);
// 复制的长度取原数组和新数组长度中的较小值，防止出现下标越界
System.arraycopy(original, 0, copy, 0,
Math.min(original.length, newLength));//将原数组下标从0开始的Math.min(original.length, newLength)长度的元素，复制到新数组下标从0开始往后。
return copy;
}*/
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
将此ArrayList实例的容量修剪为
*列表的当前大小。应用程序可以使用此操作最小化
*一个ArrayList实例的存储。
*/
public void trimToSize() {//如果数组元素个数小于数组长度，可以将多出来的空位置裁掉以节省空间
modCount++;//增加修改次数
if (size < elementData.length) {
elementData = (size == 0)//判断数组大小是否等于元素个数且为0，若为0则直接把数组设置成空数组。
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);//若不为0则根据元素个数创建一个新数组，新数组长度就是元素个数，其他不变
}
}
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
如果需要，增加这个<tt>ArrayList</tt>实例的容量，以确保它至少可以容纳由最小容量参数指定的元素数量。
*
* @param minCapacity the desired minimum capacity所需的最小容量
*/
public void ensureCapacity(int minCapacity) {//确认数组容量
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)//如果数组不是长度为10的空数组则值为0
// any size if not default element table任何大小，如果不是默认的元素表
? 0
// larger than default for default empty table. It's already
// supposed to be at default size.默认空表比默认值大。它应该是默认大小。
: DEFAULT_CAPACITY;//否则为10
if (minCapacity > minExpand) {//如果minCapacity大于数组容量，则对数组进行扩容
ensureExplicitCapacity(minCapacity);
}
}
private static int calculateCapacity(Object[] elementData, int minCapacity) {//该方法只给ensureCapacityInternal用，计算所需容量
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {//若数组等于默认10空数组
return Math.max(DEFAULT_CAPACITY, minCapacity);//则计算10和传过来的值中的较大值返回，用以底下判断是否需要扩容
}
return minCapacity;
}
private void ensureCapacityInternal(int minCapacity) {//从新确认内部容器大小是否需要扩容
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));//进行计算，然后决定是否扩容
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;//增加修改次数
// overflow-conscious code
if (minCapacity - elementData.length > 0)//如果所需容量大于数组容量则扩容
grow(minCapacity);
}
/**
* The maximum size of array to allocate.
* Some VMs reserve some header words in an array.
* Attempts to allocate larger arrays may result in
* OutOfMemoryError: Requested array size exceeds VM limit
*///数组的最大容量，可能会导致内存溢出(VM内存限制)
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.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {//扩容方法
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//对于二进制，1000右移一位相当于变成100也就是说2^4变为2^3就是除2
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);//生成扩容后的数组
// Arrays.copyOf（原数组，扩容后的长度，扩容后的类型）；本质是产生一个新数组，新数组的长度就是扩容后的长度，新数组中的元素就是原数组的内容（元素首地址）
//扩容后的类型如果没有就用原数组类型
//扩容后只是把数组长度加长，原数组的内容（元素首地址）还是保留复制到扩容后的数组。所以当hugeCapacity(minCapacity)返回值为
// Integer.MAX_VALUE时，即使大于最大的默认允许值但他仍会冒着风险去创建扩容数组。
}
private static int hugeCapacity(int minCapacity) {//判断是否溢出，这个方法基本上返回的都是Integer.MAX_VALUE，
//因为调用这个方法的条件是newCapacity - MAX_ARRAY_SIZE > 0
if (minCapacity < 0) // overflow外部所需最小容量为负数，直接抛异常
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?//若所需容量大于最大默认容量则返回Integr最大值：
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;//若容量小于最大默认则用最大默认，
}
/**
* Returns the number of elements in this list.返回列表中元素的数目。
*
* @return the number of elements in this list这个列表中的元素数量
*/
public int size() {//返回数组元素个数
return size;
}
/**
* Returns <tt>true</tt> if this list contains no elements.如果该列表不包含元素，则返回true。
*
* @return <tt>true</tt> if this list contains no elements如果此列表不包含任何元素
*/
public boolean isEmpty() {//判空
return size == 0;
}
/**
* Returns <tt>true</tt> if this list contains the specified element.
* More formally, returns <tt>true</tt> if and only if this list contains
* at least one element <tt>e</tt> such that
* <tt>(o==null ? e==null : o.equals(e))</tt>.
*
* @param o element whose presence in this list is to be tested
* @return <tt>true</tt> if this list contains the specified element
*/
public boolean contains(Object o) {//判断是否包含一个元素
return indexOf(o) >= 0;//若包含则indexOf(o)会得到该下标，所以值一定大于等于0返回true
}
/**
* Returns the index of the first occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
返回指定元素第一次出现的索引
*在该列表中，如果该列表不包含该元素，则为-1。
* More formally, returns the lowest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
public int indexOf(Object o) {//查找下标，只会返回第一个元素的位置，从前往后查找
if (o == null) {//如果该元素为null，查找
for (int i = 0; i < size; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = 0; i < size; i++)//遍历整个数组，看对象0是否等于某个元素，如果对应到了则返回下标
if (o.equals(elementData[i]))
return i;
}
return -1;//不包含则返回-1
}
/**返回指定元素最后一次出现的索引
*在该列表中，如果该列表不包含该元素，则为-1。
* Returns the index of the last occurrence of the specified element
* in this list, or -1 if this list does not contain the element.
* More formally, returns the highest index <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
* or -1 if there is no such index.
*/
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;
}
/**
* Returns a shallow copy of this <tt>ArrayList</tt> instance. (The
* elements themselves are not copied.)返回此ArrayList实例的浅拷贝。(
*不会复制元素本身。也就是说只是复制一个数组，但是数组里的元素都直接复制首地址而不是本身
*
* @return a clone of this <tt>ArrayList</tt> instance
*/
public Object clone() {//克隆得到一个新数组
try {
ArrayList<?> v = (ArrayList<?>) super.clone();//调用Object的clone方法
v.elementData = Arrays.copyOf(elementData, size);//根据本数组及其元素个数复制出一个新的数组
v.modCount = 0;
return v;
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable这不应该发生，因为我们是可克隆的
throw new InternalError(e);
}
}
/**
* Returns an array containing all of the elements in this list
* in proper sequence (from first to last element).
返回一个包含列表中所有元素的数组
*顺序正确(从第一个元素到最后一个元素)。
*
* <p>The returned array will be "safe" in that no references to it are
* maintained by this list. (In other words, this method must allocate
* a new array). The caller is thus free to modify the returned array.
返回的数组将是“安全的”，因为没有对它的引用
*由本列表维护。(换句话说，这个方法必须分配
*新数组)。因此，调用者可以*地修改返回的数组。
*
*
* <p>This method acts as bridge between array-based and collection-based
* APIs.这种方法充当了基于数组和基于集合之间的桥梁
*
* @return an array containing all of the elements in this list in包含列表中所有元素的数组
* proper sequence
*/
public Object[] toArray() {//将他整合成数组
return Arrays.copyOf(elementData, size);//根据默认数组，复制出一个新的数组其长度为元素个数，类型为elementData数组类型
}
/**
* Returns an array containing all of the elements in this list in proper
* sequence (from first to last element); the runtime type of the returned
* array is that of the specified array. If the list fits in the
* specified array, it is returned therein. Otherwise, a new array is
* allocated with the runtime type of the specified array and the size of
* this list.
返回一个包含列表中所有元素的数组
*序列(从第一个元素到最后一个元素);返回的运行时类型
*数组是指定数组的数组。如果列表符合
*指定的数组，它在其中返回。否则，新数组为
*指定数组的运行时类型和的大小
*这个列表。
*
* <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
* <tt>null</tt>. (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.)
如果列表符合指定的数组，则有多余的空间
*(即。，数组中的元素比列表中的元素多)
*集合结束后的数组被设置为
* < tt >空< / tt >。(这在确定的长度是有用的
//就是说，你集合中的数比数组长度小，则数组多余出来的空间直接全设置为0
*
* @param a the array into which the elements of the list are to
* be stored, if it is big enough; otherwise, a new array of the
* same runtime type is allocated for this purpose.
* @return an array containing the elements of the list
* @throws ArrayStoreException if the runtime type of the specified array
* is not a supertype of the runtime type of every element in
* this list
//返回一个数组，使用运行时确定类型，该数组包含在这个列表中的所有元素（从第一到最后一个元素）
//返回的数组容量由参数和本数组中较大值确定
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {//将元素保存到a数组里
if (a.length < size)//若元素个数大于a数组的长度，即a数组不够存会造成数据丢失
// Make a new array of a's runtime type, but my contents:创建一个新的数组的运行时类型，
return (T[]) Arrays.copyOf(elementData, size, a.getClass());//则生成一个新数组，新数组的长度为元素个数，新数组的类型为a
//，即得到一个a数组类型不变的扩容版本
System.arraycopy(elementData, 0, a, 0, size);//若a数组的大小等于或大于元素个数，则直接进行
if (a.length > size)//长度剩余部分进行处理
a[size] = null;
return a;
}
// Positional Access Operations位置访问操作
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];//返回数组对应下标的元素
}
/**
* 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}
*/
public E get(int index) {//根据下标获得对应元素
rangeCheck(index);//检查是否下标越界
return elementData(index);
}
/**
* 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}
*/
public E set(int index, E element) {
rangeCheck(index);//检查下标越界
E oldValue = elementData(index);//取得对应下标的原始元素
elementData[index] = element;//将新元素加进去
return oldValue;//返回原始元素
}
/**
* 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) {//将指定的元素追加到此列表的末尾。
ensureCapacityInternal(size + 1); // Increments modCount!!先将元素个数加一，传递回去重新计算是否扩容，并增加修改次数
elementData[size++] = e;//将元素放入个数下标加一的位置
return true;//返回成功
}
/**
* 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).
*将指定元素插入其中的指定位置
*列表。移动当前处于该位置的元素(如果有)并
*任何向右的后续元素(将一个元素添加到它们的索引中)。
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);//检查下标越界
ensureCapacityInternal(size + 1); // Increments modCount!!判断是否扩容
System.arraycopy(elementData, index, elementData, index + 1,
size - index);//将index和其后的元素往后移动一
elementData[index] = element;
size++;
}//大家可能会想到问题若size为Integer最大值，加一后变为负数，将不会导致扩容行为产生，即方法失败，这个问题在Arrylist11版本已经做出修改
/**
* 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}
*/
public E remove(int index) {//删除指定位置元素
rangeCheck(index);
modCount++;
E oldValue = elementData(index);//取出原始位置元素
int numMoved = size - index - 1;//计算需要移动的元素个数
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//把下标index之后的numMoved个元素全部复制下来，覆盖到从下标为index开始的元素
elementData[--size] = null; // clear to let GC do its work把原来下标最后一个位置处的空间设置为null
return oldValue;//返回被移除的值
}
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that从列表中删除指定元素的第一个匹配项，
如果它存在
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
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 remove method that skips bounds checking and does not
* return the value removed.私有删除方法，该方法跳过界限检查而不跳过
*/
private void fastRemove(int index) {//上面remove的简化版，不用进行下标判断
modCount++;
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
}
/**
* Removes all of the elements from this list. The list will
* be empty after this call returns.从列表中删除所有元素。将列表
调用返回后为空。
*/
public void clear() {//全部清除
modCount++;
// clear to let GC do its work清除，让GC做它的工作
for (int i = 0; i < size; i++)
elementData[i] = null;
size = 0;
}
/**
* Appends all of the elements in the specified collection to the end of
* this list, in the order that they are returned by the
* specified collection's Iterator. The behavior of this operation is
* undefined if the specified collection is modified while the operation
* is in progress. (This implies that the behavior of this call is
* undefined if the specified collection is this list, and this
* list is nonempty.)
将指定集合中的所有元素按照指定集合的迭代器返回它们的顺序追加到此列表的末尾。如果在操作过程中修改了指定的集合，
则此操作的行为未定义。(这意味着，如果指定的集合是这个列表，而这个列表不是空的，则此调用的行为是未定义的。)
*
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws NullPointerException if the specified collection is null
*///添加一个集合的元素到末端，若要添加的集合为空返回false
public boolean addAll(Collection<? extends E> c) {//将一个集合添加到数组末尾
Object[] a = c.toArray();//将c变成Object[]数组
int numNew = a.length;//添加的个数
ensureCapacityInternal(size + numNew); // Increments modCount//判断是否需要扩容
System.arraycopy(a, 0, elementData, size, numNew);//把a从0开始的所有元素复制到elementData末尾
size += numNew;
return numNew != 0;//返回判断添加的个数是否为0
}
/**
* Inserts all of the elements in the specified collection into this
* list, starting at the specified position. Shifts the element
* currently at that position (if any) and any subsequent elements to
* the right (increases their indices). The new elements will appear
* in the list in the order that they are returned by the
* specified collection's iterator.
*
* @param index index at which to insert the first element from the
* specified collection
* @param c collection containing elements to be added to this list
* @return <tt>true</tt> if this list changed as a result of the call
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws NullPointerException if the specified collection is null
*/
public boolean addAll(int index, Collection<? extends E> c) {//将集合c添加到指定位置
rangeCheckForAdd(index);//检查越界
Object[] a = c.toArray();//toarray产生一个新数组，clone产生一个新对象，所以toArray可视为浅克隆
int numNew = a.length;
ensureCapacityInternal(size + numNew); // Increments modCount
int numMoved = size - index;//确定右移的元素数量
if (numMoved > 0)
System.arraycopy(elementData, index, elementData, index + numNew,
numMoved);//下标从index开始后的元素向右移动numNew位置，腾出空间
System.arraycopy(a, 0, elementData, index, numNew);//将集合中的元素添加到腾出的空位中
size += numNew;
return numNew != 0;
}
/**
* Removes from this list all of the elements whose index is between
* {@code fromIndex}, inclusive, and {@code toIndex}, exclusive.
* Shifts any succeeding elements to the left (reduces their index).
* This call shortens the list by {@code (toIndex - fromIndex)} elements.
* (If {@code toIndex==fromIndex}, this operation has no effect.)
*
* @throws IndexOutOfBoundsException if {@code fromIndex} or
* {@code toIndex} is out of range
* ({@code fromIndex < 0 ||
* fromIndex >= size() ||
* toIndex > size() ||
* toIndex < fromIndex})
*/
protected void removeRange(int fromIndex, int toIndex) {//删除指定范围的元素
modCount++;
int numMoved = size - toIndex;//下标toIndex和其后的元素数量
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);//把下标toIndex和其后的元素直接覆盖到要删除的起点位置
// clear to let GC do its work
int newSize = size - (toIndex-fromIndex);//删除后的元素数量
for (int i = newSize; i < size; i++) {//有可能删除的元素比移动的元素多，导致覆盖后仍有残余
elementData[i] = null;//将移动后的剩余空间置null方便回收
}
size = newSize;
}
/**
* 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));
}
/**
* A version of rangeCheck used by add and addAll.由add和addAll使用的rangeCheck的一个版本。
*/
private void rangeCheckForAdd(int index) {//由add和addAll使用的rangeCheck的一个版本。
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* Constructs an IndexOutOfBoundsException detail message.
* Of the many possible refactorings of the error handling code,
* this "outlining" performs best with both server and client VMs.
*/
private String outOfBoundsMsg(int index) {//构造IndexOutOfBoundsException详细信息。
return "Index: "+index+", Size: "+size;
}
/**
* Removes from this list all of its elements that are contained in the
* specified collection.元素中包含的所有元素从该列表中移除
*指定的集合。
*
* @param c collection containing elements to be removed from this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean removeAll(Collection<?> c) {//删除数组中所包含的c集合中的元素
Objects.requireNonNull(c);//检查c是否为null
return batchRemove(c, false);
}
/**
* Retains only the elements in this list that are contained in the
* specified collection. In other words, removes from this list all
* of its elements that are not contained in the specified collection.
*
* @param c collection containing elements to be retained in this list
* @return {@code true} if this list changed as a result of the call
* @throws ClassCastException if the class of an element of this list
* is incompatible with the specified collection
* (<a href="Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if this list contains a null element and the
* specified collection does not permit null elements
* (<a href="Collection.html#optional-restrictions">optional</a>),
* or if the specified collection is null
* @see Collection#contains(Object)
*/
public boolean retainAll(Collection<?> c) {//保留数组中包含C集合中的元素
Objects.requireNonNull(c);//检查c是否为null
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++)//遍历数组所有元素
if (c.contains(elementData[r]) == complement)//若集合包含数组中的元素为假，即c集合不包含该元素
elementData[w++] = elementData[r];//将该元素放到数组的指定位置
} finally {
// Preserve behavioral compatibility with AbstractCollection,保持与AbstractCollection的行为兼容性，
// even if c.contains() throws.即使c.contains()抛出。
if (r != size) {
System.arraycopy(elementData, r,
elementData, w,
size - r);//若正在操作时出异常，则把未处理的部分移动到已经处理好的部分后面
w += size - r;//给W加上移动的个数
}
if (w != size) {//若w等于size，则说明根本没有进行删除或者保留操作就会返回false
// clear to let GC do its work
for (int i = w; i < size; i++)//若w不等于size个数，则将W后的残余元素剔除
elementData[i] = null;
modCount += size - w;//增加修改次数
size = w;//修改元素个数
modified = true;//返回true则说明成功操作
}
}
return modified;
}//可能大家会发现问题，若是出异常了把未处理的部分移动到处理后的部分后生成新数组仍会返回true，这个在Arraylistjdk11里做出了修改
/**
* Save the state of the <tt>ArrayList</tt> instance to a stream (that
* is, serialize it).//保存数组实例的状态到一个流（即它序列化）。写入过程数组被更改会抛出异常
*
* @serialData The length of the array backing the <tt>ArrayList</tt>
* instance is emitted (int), followed by all of its elements
* (each an <tt>Object</tt>) in the proper order.
*/
//写入流的操作
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]);//写入元素
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Reconstitute the <tt>ArrayList</tt> instance from a stream (that is,
* deserialize it).从一个流(即反序列化)。
*/
//读操作
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
// Read in size, and any hidden stuff
s.defaultReadObject();//执行默认的反序列化/序列化过程。
// Read in capacity
s.readInt(); // ignored
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
int capacity = calculateCapacity(elementData, size);
SharedSecrets.getJavaOISAccess().checkArray(s, Object[].class, capacity);
ensureCapacityInternal(size);
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {//读入元素
a[i] = s.readObject();
}
}
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence), starting at the specified position in the list.
* The specified index indicates the first element that would be
* returned by an initial call to {@link ListIterator#next next}.
* An initial call to {@link ListIterator#previous previous} would
* return the element with the specified index minus one.
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public ListIterator<E> listIterator(int index) {//返回迭代器，起始位置为指定位置
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("Index: "+index);
return new ListItr(index);
}
/**
* Returns a list iterator over the elements in this list (in proper
* sequence).
*
* <p>The returned list iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @see #listIterator(int)
*/
public ListIterator<E> listIterator() {//起始位置为0
return new ListItr(0);
}
/**
* Returns an iterator over the elements in this list in proper sequence.
*
* <p>The returned iterator is <a href="#fail-fast"><i>fail-fast</i></a>.
*
* @return an iterator over the elements in this list in proper sequence
*/
public Iterator<E> iterator() {//返回一个迭代器
return new Itr();
}
/**
* An optimized version of AbstractList.Itr一个优化版的AbstractList.Itr
*/
private class Itr implements Iterator<E> {//实现一个迭代器
int cursor; // index of next element to return下一个要返回的元素的索引
int lastRet = -1; // index of last element returned; -1 if no such（最后一次元素的下标）上一个返回元素的下标
int expectedModCount = modCount;//将修改次数设置给迭代器，在遍历时若该数字改变了则报异常
Itr() {}
public boolean hasNext() {
return cursor != size;//若下一个下标不为元素个数，则返回true
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();//检查是否修改次数发生变化
int i = cursor;//下一个元素的下标
if (i >= size)//若下标大于等于元素个数，则报异常
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)//若下标大于数组的长度，则报异常
throw new ConcurrentModificationException();
cursor = i + 1;//下标+1
return (E) elementData[lastRet = i];//返回数组对应下标的元素
}
public void remove() {//迭代时删除
if (lastRet < 0)//若上一个元素下标-1则说明还没开始或元素为0个
throw new IllegalStateException();
checkForComodification();//检查是否修改
try {
ArrayList.this.remove(lastRet);//移除这个下标的元素
cursor = lastRet;//把这个下标给下一个要返回的元素下标
lastRet = -1;
expectedModCount = modCount;//将修改次数同步
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);//判断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();
}
}
/**
* An optimized version of AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {//实现一个 ListIterator
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {//判断是否有前一个元素
return cursor != 0;//此下标不为0
}
public int nextIndex() {//下一个下标
return cursor;
}
public int previousIndex() {//前一个下标
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {//返回前一个元素
checkForComodification();//检查修改
int i = cursor - 1;//下标为上一个元素下标
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;//修改下标
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {//添加元素
checkForComodification();//检查
try {
int i = cursor;
ArrayList.this.add(i, e);//给下一个元素位置添加元素
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;//从新设置修改标记
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
}
以上便是博主对Arraylist1.8源码的解读sublist部分源码没有写出，其他均为为个人理解可能存在问题，欢迎大家批评指出，共同交流进步。