Java集合【2】——— iterator接口

一、iterator接口介绍

iterator接口,也是集合大家庭中的一员。和其他的Map和Collection接口不同，iterator 主要是为了方便遍历集合中的所有元素，用于迭代访问集合中的元素，相当于定义了遍历元素的规范，而另外的Map和Collection接口主要是定义了存储元素的规范。
还记得么？之前说的iterable接口，有一个方法就是叫iterator()，也是返回iterator对象。

迭代：不断访问集合中元素的方式，取元素之前先判断是否有元素，有则取出来，没有则结束，不断循环这个过程，直到遍历完里面所有的元素。

接口定义的方法如下：

image

boolean hasNext(); // 是否有下一个元素

E next();   // 获取下一个元素

// 移除元素
default void remove() {
        throw new UnsupportedOperationException("remove");
    }
    
// 对剩下的所有元素进行处理，action则为处理的动作，意为要怎么处理
default void forEachRemaining(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        while (hasNext())
            action.accept(next());
    }

但是值得注意的是，集合类的整体不是继承了iterator接口，而是继承了iterable接口，通过iterable接口的方法返回iterator的对象。值得注意的是，iterator的remove()方法，是迭代过程中唯一安全的修改集合的方法，为何这样说？
如果使用for循环索引的方式遍历，删除掉一个元素之后，集合的元素个数已经变化，很容易出错。例如

for(int i=0;i<collection.size();i++){
    if(i==2){
        collection.remove(i);
    }
}

而iterator的remove()方法则不会出错，因为通过调用hasNext()和next()方法，对指针控制已经处理得比较完善。

二、为什么需要iterator接口

首先，我们知道iterator接口是为了定义遍历集合的规范，也是一种抽象，把在不同集合的遍历方式抽象出来，这样遍历的时候，就不需要知道不同集合的内部结构。

为什么需要抽象？

假设没有iterator接口,我们知道，遍历的时候只能通过索引，比如

for(int i=0;i<array.size();i++){
    T item = array[i];
}

这样一来，耦合程度比较高，如果使用的数据结构变了，就要换一种写法，不利于维护已有的代码。如果没有iterator,那么客户端需要维护指针，相当于下放了权限，会造成一定程度的混乱。抽象则是把遍历功能抽取出来，交给iterator处理，客户端处理集合的时候，交给更“专业”的它，it do it well.

三、iterator接口相关接口

3.1 ListIterator

ListIterator继承于Iterator接口，功能更强大，只能用于访问各种List类型，使用List类型的对象list，调用listIterator()方法可以获取到一个指向list开头的ListIterator

image

从上面图片接口看，这个接口具有访问下一个元素，判断是否有下一个元素，是否有前面一个元素，判断是否有前一个元素，获取下一个元素的索引，获取上一个元素的索引，移除元素，修改元素，增加元素等功能。和普通的Iterator不一样的是,ListIterator的访问指针可以向前或者向后移动，也就是双向移动。

boolean hasNext();  //是否还有元素 

E next();   //获取下一个元素

boolean hasPrevious();  //是否有上一个元素

E previous();   // 获取上一个元素

int nextIndex();    //获取下一个索引

int previousIndex();    //获取上一个索引

void remove();  //移除

void set(E e); //更新

void add(E e); //添加元素

测试代码如下：

        List<String> list =
                new ArrayList<String>(Arrays.asList("Book","Pen","Desk"));
        // 把指针指向第一个元素
        ListIterator<String> lit = list.listIterator(1);
        while(lit.hasNext()){
            System.out.println(lit.next());
        }
        System.out.println("===================================");
        //指针指向最后一个元素列表中的最后一个元素修改ChangeDesk。
        lit.set("ChangeDesk");
        // 往前面遍历
        while(lit.hasPrevious()){
            System.out.println(lit.previous());
        }

输出如下：

Pen
Desk
===================================
ChangeDesk
Pen
Book

如果点开ArrayList的源码，看到与ListIterator相关的部分，我们会发现其实ArrayList在底层实现了一个内部类ListItr，继承了Itr,实现了ListIterator接口。这个Itr其实就是实现了Iterator,实现了基本的List迭代器功能，而这个ListItr则是增强版的专门为List实现的迭代器。里面使用cursor作为当前的指针（索引），所有函数功能都是操作这个指针实现。

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();
            }
        }
    }

我们可以看到，在上面方法中，有很多校验，比如checkForComodification()，意为检查是否被修改，list中的元素修改有可能导致数组越界。

3.2 SpitIterator

准确地来说，SpitIterator和Iterator并没有什么关系，只是两个功能上有类似。SpitIterator主要是定义类将集合分割成多个集合，方便并行计算。

3.2.1 SpitIterator源码方法解析

public interface Spliterator<T> {

    // 顺序处理每一个元素，参数是处理的动作，如果还有元素需要处理则返回true，否则返回false
    boolean tryAdvance(Consumer<? super T> action);

    // 依次处理剩下的元素
    default void forEachRemaining(Consumer<? super T> action) {
        do { } while (tryAdvance(action));
    }

    // 最重要的方法，用来分割集合
    Spliterator<T> trySplit();
    
    //估算还有多少元素需要遍历处理
    long estimateSize();

    // 获取准确的元素，如果不能获取准确的，则会返回估算的
    default long getExactSizeIfKnown() {
        return (characteristics() & SIZED) == 0 ? -1L : estimateSize();
    }

    // 表示该Spliterator有哪些特性，这个像是个拓展功能，更好控制和优化Spliterator使用
    int characteristics();
    
    // 判断是否有哪些特性
    default boolean hasCharacteristics(int characteristics) {
        return (characteristics() & characteristics) == characteristics;
    }
    // 如果这个Spliterator的源具有已排序的特征，那么这个方法将返回相应的比较器。如果源按自然顺序排序，则返回     // null。否则，如果源未排序，则抛出IllegalStateException。
    default Comparator<? super T> getComparator() {
        throw new IllegalStateException();
    }

    public static final int ORDERED    = 0x00000010;
    public static final int DISTINCT   = 0x00000001;
    public static final int SORTED     = 0x00000004;
    public static final int SIZED      = 0x00000040;
    public static final int NONNULL    = 0x00000100;
    public static final int IMMUTABLE  = 0x00000400;
    public static final int CONCURRENT = 0x00001000;
    public static final int SUBSIZED = 0x00004000;
}

使用的方法例子如下：

    public static void spliterator(){
        List<String> list = Arrays.asList("1", "2", "3","4","5","6","7","8","9","10");
        // 获取可迭代器
        Spliterator<String> spliterator = list.spliterator();
        // 一个一个遍历
        System.out.println("tryAdvance: ");
        spliterator.tryAdvance(item->System.out.print(item+" "));
        spliterator.tryAdvance(item->System.out.print(item+" "));
        System.out.println("\n-------------------------------------------");

        // 依次遍历剩下的
        System.out.println("forEachRemaining: ");
        spliterator.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");

        // spliterator1:0~10
        Spliterator<String> spliterator1 = list.spliterator();
        // spliterator1:6~10 spliterator2:0~5
        Spliterator<String> spliterator2 = spliterator1.trySplit();
        // spliterator1:8~10 spliterator3:6~7
        Spliterator<String> spliterator3 = spliterator1.trySplit();
        System.out.println("spliterator1: ");
        spliterator1.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");
        System.out.println("spliterator2: ");
        spliterator2.forEachRemaining(item->System.out.print(item+" "));
        System.out.println("\n------------------------------------------");
        System.out.println("spliterator3: ");
        spliterator3.forEachRemaining(item->System.out.print(item+" "));
    }
  • tryAdvance（） 一个一个元素进行遍历
  • forEachRemaining() 顺序地分块遍历
  • trySplit()进行分区形成另外的 Spliterator，使用在并行操作中，分出来的是前面一半，就是不断把前面一部分分出来

结果如下：

tryAdvance: 
1 2 
-------------------------------------------
forEachRemaining: 
3 4 5 6 7 8 9 10 
------------------------------------------
spliterator1: 
8 9 10 
------------------------------------------
spliterator2: 
1 2 3 4 5 
------------------------------------------
spliterator3: 
6 7

还有一些其他的用法在这里就不列举了，主要是trySplit()之后，可以用于多线程遍历。理想的时候，可以平均分成两半，有利于并行计算，但是不是一定平分的。

3.2.2 SpitIterator里面哪些特征常量有什么用呢？

spliterator可以将其实现特征表示为同一接口中定义的一组常量。也就是我们见到的ORDERED,DISTINCT,SORTED,SIZED之类的，这个意思是每一个实现类，都有自己的实现方式，实现方式不同，实现特征也不一样，比如ArrayList实现特征是ORDERED,SIZED和SUBSIZED,这个我们可以通过
characteristics() and hasCharacteristics()来判断。例如：

    public static void main(String[] args) throws Exception{
        List<String> list = new ArrayList<>();
        Spliterator<String> s = list.spliterator();
        System.out.println(s.characteristics());
        if(s.hasCharacteristics(Spliterator.ORDERED)){
            System.out.println("ORDERED");
        }
        if(s.hasCharacteristics(Spliterator.DISTINCT)){
            System.out.println("DISTINCT");
        }
        if(s.hasCharacteristics(Spliterator.SORTED)){
            System.out.println("SORTED");
        }
        if(s.hasCharacteristics(Spliterator.SIZED)){
            System.out.println("SIZED");
        }

        if(s.hasCharacteristics(Spliterator.CONCURRENT)){
            System.out.println("CONCURRENT");
        }
        if(s.hasCharacteristics(Spliterator.IMMUTABLE)){
            System.out.println("IMMUTABLE");
        }
        if(s.hasCharacteristics(Spliterator.NONNULL)){
            System.out.println("NONNULL");
        }
        if(s.hasCharacteristics(Spliterator.SUBSIZED)){
            System.out.println("SUBSIZED");
        }
    }

输出的结果是

16464
ORDERED
SIZED
SUBSIZED

输出结果中的16464和其他的怎么挂钩的呢？其实我们发现上面的hasCharacteristics()方法中，实现是return (characteristics() & characteristics) == characteristics;，不难看出，这些状态是根据与运算来计算出来的。上面的结果也表明ArrayList有ORDERED,SIZED和SUBSIZED这几个特征。
如果是HashSet则特征是DISTINCT和SIZED。

四、 iterator在集合中的实现例子

iterator只是一个接口，相当于一个规范，所有的子类或者继承类实现的时候理论上应该遵守，但是不一样的继承类/子类会有不一样的实现。

4.1 iterator在ArrayList的实现

iterator只是一个接口，一个规范，虽然里面有个别方法有默认实现，但是最重要也最丰富的的，是它在子类中的实现与拓展，现在来看在ArrayList 中的实现。ArrayList并没有直接去实现iterator接口，而是通过内部类的方式来操作，内部类为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;
        }

        // 下一个元素
        @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();
        }
    }

从上面的源码可以看到，很多关于被修改的检查，集合会追踪修改（增删改）的次数（modCount 又称版本号），每一个迭代器会单独立维护一个计数器，在每次操作（增删改），检查版本号是否发生改变，如果改变，就会抛出ConcurrentModificationException() 异常，这是一种安全保护机制。
安全检查，快速失败机制实现主要和变量modCount，expectedModCount，以及一个checkForComodification()方法有关，也就是expectedModCount是内部类的修改次数，从字面意思看是指理论上期待的修改次数，modCount是外部类的修改次数，创建的时候，会将modCount赋值给expectedModCount，两者保持一致，如果在迭代的过程中，外部类的modCount对不上expectedModCount，n那么就会抛出ConcurrentModificationException异常。

4.2 iterator在HashMap的实现

首先，HashMap里面定义了一个HashIterator，为什么这样做呢？因为HashMap存储结构的特殊性，里面有Entry<key,value>，所以遍历就有三种情况，一个是Key，一个是Value，另一个就是Entry,这三个的迭代遍历都有相似性，所以这里根据抽象原则，定义了一个Hash迭代器。

    abstract class HashIterator {
        // 下一个节点
        Node<K,V> next;
        
        // 当前节点
        Node<K,V> current;     // current entry
        // 期望修改次数
        int expectedModCount;  // for fast-fail
        // 索引
        int index;             // current slot

        HashIterator() {
            expectedModCount = modCount;
            Node<K,V>[] t = table;
            current = next = null;
            index = 0;
            if (t != null && size > 0) { 
                // 指向第一个不为空的元素
                do {} while (index < t.length && (next = t[index++]) == null);
            }
        }

        // 是否有下一个节点
        public final boolean hasNext() {
            return next != null;
        }

        // 获取下一个节点
        final Node<K,V> nextNode() {
            Node<K,V>[] t;
            Node<K,V> e = next;
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            if (e == null)
                throw new NoSuchElementException();
            if ((next = (current = e).next) == null && (t = table) != null) {
                do {} while (index < t.length && (next = t[index++]) == null);
            }
            return e;
        }

        // 移除
        public final void remove() {
            Node<K,V> p = current;
            if (p == null)
                throw new IllegalStateException();
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
            current = null;
            K key = p.key;
            removeNode(hash(key), key, null, false, false);
            expectedModCount = modCount;
        }
    }

之后分别定义KeyIterator,ValueIterator,EntryIterator,继承于HashIterator，

    // 遍历key
    final class KeyIterator extends HashIterator
        implements Iterator<K> {
        public final K next() { return nextNode().key; }
    }
    // 遍历value
    final class ValueIterator extends HashIterator
        implements Iterator<V> {
        public final V next() { return nextNode().value; }
    }

    //遍历entry
    final class EntryIterator extends HashIterator
        implements Iterator<Map.Entry<K,V>> {
        public final Map.Entry<K,V> next() { return nextNode(); }
    }

五、总结

以上的种种，关于Iterator，其实就是一个迭代器，可简单地理解为遍历使用，主要功能是指向一个节点，向前或者向后移动，如果数据结构复杂就需要多个迭代器，比如HashMap，可以避免多个迭代器之间相互影响。每一个迭代器都会有
expectedModCount 和modCount，就是校验这个迭代过程中是否被修改，如果修改了，则会抛出异常。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

技术之路不在一时，山高水长，纵使缓慢，驰而不息。

公众号：秦怀杂货店

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 204,590评论 6赞 478
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 86,808评论 2赞 381
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 151,151评论 0赞 337
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 54,779评论 1赞 277
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 63,773评论 5赞 367
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 48,656评论 1赞 281
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 38,022评论 3赞 398
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 36,678评论 0赞 258
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 41,038评论 1赞 299
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,659评论 2赞 321
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,756评论 1赞 330
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 33,411评论 4赞 321
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 39,005评论 3赞 307
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,973评论 0赞 19
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,203评论 1赞 260
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 45,053评论 2赞 350
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 42,495评论 2赞 343