Java集合-Iterator

本章章节目录:

  Iterator的基本用法;

  Iterator的底层分析;

  Iterator与ListIterator区别;

  Iterator迭代获取与for循环获取的效率比较/及使用建议;

 Iterator的基本用法

     在Java中遍历List时会用到Java提供的Iterator,Iterator十分好用,原因是:

     迭代器是一种设计模式,它是一个对象,它可以遍历并选择序列中的对象,而开发人员不需要了解该序列的底层结构。迭代器通常被称为“轻量级”对象,因为创建它的代价小。

     Java中的Iterator功能比较简单,并且只能单向移动:

      (1) 使用方法iterator()要求容器返回一个Iterator。第一次调用Iterator的next()方法时,它返回序列的第一个元素。注意:iterator()方法是java.lang.Iterable接口,被Collection继承。

      (2) 使用next()获得序列中的下一个元素。

      (3) 使用hasNext()检查序列中是否还有元素。

      (4) 使用remove()将迭代器新返回的元素删除。

      只要看看下面这个例子就一清二楚了:

import java.util.*;
public class Muster {
     public static void main(String[] args) {
        ArrayList list = new ArrayList();
        list.add("a");
        list.add("b");
        list.add("c");
        Iterator it = list.iterator();
        while(it.hasNext()){
            String str = (String) it.next();
            System.out.println(str);
        }
    }
}

   运行结果:

a
b
c

     可以看到,Iterator可以不用管底层数据具体是怎样存储的,都能够通过next()遍历整个List。

Iterator的代码分析

     但是,具体是怎么实现的呢?背后机制究竟如何呢?

     这里我们来看看Java里AbstractList实现Iterator的源代码:

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

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

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

        可以看到,实现next()是通过get(cursor),然后cursor=cursor+1,通过这样实现遍历。

       这部分代码不难看懂,唯一难懂的是remove操作里涉及到的expectedModCount = modCount;

     这是集合迭代中的一种“快速失败”机制,这种机制提供迭代过程中集合的安全性。

        从源代码里可以看到增删操作都会使modCount++,通过和expectedModCount的对比,迭代器可以快速的知道迭代过程中是否存在list.add()类似的操作,存在的话快速失败!

      blob.png

 可以查阅之前的文章:http://www.dczou.com/viemall/224.html

Iterator与ListIterator区别:

       我们在使用List,Set的时候,为了实现对其数据的遍历,我们经常使用到了Iterator(跌代器)。使用跌代器,你不需要干涉其遍历的过程,只需要每次取出一个你想要的数据进行处理就可以了。 但是在使用的时候也是有不同的。List和Set都有iterator()来取得其迭代器。对List来说,你也可以通过listIterator()取得其迭代器,两种迭代器在有些时候是不能通用的,Iterator和ListIterator主要区别在以下方面: 

      1. ListIterator有add()方法,可以向List中添加对象,而Iterator不能 
      2. ListIterator和Iterator都有hasNext()和next()方法,可以实现顺序向后遍历,但是ListIterator有hasPrevious()和previous()方法,可以实现逆向(顺序向前)遍历。Iterator就不可以。 
       3. ListIterator可以定位当前的索引位置,nextIndex()和previousIndex()可以实现。Iterator没有此功能。 
       4. 都可实现删除对象,但是ListIterator可以实现对象的修改,set()方法可以实现。Iierator仅能遍历,不能修改。 
         因为ListIterator的这些功能,可以实现对LinkedList等List数据结构的操作。其实,数组对象也可以用迭代器来实现。 
      org.apache.commons.collections.iterators.ArrayIterator就可以实现此功能。一般情况下,我们使用Iterator就可以了,如果你需要进行记录的前后反复检索的话,你就可以使用ListIterator来扩展你的功能,(有点象JDBC中的滚动结果集)。 

 Iterator迭代获取与for循环获取的效率比较/及使用建议:

    在对比之前首先的理解RandomAccess这个接口:

    类Collections的shuffle()方法中的使用:

   blob.png

        这个方法的作用就是将集合对象打乱,洗牌。那为什么JDK这些大牛要区分了该类是否是RandomAccess的实例,这样做有什么意义呢?请继续向下看:

        在jdk文档中对RandomAccess接口的定义如下:

    public interface RandomAccess

     List 实现所使用的标记接口,用来表明其支持快速(通常是固定时间)随机访问。此接口的主要目的是允许一般的算法更改其行为,从而在将其应用到随机或连续访问列表时能提供良好的性能。

    强调:

    JDK中推荐的是对List集合尽量要实现RandomAccess接口

    如果集合类是RandomAccess的实现,则尽量用for(int i = 0; i < size; i++) 来遍历而不要用Iterator迭代器来遍历,在效率上要差一些。反过来,如果List是Sequence List,则最好用迭代器来进行迭代。

    JDK中说的很清楚,在对List特别是Huge size的List的遍历算法中,要尽量来判断是属于RandomAccess(如ArrayList)还是Sequence List (如LinkedList),因为适合RandomAccess List的遍历算法,用在Sequence List上就差别很大,常用的作法就是:
        要作一个判断:

     if (list instance of RandomAccess) {
            for(int m = 0; m < list.size(); m++){}
        }else{
            Iterator iter = list.iterator();
            while(iter.hasNext()){}
        }

    代码测试:

    public class Test {
    
    	// 初始化列表  
    	  
        public static void initList(List list, int n) {  
            for (int i = 0; i < n; i++) {  
                list.add(i);  
            }  
        }  
    
       /*
        * 使用循环进行对列表的迭代  
        */
        public static void traverseWithLoop(List list) {  
            long starttime = 0;  
            long endtime = 0;  
            starttime = System.currentTimeMillis();  
            for (int count = 0; count <= 1000; count++) {  
                for (int i = 0; i < list.size(); i++) {  
                    list.get(i);  
                }  
            }  
            endtime = System.currentTimeMillis();  
            System.out.println("使用loop迭代一共花了" + (endtime - starttime) + "ms时间");  
      
        }  
    
       /*
        * 使用迭代器对列表进行迭代  
        */
        public static void traverseWithIterator(List list) {  
            long starttime = 0;  
            long endtime = 0;  
            starttime = System.currentTimeMillis();  
            for (int count = 0; count <= 1000; count++) {  
                for (Iterator itr = list.iterator(); itr.hasNext();) {  
                    itr.next();  
                }  
            }  
            endtime = System.currentTimeMillis();  
            System.out.println("使用Iterator迭代一共花了" + (endtime - starttime) + "ms时间");  
        }  
      
         /*
          * 
          */
        public static void traverse(List list) {  
      
            long starttime = 0;  
            long endtime = 0;  
            if (list instanceof RandomAccess) {  
                System.out.println("该list实现了RandomAccess接口");  
                starttime = System.currentTimeMillis();  
                for (int count = 0; count <= 1000; count++) {  
                    for (int i = 0; i < list.size(); i++) {  
                        list.get(i);  
                    }  
                }  
                endtime = System.currentTimeMillis();  
                System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");  
            } else {  
                System.out.println("该list未实现RandomAccess接口");  
                starttime = System.currentTimeMillis();  
                for (int count = 0; count <= 1000; count++) {  
                    for (Iterator itr = list.iterator(); itr.hasNext();) {  
                        itr.next();  
                    }  
                }  
                endtime = System.currentTimeMillis();  
                System.out.println("迭代一共花了" + (endtime - starttime) + "ms时间");  
            }  
        }  
      
        public static void main(String[] args) {  
            ArrayList arraylist = new ArrayList();  
            LinkedList linkedlist = new LinkedList();  
            initList(arraylist, 1000);  
            initList(linkedlist, 1000);  
            traverse(arraylist);  
            traverse(linkedlist);  
            traverseWithIterator(arraylist);  
            traverseWithLoop(arraylist);  
            traverseWithIterator(linkedlist);  
            traverseWithLoop(linkedlist);  
        }  
    
    }

  结果输出:

该list实现了RandomAccess接口
迭代一共花了29ms时间
该list未实现RandomAccess接口
迭代一共花了57ms时间
使用Iterator迭代一共花了33ms时间
使用loop迭代一共花了26ms时间
使用Iterator迭代一共花了79ms时间
使用loop迭代一共花了937ms时间

    结论分析:

     根据程序输出的结果的确证明了,arraylist等实现了RandomAccessj接口的类在进行迭代时使用loop效率更高,而linkedList那些未实现该接口的类在进行迭代时使用Iterator进行迭代效率更高.