ArrayList类源码全解读
- ArryaList的实现方式是数组
- 数组的默认大小为10
- ArrayList线程不安全
- ArrayList的最大容量是最大整形.
- 可以传入一个比较器来修改list的顺序
ArrayList的重要方法
grow(int minCapacity)
方法来增加list容量
/**
* 增加list的容量,确保它至少可以存放指定的最小数量的元素.
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新的容量=旧的容量*1.5
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);
}
复制代码
add(E e)添加元素
/**
* 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) {
//增加一个元素前,确保list空间足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
复制代码
get(int index)获取元素
/**
* 返回指定下标元素
* @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);
}
复制代码
删除元素remove(int index)
/**
* 删除指定位置的元素.将该位置及后边的元素左移.返回旧的该位置的元素
* @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);//检查index合法性
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//该位置及后面的元素全部往前移
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//list元素个数-1,全部元素左移后,将最后一个元素置为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
复制代码
过滤器过滤元素removeIf(Predicate<? super E> filter)
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
//删除的元素数量
int removeCount = 0;
//BitSet是一个用来表示各个数值是否存在的类.
//它将多个数值放在一个long[]中,long[]中的每一个值只能是0或者1.
//0表示该index的数不存在,1表示该index的数存在.
//例如三个数1,6,7存在long[]中,因为一个long值长度为64bit,因此,只需一个long值即可存
//存起来的结果是: [000...76000010],第1位,6位,7位的值置为1
final BitSet removeSet = new BitSet(size);
//期望修改次数
final int expectedModCount = modCount;
final int size = this.size;
//遍历所有元素
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//如果该元素符合过滤条件
if (filter.test(element)) {
//BitSet中标记
removeSet.set(i);
删除元素数量+1
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
//遍历所有元素
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//i为下一个未删除的元素
i = removeSet.nextClearBit(i);
//将未删除的元素集中挪到数组的前面
elementData[j] = elementData[i];
}
//遍历未被删除的元素后面的所有元素,将所有元素置为null,等待回收
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//设置list中元素数量
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
//返回是否有元素被删除
return anyToRemove;
}
复制代码
源码全解读
package java.util;
import java.util.function.Consumer;
import java.util.function.Predicate;
import java.util.function.UnaryOperator;
/**
*
* @author Josh Bloch
* @author Neal Gafter
* @see Collection
* @see List
* @see LinkedList
* @see Vector
* @since 1.2
*/
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
/**
* DEFAULT_CAPACITY: 默认初始容量
*/
private static final int DEFAULT_CAPACITY = 10;
/**
* 空的共享示例
*/
private static final Object[] EMPTY_ELEMENTDATA = {};
/**
* 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.
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
* 存储ArrayList的元素的数组缓冲区。ArrayList的容量是此数组缓冲区的长度。
*/
transient Object[] elementData; * 非私有化为了简化类的嵌套访问
/**
* ArrayList拥有的元素个数
*
* @serial
*/
private int size;
/**
* 指定初始容量,构造一个空的list
* @param initialCapacity the initial capacity of the list
* @throws IllegalArgumentException if the specified initial capacity
* is negative
*/
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);
}
}
/**
* 构造一个空的list,默认初始容量为10
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
/**
* 使用集合来构造一个list
*
* @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 = c.toArray();
if ((size = elementData.length) != 0) {
// 如果返回的不是Object类型,那么新建一个数组,复制原来的元素并转换为Object类型
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// 空数组
this.elementData = EMPTY_ELEMENTDATA;
}
}
/**
* 将list数组的大小设置到和size一样大,来节省存储空间
*/
public void trimToSize() {
modCount++;
if (size < elementData.length) {
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
/**
* 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.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
// list不等于空,最小扩容就是0,否则最小容量是10
int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
// 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;
// 如果最小容量大于最小扩容,那么确保最小容量可用,将list扩容到最小容量
if (minCapacity > minExpand) {
ensureExplicitCapacity(minCapacity);
}
}
private void ensureCapacityInternal(int minCapacity) {
// 如果list为空,最小容量是10或者最小容量中较大的值
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
// 确保最小容量可用,将list扩容到最小容量
ensureExplicitCapacity(minCapacity);
}
// 保证最小容量: 防止内存溢出
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
/**
* list的最大可分配大小.一些虚拟机需要在数组里保留一些头信息,获取更大的空间可
* 能会导致内存溢出.
*/
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
/**
* 增加list的容量,确保它至少可以存放指定的最小数量的元素.
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新的容量=旧的容量*1.5
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) * 如果最小容量数字已经溢出了,抛异常
throw new OutOfMemoryError();
// 如果最小容量>Integer.MAX_VALUE - 8,那么最小容量
// 设为Integer.MAX_VALUE,否则最小容量设为Integer.MAX_VALUE-8
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
/**
* 查询list中元素个数
*/
public int size() {
return size;
}
/**
* 查询list是否为空
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 查询是否包含指定元素
*/
public boolean contains(Object o) {
return indexOf(o) >= 0;
}
/**
* 遍历list查询指定元素的位置.如果没有返回-1
*/
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;
}
/**
* 查询某个元素最后出现的位置,没有的话返回-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;
}
/**
* 复制一个list,元素本身并不会被复制,相当于浅复制
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.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);
}
}
/**
* 返回一个包含所有元素并且顺序正确的数组.
*/
public Object[] toArray() {
return Arrays.copyOf(elementData, size);
}
/**
* 将list中的全部元素放到数组a中,并覆盖.
* 如果a的空间足够,那么直接覆盖a,多余的空间用null填充,
* 如果a中没有足够的空间,那么新生成一个数组,
* 并将list中的元素全部放进去,而a不变.
* @throws NullPointerException if the specified array is null
*/
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
if (a.length < size)
// Make a new array of a's runtime type, but my contents:
return (T[]) Arrays.copyOf(elementData, size, a.getClass());
System.arraycopy(elementData, 0, a, 0, size);
if (a.length > size)
a[size] = null;
return a;
}
//下标查找
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
/**
* 返回指定下标元素
* @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);
}
/**
* 根据下标来设置元素,返回旧的该位置的元素
* @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;
}
/**
* 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) {
//增加一个元素前,确保list空间足够
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
/**
* 在制定位置增加新的元素,原来该位置的元素以及后边的元素全部往后挪一个位置.
* @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);//检查index是否越界.
//确保空间足够
ensureCapacityInternal(size + 1); // Increments modCount!!
//将该位置及后边的元素右移
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//添加该元素
elementData[index] = element;
//元素个数+1
size++;
}
/**
* 删除指定位置的元素.将该位置及后边的元素左移.返回旧的该位置的元素
* @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);//检查index合法性
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
//该位置及后面的元素全部往前移
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//list元素个数-1,全部元素左移后,将最后一个元素置为null
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
/**
* 如果存在某元素,遍历删除第一个.
* @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) {
//该位置及后面的元素全部往前移,并把最后一个元素置
//为null,list元素个数-1
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
/*
* 删除指定位置的元素,不检查index合法性,不返回被删除的元素的值
*/
private void fastRemove(int index) {
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
}
/**
* 删除所有元素
*/
public void clear() {
modCount++;
// clear to let GC do its work
for (int i = 0; i < size; i++)
//设置元素为空
elementData[i] = null;
//list的元素个数置为0
size = 0;
}
/**
* 将集合c中的全部元素添加到list的尾部.
* @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
*/
public boolean addAll(Collection<? extends E> c) {
//集合转换为数组
Object[] a = c.toArray();
int numNew = a.length;
//如果容量足够,那么扩容
ensureCapacityInternal(size + numNew); // Increments modCount
//复制集合中的元素到list中
System.arraycopy(a, 0, elementData, size, numNew);
size += numNew;
//如果集合长度不为0,则添加成功
return numNew != 0;
}
/**
* 将集合c中的全部元素添加到list的指定位置,原来位置以及后面的元素往后移.
* @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) {
rangeCheckForAdd(index);//检查index合法性
Object[] a = c.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);
//将集合中的全部元素放进去
System.arraycopy(a, 0, elementData, index, numNew);
size += numNew;
return numNew != 0;
}
/**
* 将list中下标从fromIndex到toIndex的元素删除
* @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开始的全部元素往前移至fromIndex的位置.
System.arraycopy(elementData, toIndex, elementData, fromIndex,
numMoved);
// clear to let GC do its work
//新的list元素个数
int newSize = size - (toIndex-fromIndex);
for (int i = newSize; i < size; i++) {
//将超出下标范围的元素的值设为null
elementData[i] = null;
}
size = newSize;
}
/**
* 检查index合法性,越界抛出异常.这个方法并不检查index是否为负数.
* 当index为负数时,数组本身也会抛出越界的错误,所以这个方法没必要
* 检查index是否为负数.
*/
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* add和addAll方法检查index是否合法
*/
private void rangeCheckForAdd(int index) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
/**
* 构造下标越界的错误提醒
*/
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+size;
}
/**
* 从list中删除与集合c重复的元素
*
* @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) {
Objects.requireNonNull(c);
//批量删除
return batchRemove(c, false);
}
/**
* list中只保留与集合c相同的元素
*
* @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) {
Objects.requireNonNull(c);
return batchRemove(c, true);
}
/**
* list批量删除/保留与集合c相同的元素.complement: 删除为false,保留为true
*/
private boolean batchRemove(Collection<?> c, boolean complement) {
final Object[] elementData = this.elementData;
//r: 遍历元素最后一个元素的下标,w: 剩下元素最后一个元素的下标
int r = 0, w = 0;
//是否删除元素
boolean modified = false;
try {
for (; r < size; r++)
if (c.contains(elementData[r]) == complement)
//把要保留的元素按照顺序还放到list里,将原来的元素覆盖.
elementData[w++] = elementData[r];
} finally {
//原方法有可能会报错,这样r就没走到r.size
if (r != size) {
//将r到size-1的元素移到保留的元素的后面
System.arraycopy(elementData, r,
elementData, w,
size - r);
//w的下标增加r到size-1个元素
w += size - r;
}
if (w != size) {
// clear to let GC do its work
//将保留的元素的后面的元素的值置为null
for (int i = w; i < size; i++)
elementData[i] = null;
//修改的次数就是删除的元素个数
modCount += size - w;
size = w;
//w和size不相等,说明有元素被删除
modified = true;
}
}
return modified;
}
/**
* 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
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() {
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();
}
/**
* 内部类,优化版本的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
//期待的版本号: 如果跟list中的保持一致,说明中间没有被修改.
int expectedModCount = modCount;
//如果游标不等于index,那么有下一个元素
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
//检查有没有其他线程修改list内容
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;
//返回下一个元素.修改最后返回元素的下标
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
//删除当前元素
ArrayList.this.remove(lastRet);
//删除元素后游标指向上一个元素
cursor = lastRet;
//最后修改元素设为初始值
lastRet = -1;
//将期望版本号改为同list的版本号保持一致
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
//消费剩下的元素
public void forEachRemaining(Consumer<? super E> 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();
}
//遍历消费从i开始的元素
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();
}
}
/**
* 优化版本的AbstractList.ListItr
*/
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 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();
}
}
}
/**
* 返回一个list,从原list的fromIndex(包含),到原list的toIndex(不包含).
* 对新的list的修改会反映在原list上.
*
* @throws IndexOutOfBoundsException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
*/
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);
}
//参数检查
static void subListRangeCheck(int fromIndex, int toIndex, int size) {
if (fromIndex < 0)
throw new IndexOutOfBoundsException("fromIndex = " + fromIndex);
if (toIndex > size)
throw new IndexOutOfBoundsException("toIndex = " + toIndex);
if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex + ")");
}
private class SubList extends AbstractList<E> implements RandomAccess {
private final AbstractList<E> parent;
private final int parentOffset;
private final int offset;
int size;
SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
//原list
this.parent = parent;
//子list与原list的偏移量就是fromIndex
this.parentOffset = fromIndex;
//子list的偏移量(即子list的游标)是原list的偏移量+fromIndex
this.offset = offset + fromIndex;
//子list的长度是toIndex - fromIndex
this.size = toIndex - fromIndex;
//子list版本号与原list版本号一直
this.modCount = ArrayList.this.modCount;
}
public E set(int index, E e) {
//检查index合法性
rangeCheck(index);
//检查版本号是否一致,看看操作期间是否被修改
checkForComodification();
E oldValue = ArrayList.this.elementData(offset + index);
//设置值
ArrayList.this.elementData[offset + index] = e;
return oldValue;
}
//取值
public E get(int index) {
rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);
}
//长度
public int size() {
checkForComodification();
return this.size;
}
//调用原list方法添加元素
public void add(int index, E e) {
rangeCheckForAdd(index);
checkForComodification();
parent.add(parentOffset + index, e);
this.modCount = parent.modCount;
this.size++;
}
public E remove(int index) {
rangeCheck(index);
checkForComodification();
E result = parent.remove(parentOffset + index);
this.modCount = parent.modCount;
this.size--;
return result;
}
protected void removeRange(int fromIndex, int toIndex) {
checkForComodification();
parent.removeRange(parentOffset + fromIndex,
parentOffset + toIndex);
this.modCount = parent.modCount;
this.size -= toIndex - fromIndex;
}
public boolean addAll(Collection<? extends E> c) {
return addAll(this.size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
rangeCheckForAdd(index);
int cSize = c.size();
if (cSize==0)
return false;
checkForComodification();
parent.addAll(parentOffset + index, c);
this.modCount = parent.modCount;
this.size += cSize;
return true;
}
public Iterator<E> iterator() {
return listIterator();
}
public ListIterator<E> listIterator(final int index) {
checkForComodification();
rangeCheckForAdd(index);
final int offset = this.offset;
return new ListIterator<E>() {
int cursor = index;
int lastRet = -1;
int expectedModCount = ArrayList.this.modCount;
public boolean hasNext() {
return cursor != SubList.this.size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= SubList.this.size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[offset + (lastRet = i)];
}
public boolean hasPrevious() {
return cursor != 0;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[offset + (lastRet = i)];
}
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = SubList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (offset + i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[offset + (i++)]);
}
* update once at end of iteration to reduce heap write traffic
lastRet = cursor = i;
checkForComodification();
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
SubList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(offset + lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
SubList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = ArrayList.this.modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
final void checkForComodification() {
if (expectedModCount != ArrayList.this.modCount)
throw new ConcurrentModificationException();
}
};
}
public List<E> subList(int fromIndex, int toIndex) {
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, offset, fromIndex, toIndex);
}
private void rangeCheck(int index) {
if (index < 0 || index >= this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > this.size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private String outOfBoundsMsg(int index) {
return "Index: "+index+", Size: "+this.size;
}
private void checkForComodification() {
if (ArrayList.this.modCount != this.modCount)
throw new ConcurrentModificationException();
}
public Spliterator<E> spliterator() {
checkForComodification();
return new ArrayListSpliterator<E>(ArrayList.this, offset,
offset + this.size, this.modCount);
}
}
@Override
public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;
@SuppressWarnings("unchecked")
final E[] elementData = (E[]) this.elementData;
final int size = this.size;
//遍历消费元素
for (int i=0; modCount == expectedModCount && i < size; i++) {
action.accept(elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
/**
* Creates a <em><a href="Spliterator.html#binding">late-binding</a></em>
* and <em>fail-fast</em> {@link Spliterator} over the elements in this
* list.
*
* <p>The {@code Spliterator} reports {@link Spliterator#SIZED},
* {@link Spliterator#SUBSIZED}, and {@link Spliterator#ORDERED}.
* Overriding implementations should document the reporting of additional
* characteristic values.
*
* @return a {@code Spliterator} over the elements in this list
* @since 1.8
*/
@Override
public Spliterator<E> spliterator() {
return new ArrayListSpliterator<>(this, 0, -1, 0);
}
/** Index-based split-by-two, lazily initialized Spliterator */
static final class ArrayListSpliterator<E> implements Spliterator<E> {
/*
* If ArrayLists were immutable, or structurally immutable (no
* adds, removes, etc), we could implement their spliterators
* with Arrays.spliterator. Instead we detect as much
* interference during traversal as practical without
* sacrificing much performance. We rely primarily on
* modCounts. These are not guaranteed to detect concurrency
* violations, and are sometimes overly conservative about
* within-thread interference, but detect enough problems to
* be worthwhile in practice. To carry this out, we (1) lazily
* initialize fence and expectedModCount until the latest
* point that we need to commit to the state we are checking
* against; thus improving precision. (This doesn't apply to
* SubLists, that create spliterators with current non-lazy
* values). (2) We perform only a single
* ConcurrentModificationException check at the end of forEach
* (the most performance-sensitive method). When using forEach
* (as opposed to iterators), we can normally only detect
* interference after actions, not before. Further
* CME-triggering checks apply to all other possible
* violations of assumptions for example null or too-small
* elementData array given its size(), that could only have
* occurred due to interference. This allows the inner loop
* of forEach to run without any further checks, and
* simplifies lambda-resolution. While this does entail a
* number of checks, note that in the common case of
* list.stream().forEach(a), no checks or other computation
* occur anywhere other than inside forEach itself. The other
* less-often-used methods cannot take advantage of most of
* these streamlinings.
*/
private final ArrayList<E> list;
//下标: 默认为0
private int index; // current index, modified on advance/split
//分割次数,默认-1
private int fence; // -1 until used; then one past last index
//期望版本号: 默认0
private int expectedModCount; // initialized when fence set
/** Create new spliterator covering the given range */
ArrayListSpliterator(ArrayList<E> list, int origin, int fence,
int expectedModCount) {
this.list = list; * OK if null unless traversed
this.index = origin;
this.fence = fence;
this.expectedModCount = expectedModCount;
}
//当fence为获取分割次数
private int getFence() { // initialize fence to size on first use
//每一个分割里的终止位置的下标
int hi; // (a specialized variant appears in method forEach)
ArrayList<E> lst;
//此处会给hi赋值为fence.
if ((hi = fence) < 0) {
if ((lst = list) == null)
hi = fence = 0;
else {
expectedModCount = lst.modCount;
//分割次数是元素的个数
hi = fence = lst.size;
}
}
return hi;
}
public ArrayListSpliterator<E> trySplit() {
//获取分割次数,lo为起始下标,mid为起始下标+终止下标/2
int hi = getFence(), lo = index, mid = (lo + hi) >>> 1;
return (lo >= mid) ? null : // divide range in half unless too small
new ArrayListSpliterator<E>(list, lo, index = mid,
expectedModCount);
}
public boolean tryAdvance(Consumer<? super E> action) {
if (action == null)
throw new NullPointerException();
int hi = getFence(), i = index;
if (i < hi) {
index = i + 1;
@SuppressWarnings("unchecked") E e = (E)list.elementData[i];
action.accept(e);
if (list.modCount != expectedModCount)
throw new ConcurrentModificationException();
return true;
}
return false;
}
public void forEachRemaining(Consumer<? super E> action) {
int i, hi, mc; * hoist accesses and checks from loop
ArrayList<E> lst; Object[] a;
if (action == null)
throw new NullPointerException();
if ((lst = list) != null && (a = lst.elementData) != null) {
if ((hi = fence) < 0) {
mc = lst.modCount;
hi = lst.size;
}
else
mc = expectedModCount;
if ((i = index) >= 0 && (index = hi) <= a.length) {
for (; i < hi; ++i) {
@SuppressWarnings("unchecked") E e = (E) a[i];
action.accept(e);
}
if (lst.modCount == mc)
return;
}
}
throw new ConcurrentModificationException();
}
public long estimateSize() {
return (long) (getFence() - index);
}
public int characteristics() {
return Spliterator.ORDERED | Spliterator.SIZED | Spliterator.SUBSIZED;
}
}
@Override
public boolean removeIf(Predicate<? super E> filter) {
Objects.requireNonNull(filter);
// figure out which elements are to be removed
// any exception thrown from the filter predicate at this stage
// will leave the collection unmodified
//删除的元素数量
int removeCount = 0;
//BitSet是一个用来表示各个数值是否存在的类.
//它将多个数值放在一个long[]中,long[]中的每一个值只能是0或者1.
//0表示该index的数不存在,1表示该index的数存在.
//例如三个数1,6,7存在long[]中,因为一个long值长度为64bit,因此,只需一个long值即可存
//存起来的结果是: [000...76000010],第1位,6位,7位的值置为1
final BitSet removeSet = new BitSet(size);
//期望修改次数
final int expectedModCount = modCount;
final int size = this.size;
//遍历所有元素
for (int i=0; modCount == expectedModCount && i < size; i++) {
@SuppressWarnings("unchecked")
final E element = (E) elementData[i];
//如果该元素符合过滤条件
if (filter.test(element)) {
//BitSet中标记
removeSet.set(i);
删除元素数量+1
removeCount++;
}
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
// shift surviving elements left over the spaces left by removed elements
final boolean anyToRemove = removeCount > 0;
if (anyToRemove) {
final int newSize = size - removeCount;
//遍历所有元素
for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
//i为下一个未删除的元素
i = removeSet.nextClearBit(i);
//将未删除的元素集中挪到数组的前面
elementData[j] = elementData[i];
}
//遍历未被删除的元素后面的所有元素,将所有元素置为null,等待回收
for (int k=newSize; k < size; k++) {
elementData[k] = null; // Let gc do its work
}
//设置list中元素数量
this.size = newSize;
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
//返回是否有元素被删除
return anyToRemove;
}
@Override
@SuppressWarnings("unchecked")
public void replaceAll(UnaryOperator<E> operator) {
Objects.requireNonNull(operator);
final int expectedModCount = modCount;
final int size = this.size;
for (int i=0; modCount == expectedModCount && i < size; i++) {
elementData[i] = operator.apply((E) elementData[i]);
}
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
@Override
@SuppressWarnings("unchecked")
public void sort(Comparator<? super E> c) {
final int expectedModCount = modCount;
//调用Arrays.sort方法来对list进行排序
Arrays.sort((E[]) elementData, 0, size, c);
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
modCount++;
}
}
复制代码
正文到此结束
- 本文标签： 游标 空间 list 删除 LinkedList https 代码 value http id rand struct IDE DOM dist Collection tag tab UI Document example IO stream 源码 安全 遍历 consumer ORM lambda update cat HTML final Action zab java 线程 App 参数 trigger equals rmi tar CTO REST ACE ArrayList
- 版权声明： 本文为互联网转载文章，出处已在文章中说明(部分除外)。如果侵权，请联系本站长删除，谢谢。
- 本文海报： 生成海报一 生成海报二
热门推荐
相关文章
近期评论
-
文章和留言都翻到11页了 没有OOM
-
-
朋友，翻页到11页，及以后，会出现OOM，无法访问
-
-
搞个gitee的项目
-
-
版本号是多少，你可以下载哪个代码仓库，jdk选1.8 直接跑就行
-
-
-
Loading...
![[HBLOG]公众号](https://www.liuhaihua.cn/img/qrcode_gzh.jpg)
