乐趣区

关于java:java集合2-iterator接口详解

一、iterator接口介绍

iterator接口, 也是汇合小家庭中的一员。和其余的 MapCollection接口不同,iterator 次要是为了不便遍历汇合中的所有元素,用于迭代拜访汇合中的元素,相当于定义了遍历元素的标准,而另外的 MapCollection接口次要是定义了存储元素的标准。
还记得么?之前说的 iterable 接口,有一个办法就是叫 iterator(),也是返回iterator 对象。

迭代:一直拜访汇合中元素的形式,取元素之前先判断是否有元素,有则取出来,没有则完结,一直循环这个过程,直到遍历完外面所有的元素。

接口定义的办法如下:

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 的对象。值得注意的是,iteratorremove() 办法,是迭代过程中 惟一平安 的批改汇合的办法,为何这样说?
如果应用 for 循环索引的形式遍历,删除掉一个元素之后,汇合的元素个数曾经变动,很容易出错。例如

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

iteratorremove()办法则不会出错,因为通过调用 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

从下面图片接口看,这个接口具备拜访下一个元素,判断是否有下一个元素,是否有后面一个元素,判断是否有前一个元素,获取下一个元素的索引,获取上一个元素的索引,移除元素,批改元素,减少元素等性能。和一般的 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

精确地来说,SpitIteratorIterator 并没有什么关系,只是两个性能上有相似。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,SIZEDSUBSIZED, 这个咱们能够通过
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;,不难看出,这些状态是依据与运算来计算出来的。下面的后果也表明ArrayListORDERED,SIZEDSUBSIZED 这几个特色。
如果是 HashSet 则特色是 DISTINCTSIZED

四、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() 异样,这是一种平安爱护机制。
安全检查,疾速失败机制实现次要和变量 modCountexpectedModCount,以及一个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,就是校验这个迭代过程中是否被批改,如果批改了,则会抛出异样。

此文章仅代表本人(本菜鸟)学习积攒记录,或者学习笔记,如有侵权,请分割作者删除。人无完人,文章也一样,文笔稚嫩,在下不才,勿喷,如果有谬误之处,还望指出,感激不尽~

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

公众号:秦怀杂货店

退出移动版