当前位置:

首页 > 编程开发 > Java教程 >

JDK源码之ArrayList-Iterator

之前写过一篇ArrayList源码的博客 https://www.cnblogs.com/zumengjie/p/13538394.html 其中遗留了一个问题,ArrayList添加元素和删除元素或者清空元素时都会有一个操作 modCount++;当时并没有将死磕到底的精神进行到底。这两天在一本源码书籍里边提到了这个变量,看完后决定记录下来。这本书我也介绍大家去读《Java修炼指南-高频源码解析》是开课吧组编的书,这本书四个字形容,开卷有益。

下文带//为个人注释。源代码使用这个颜色

迭代集合引发的问题

Itr迭代器

ListItr迭代器继承自Itr

ListItr的特色功能

Fail-Fast机制

一些有趣的方法

forEach
trimToSize
subList
为什么说增强for就是迭代器？
Arrays.asList

迭代集合引发的问题

首先先看一段代码。这段代码就是在for循环中使用集合本身的remove方法删除元素。结果大家也都知道因为删除了元素,size减去1,变量i又自增1。最终导致被元素后边的一个没有被遍历到。B被删除了,C顶替了B它的index是2但是变量i已经是3了所以跳过。

	 View Code

接着再看这一段代码。看这段代码主要就是要知道在迭代器中使用集合本身的删除,新增都会报错。ConcurrentModificationException。

	 View Code

但是可以使用迭代器自己的新增或者删除元素的方法。

	 View Code

Itr迭代器

//它返回的是一个Iterator对象是ArrayList中的一个内部类,Iterator<E> iterator()其实是List接口的一个抽象方法。

public Iterator<E> iterator() {
return new Itr();
}

int cursor;//指向下一个元素的下标，默认是0。
int lastRet = -1;//上一个被迭代的下标。
int expectedModCount = modCount;//这个变量在集合长度变化时会自增1

public boolean hasNext() {
return cursor != size;//判断有没有下一个元素的依据是cursor的size!=size,cursor默认是0。如果size是3,cursor也是3那就没有下一个元素了。
}

//在迭代器里抛出的异常就是它做的,当迭代器创建后expectedModCount==modCount,但如果我们使用集合本身的方法改变了集合的长度modCount就会增加而expectedModCount不会增加。

final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}

@SuppressWarnings("unchecked")
public E next() {//获取集合内的下一个元素

checkForComodification();//进来后就走了判断,如果通过迭代器以外的方法修改了集合的长度,那这个方法就直接异常了。
int i = cursor;//默认是0
if (i >= size)//这里也是健壮性的判断,和hasNext()起到同样的效果。
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//拿到ArrayList中的数组。
if (i >= elementData.length)//健壮性的判断
throw new ConcurrentModificationException();
cursor = i + 1;//cursor+1,这表示下一个被读取的元素的下标。
return (E) elementData[lastRet = i];//获取当前元素,并且把下标赋值给lastRet,也就是说这个变量的意思是上一个被迭代的下标。
}

public void remove() {//删除当前被迭代的元素
if (lastRet < 0)
throw new IllegalStateException();//lastRet默认是-1,也就是说如果没有调用next()就调用remove()是会报错的。
checkForComodification();//检验modCount

try {
ArrayList.this.remove(lastRet);//此处调用了ArrayList自身的remove(index)
cursor = lastRet;//这里有点意思。假如调用next()获取的元素是第四个,其实cursor是5而lastRet是4,这里把lastRet赋值给cursor意味着下次next()返回的结果还是第四个。
lastRet = -1;//这里将lastRet置为-1表示如果连续调用两个remove()也会报错。
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

//这个方法其实就是用来遍历集合的,不要试图使用这个方法时改变集合长度,否则极大的几率会出现异常。

//另外这个方法中使用的cursor,lastRet和迭代器中其他方法是共用的。

@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);//断言判断
final int size = ArrayList.this.size;//当前集合的长度
int i = cursor;//cursor默认是0
if (i >= size) {//健壮性判断
return;
}
final Object[] elementData = ArrayList.this.elementData;//拿到数组
if (i >= elementData.length) {//健壮判断
throw new ConcurrentModificationException();
}

//这里就是遍历集合元素,把当前元素交给参数consumer消费。

//如果你在消费时使用集合本身的增加或者删除方法,其效果和普通for循环一样。

//如果你在消费时使用迭代器的remove(i)则会直接报错,因为lastRet默认是-1。
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}

//这里修改cursor意味着再次调用next将会返回false。
cursor = i;

lastRet = i - 1;

//这里会再次检验modCount
checkForComodification();
}

ListItr迭代器继承自Itr

public ListIterator<E> listIterator() {
return new ListItr(0);//它创建的是带参数的 Listltr(0)
}

ListItr(int index) {
super();

//传入的index赋值给了cursor,这意味着我们可以手动的指定下一次迭代的位置。

//但是需要注意cursor更改后,lastRet没有跟着更改，意味着创建listIterator调用迭代器的remove()同样会异常。
cursor = index;
}

//获取迭代器下一次迭代的下标。

public int nextIndex() {
return cursor;
}

//在Itr类中是没有add()方法的。

public void add(E e) {
checkForComodification();//进来后首先做的就是检验modCount的值。

try {
int i = cursor;//当前下标赋值变量

//调用ArrayList自己的添加元素方法。将元素添加到当前i的位置。

//如果当前next元素是1,那么next后就是2也就是在当前迭代元素后添加元素。
ArrayList.this.add(i, e);

//迭代下标+1,这个操作意味着,新添加的元素不会被迭代到。

//例如当前集合为[A,B,C,D,E]当前next指向的是B,则next后cursor就是2

//在2位置添加元素后就是[A,B,N,C,D,E]，那其实下一个next就是N但是cursor+1后下一个就是C了。
cursor = i + 1;
lastRet = -1;//添加后同样会lastRet同样是-1意味着同时调用两次add(e)也会报错。
expectedModCount = modCount;//将modCount赋值给expectedModCount。
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

//这个set方法，倒是有些多余了,因为ArrayList集合本身的set方法不会更改modCount

//因为ListItr的set方法还会检验modCount的值。

public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();//检验modCount

try {
ArrayList.this.set(lastRet, e);//ArrayList自身的set()方法。
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}

ListItr的特色功能

//判断有没有上一个,默认的cursor是0,使用了next()后cursor+1。意味着有上一个元素。

public boolean hasPrevious() {
return cursor != 0;
}

//如果有上一个则调用previous获取上一个元素。

@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();//先检验modCount
int i = cursor - 1;//当前cursor左移
if (i < 0)//如果当前迭代器的cursor已经在最左边了,就要报错。
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;//拿到集合中的数组
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];//这里取得是cursor-1
}

//或者可以使用previousIndex向左移动cursor,但是总感觉这个方法使用不当会很危险。

public int previousIndex() {
return cursor - 1;
}

Fail-Fast机制

以上内容解释了modCount这个变量到底是干啥用的。但是都没有用很专业很有B格的名词唠一下。

Fail-Fast是Java中一种错误检测机制！它的触发机制是，在迭代过程中如果集合的结构发生了

变化此时迭代器并不知情或没有来得及反应就会产生Fail-Fast事件。抛出ConcurrentModificationException异常。

所以modCount和迭代器中的expectedModCount不相等就会报错这就是Fail-Fast机制。

一些有趣的方法

forEach

//这个方法是JDK8出的，为了结合拉姆达表达式使用。　

//它接收一个Consumer消费者接口，这个接口只有一个accept方法。

public void forEach(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int expectedModCount = modCount;//获取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]);//将数组的每个元素交给Consumer的accept方法并且执行。
}
if (modCount != expectedModCount) {//此处也会判断如果modCount出现改变会报错。
throw new ConcurrentModificationException();
}
}

trimToSize

//这个方法用来收缩数组，当已经确认了集合内不会添加元素时，调用此方法将集合内

//的数组进行收缩，也就是说将数组内的元素拷贝到新的数组中，新的数组大小和size相同

public void trimToSize() {

//这个变量现在已经很熟悉了吧。
modCount++;
if (size < elementData.length) {

//如果size是0就把空数组赋值给elementData,如果不是就做数组拷贝。
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}

subList

看下图的执行结果截取后的小集合元素为BC,小集合添加一个元素后卫BCF。令人迷惑的是大集合的元素ABCFDE。

首先subList(int,int)是对集合做截取返回的一个List但是注意,返回的集合并不是ArrayList而是SubList。

public List<E> subList(int fromIndex, int toIndex) {

//这个方法是对入参进行限定起始位置不能小于0,结束位置不能大于大集合的size,其实位置不能大于结束位置。否则都会抛出异常。
subListRangeCheck(fromIndex, toIndex, size);
return new SubList(this, 0, fromIndex, toIndex);

}

//这是ArrayList中的一个内部类。它继承自AbstractList也就是说它和ArrayList是兄弟关系。
private class SubList extends AbstractList<E> implements RandomAccess {

private final AbstractList<E> parent;

//这个变量和offset是一致的,要截取数组的起始位置是N那么小集合和大集合的偏移量就是N

//也就是说要获取小集合的M下标就是要到大集合中找N+M位置的元素
private final int parentOffset;
private final int offset;
int size;

//以上图为例构造函数参数分别是当前ArrayList,0,1,3

SubList(AbstractList<E> parent,
int offset, int fromIndex, int toIndex) {
this.parent = parent;
this.parentOffset = fromIndex;//这个值是1
this.offset = offset + fromIndex;//这个值是0+1
this.size = toIndex - fromIndex;//这个值是2
this.modCount = ArrayList.this.modCount;//ArrayList里的集合操作数变量。到处都有它。