写点什么

奇葩 java 迭代器笔试题,做对算你厉害

用户头像
田维常
关注
发布于: 2021 年 01 月 30 日

有位小朋友最近正在为年后换工作做准备,但是遇到一个问题,觉得很不可思议的一道笔试题。然后我把这道题发到技术群里,发现很多人居然不知道,很多都是连蒙带猜的说。感觉很有必要写一篇文章来说道说道。


奇怪的笔试题


阅读下面这段代码,请写出这段代码的输出内容:


import java.util.ArrayList;import java.util.Iterator;import java.util.*;public class Test {    public static void main(String[] args) {        List<String> list = new ArrayList<>();        list.add("1");        list.add("2");        list.add("3");        Iterator iterator = list.iterator();        while (iterator.hasNext()) {            String str = (String) iterator.next();            if (str.equals("2")) {                iterator.remove();            }        }        while (iterator.hasNext()) {            System.out.println(iterator.next());        }        System.out.println("4");    }}
复制代码


他写出来的答案是:


134
复制代码


奇怪的是,你把这道题目发给你身边人,让他们回答这道面试题输出结果是什么,说这个结果的人非常多。不行你试试



~


答案明显不对,因为在第一个 while 里的 iterator.hasNext()==false 后才会到第二个 while 里来,同一个 Iterator 对象,前面调一次 iterator.hasNext()==false,再判断一次结果不还是一样吗?,


所以第二个 while 判断为 false,也就不会再去遍历 iterator 了,由此可知本体答案是:4。


下面我们来分析一下为什么是具体底层是怎么实现的。


这里的 Iterator 是什么?


  • 迭代器是一种模式、详细可见其设计模式,可以使得序列类型的数据结构的遍历行为与被遍历的对象分离,即我们无需关心该序列的底层结构是什么样子的。只要拿到这个对象,使用迭代器就可以遍历这个对象的内部

  • Iterable 实现这个接口的集合对象支持迭代,是可以迭代的。实现了这个可以配合 foreach 使用~

  • Iterator 迭代器,提供迭代机制的对象,具体如何迭代是这个 Iterator 接口规范的。


Iterator 说明


public interface Iterator<E> {     //每次next之前,先调用此方法探测是否迭代到终点    boolean hasNext();    //返回当前迭代元素 ,同时,迭代游标后移    E next();     /*删除最近一次已近迭代出出去的那个元素。     只有当next执行完后,才能调用remove函数。     比如你要删除第一个元素,不能直接调用 remove()   而要先next一下( );     在没有先调用next 就调用remove方法是会抛出异常的。     这个和MySQL中的ResultSet很类似    */    default void remove() {        throw new UnsupportedOperationException("remove");    }     default void forEachRemaining(Consumer<? super E> action) {        Objects.requireNonNull(action);        while (hasNext())            action.accept(next());    }}
复制代码


这里的实现类是 ArrayList 的内部类 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        //modCountshi ArrayList中的属性,当添加或删除的时候moCount值会增加或者减少        //这里主要是给fail-fast使用,避免一遍在遍历,一遍正在修改导致数据出错        //此列表在结构上被修改的次数。结构修改是指改变结构尺寸的修改列表,        //或者以这样的方式对其进行扰动,进步可能会产生错误的结果。        int expectedModCount = modCount;        public boolean hasNext() {            //cursor初始值为0,没掉一次next方法就+1            //size是ArrayList的大小            return cursor != size;        }        @SuppressWarnings("unchecked")        public E next() {            checkForComodification();            int i = cursor;            if (i >= size)                throw new NoSuchElementException();            //把ArrayList中的数组赋给elementData            Object[] elementData = ArrayList.this.elementData;            if (i >= elementData.length)                throw new ConcurrentModificationException();            //每调用一次next方法,游标就加1            //cursor=lastRet+1            cursor = i + 1;            //返回ArrayList中的元素            return (E) elementData[lastRet = i];        }        public void remove() {            if (lastRet < 0)                throw new IllegalStateException();            checkForComodification();            try {                //调用ArrayList中remove方法,溢出该元素                ArrayList.this.remove(lastRet);                //cursor=lastRet+1,                //所以此时相当于cursor=cursor-1                cursor = lastRet;                lastRet = -1;                expectedModCount = modCount;            } catch (IndexOutOfBoundsException ex) {                throw new ConcurrentModificationException();            }        }        final void checkForComodification() {            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }}
复制代码


再回到上面题目中:


第一个 iterator.hasNext()


第 1 次循环


  • hasNext 方法中:cursor==0, size==3,所以 cursor != size 返回 true。

  • next 方法中:cursor=0+1。返回"1"。


第 2 次循环


  • hasNext 方法中:cursor==1, size==3,所以 cursor != size 返回 true。

  • next 方法中:cursor=1+1。返回"2"。

  • remove 方法中:cursor==cursor-1==2-1=1,把 ArrayList 中的"2"给删除了,所以 size==2。


第 3 次循环


  • hasNext 方法中:cursor==1, size==2,那么 cursor != size 返回 true。

  • next 方法中:cursor=1+1==2;返回"3"。


第 4 次循环


  • hasNext 方法中:cursor==2, size==2,那么 cursor != size 返回 false。


第二个 iterator.hasNext()


hasNext 方法中:cursor==2, size==2,所以 cursor != size 返回 false。


所以,最后只输出"4",即答案为 4.


Iterator 与泛型搭配


  • Iterator 对集合类中的任何一个实现类,都可以返回这样一个 Iterator 对象。可以适用于任何一个类。

  • 因为集合类(List 和 Set 等)可以装入的对象的类型是不确定的,从集合中取出时都是 Object 类型,用时都需要进行强制转化,这样会很麻烦,用上泛型,就是提前告诉集合确定要装入集合的类型,这样就可以直接使用而不用显示类型转换.非常方便.


foreach 和 Iterator 的关系


  • for each 以用来处理集合中的每个元素而不用考虑集合定下标。就是为了让用 Iterator 简单。但是删除的时候,区别就是在 remove,循环中调用集合 remove 会导致原集合变化导致错误,而应该用迭代器的 remove 方法。


使用 for 循环还是迭代器 Iterator 对比


  • 采用 ArrayList 对随机访问比较快,而 for 循环中的 get()方法,采用的即是随机访问的方法,因此在 ArrayList 里,for 循环较快

  • 采用 LinkedList 则是顺序访问比较快,iterator 中的 next()方法,采用的即是顺序访问的方法,因此在 LinkedList 里,使用 iterator 较快

  • 从数据结构角度分析,for 循环适合访问顺序结构,可以根据下标快速获取指定元素.而 Iterator 适合访问链式结构,因为迭代器是通过 next()和 Pre()来定位的.可以访问没有顺序的集合.

  • 而使用 Iterator 的好处在于可以使用相同方式去遍历集合中元素,而不用考虑集合类的内部实现(只要它实现了 java.lang.Iterable 接口),如果使用 Iterator 来遍历集合中元素,一旦不再使用 List 转而使用 Set 来组织数据,那遍历元素的代码不用做任何修改,如果使用 for 来遍历,那所有遍历此集合的算法都得做相应调整,因为 List 有序,Set 无序,结构不同,他们的访问算法也不一样.(还是说明了一点遍历和集合本身分离了)。


总结


  • 迭代出来的元素都是原来集合元素的拷贝。

  • Java 集合中保存的元素实质是对象的引用,而非对象本身。

  • 迭代出的对象也是引用的拷贝,结果还是引用。那么如果集合中保存的元素是可变类型的,那么可以通过迭代出的元素修改原集合中的对象。


发布于: 2021 年 01 月 30 日阅读数: 12
用户头像

田维常

关注

关注公众号:Java后端技术全栈,领500G资料 2020.10.24 加入

关注公众号:Java后端技术全栈,领500G资料

评论

发布
暂无评论
奇葩java迭代器笔试题,做对算你厉害