Iterator在ArrayList中的源码实现

小小明童鞋

发布于 2018-06-13 16:07:52

1K0

发布于 2018-06-13 16:07:52

获取迭代器

List<LinkedHashMap> list = new ArrayList<>();
        Iterator iterator = list.iterator();

iterator()方法实现

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

Itr 源码

/**
 * An optimized version of 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;

    public boolean hasNext() {
        return cursor != size;
    }

    @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;
        return (E) elementData[lastRet = i];
    }

    public void remove() {
        if (lastRet < 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);
        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();
    }
}

Itr 为ArrayList的一个内部类，结构：

首先看变量

int cursor;       // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;

**cursor 返回下个元素的下标索引，初始化为0

lastRet 上一个元素的下标索引，初始化为-1，因为当前元素下标为0时没有上一个元素

modCount 声明的变量如下，用于记录数组集合是否被修改过**

protected transient int modCount = 0;

使用到的方法如下：

trimToSize()
ensureExplicitCapacity()
add()
remove()
fastRemove()
clear()
addAll()
removeRange()
batchRemove()
sort()

再看一下， expectedModCount 除了初始化的时候被赋值了意外，只有在迭代过程中将modCount重新赋值给它，其它任何时候它都不会变化。因此，当我们用迭代器进行迭代的时候，单线程条件下，理论上expectedModCount = modCount 是恒成立的。但在多线程环境下，就会出现二者不像等的情况。

hasNext()

public boolean hasNext() {
    return cursor != size;
}

**意思就是数组下表索引没有越界之前都是有元素的 **

next()

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;
    return (E) elementData[lastRet = i];
}

**获取当前索引下标元素，指针（cursor)后移，不多说。 **

remove源码

 public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            checkForComodification();

            try {
                ArrayList.this.remove(lastRet);
                cursor = lastRet;
                lastRet = -1;
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }


### 校验数组是否修改过（在迭代遍历过程中经常会抛出的异常）

这里输入代码

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

校验数组是否越界

private void rangeCheck(int index) {
    if (index >= size)
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

数组复制：

public static native void arraycopy(Object src,  int  srcPos,
                                    Object dest, int destPos,
                                    int length);

arraycopy 的源码在这

System.arraycopy 源码

我翻看了下注释说明：敲重点：

If the <code>src</code> and <code>dest</code> arguments refer to the
same array object, then the copying is performed as if the
components at positions <code>srcPos</code> through
<code>srcPos+length-1</code> were first copied to a temporary
array with <code>length</code> components and then the contents of
the temporary array were copied into positions
<code>destPos</code> through <code>destPos+length-1</code> of the
destination array.

就是说，原数组与将要复制的数组为同一个的时候，就是元素之间的移动。其它的实现暂时不解释。于是，我们可以理解为：删除指定数组下标index位置的元素，然后从数组下表index+1的位置开始向前移动size-index-1 个元素，学过数据结构的童鞋这里就很好理解啦，不多做解释。这里的size 指的是数组的容量（如果元素不为空觉得能得到元素的个数效率更高一点）

_总结

** 1.迭代器在ArrayList中的实现，起始是对对象数组的一系列操作。**

** 2.在List集合中可以使用迭代器的原因是ArrayList 中的内部类 Itr 实现了 Iterator接口 ** ** 3. 在对数组元素进行删除或者更新添加元素等操作时，单线程下最好用迭代器，用传统的for循环或者foreach循环都将导致异常。解决遍历过程中对集合进行修改的问题请参考 CopyOnWriteArrayList_**

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

java

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

java

登录后参与评论

0 条评论

热度