关于java:从源码解读Java列表的遍历效率

Java列表应该如何遍历效率更好？

Java有三种遍历的形式：

• 一般for循环遍历(for)
• 增强型for循环遍历(foreach)
• 迭代器循环遍历(iterator)

这三种遍历形式是有差异的。

上面先用一个程序来比照不同的列表用不同的遍历形式所花的工夫差异：

import java.util.ArrayList;import java.util.Iterator;import java.util.LinkedList;import java.util.List;/** * @author zhangjianhua * @date 2021-05-09 16:08 * @description 列表for循环 */@SuppressWarnings("ALL")public class Main {    public static void main(String[] args) {        testForeachTransform();        long arrayListForTime = arrayListForTime();        System.out.println("测试ArrayList通过for遍历耗费工夫：" + arrayListForTime);        long arrayListForeachTime = arrayListForeachTime();        System.out.println("测试ArrayList通过foreach遍历耗费工夫：" + arrayListForeachTime);        long arrayListIteratorTime = arrayListIteratorTime();        System.out.println("测试ArrayList通过iterator遍历耗费工夫：" + arrayListIteratorTime);        long linkedListForTime = linkedListForTime();        System.out.println("测试LinkedList通过for遍历耗费工夫：" + linkedListForTime);        long linkedListForeachTime = linkedListForeachTime();        System.out.println("测试LinkedList通过foreach遍历耗费工夫：" + linkedListForeachTime);        long linkedListIteratorTime = linkedListIteratorTime();        System.out.println("测试LinkedList通过iterator遍历耗费工夫：" + linkedListIteratorTime);        // 依据测试后果：        // ArrayList通过for遍历和通过iterator遍历差不多        // LinkedList通过iterator遍历比通过for遍历要快很多        // 在咱们的利用中，要思考应用List接口的哪种实现类，能够更好更高效的满足理论场景需要        // 通过实现RandomAccess接口来辨别List的哪种实现类        // 实现RandomAccess接口的List通过for遍历数据，和通过iterator遍历数据差不多        // 未实现RandomAccess接口的List通过iterator遍历数据，比通过for遍历数据高效很多    }    /**     * 测试foreach转换成什么     */    private static void testForeachTransform() {        System.out.println("测试foreach转换成什么");        // 对于根本类型数组，foreach遍历会转为for遍历，因为没有实现iterator        // 对于List，foreach遍历会转为iterator遍历，因为实现了iterator        // 运行后查看编译后的class文件即可看到foreach转换成什么        int[] arrays = {1, 2, 3, 4, 5};        for (int i = 0; i < arrays.length; ++i) {        }        for (int array : arrays) {        }        List<Integer> list = new ArrayList<>();        list.add(1);        list.add(2);        list.add(3);        list.add(4);        list.add(5);        for (int i = 0; i < list.size(); ++i) {        }        for (int element : list) {        }    }    /**     * 测试ArrayList通过for遍历耗费工夫     *     * @return 耗费工夫     */    private static long arrayListForTime() {        List<Integer> arrayList = new ArrayList<>();        for (int i = 0; i < 100000; i++) {            arrayList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过for遍历        for (int i = 0; i < arrayList.size(); i++) {            arrayList.get(i);        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }    /**     * 测试ArrayList通过foreach遍历耗费工夫     *     * @return 耗费工夫     */    private static long arrayListForeachTime() {        List<Integer> arrayList = new ArrayList<>();        for (int i = 0; i < 100000; i++) {            arrayList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过foreach遍历        for (int array : arrayList) {        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }    /**     * 测试ArrayList通过iterator遍历耗费工夫     *     * @return 耗费工夫     */    private static long arrayListIteratorTime() {        List<Integer> arrayList = new ArrayList<>();        for (int i = 0; i < 100000; i++) {            arrayList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过iterator遍历        Iterator<Integer> iterator = arrayList.iterator();        while (iterator.hasNext()) {            iterator.next();        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }    /**     * 测试LinkedList通过for遍历所耗费工夫     *     * @return 耗费工夫     */    private static long linkedListForTime() {        List<Integer> linkedList = new LinkedList<>();        for (int i = 0; i < 100000; i++) {            linkedList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过for遍历        for (int i = 0; i < linkedList.size(); i++) {            linkedList.get(i);        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }    /**     * 测试LinkedList通过for遍历所耗费工夫     *     * @return 耗费工夫     */    private static long linkedListForeachTime() {        List<Integer> linkedList = new LinkedList<>();        for (int i = 0; i < 100000; i++) {            linkedList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过foreach遍历        for (int array : linkedList) {        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }    /**     * 测试LinkedList通过iterator遍历所耗费工夫     *     * @return 耗费工夫     */    private static long linkedListIteratorTime() {        List<Integer> linkedList = new LinkedList<>();        for (int i = 0; i < 100000; i++) {            linkedList.add(i);        }        // 记录开始工夫        long startTime = System.currentTimeMillis();        // 通过iterator遍历        Iterator<Integer> iterator = linkedList.iterator();        while (iterator.hasNext()) {            iterator.next();        }        // 记录完结工夫        long endTime = System.currentTimeMillis();        // 返回耗费工夫        return endTime - startTime;    }}

来看运行后果：

咱们能够发现，对于程序式列表ArrayList，一般for循环、增强型for循环、迭代器循环三者差异不大，遍历10万次都是破费2ms。

然而对于链式列表LinkedList，一般for循环和增强型for循环、迭代器循环的差异十分大，一般for循环遍历10万次破费4390ms，而增强型for循环、迭代器循环遍历10万次仅破费3ms、1ms。

为什么会这样？

因为程序式列表用三种遍历的任意一种，工夫复杂度都是O(n)。而链式列表用一般for循环遍历，工夫复杂度是O(n^2)，然而如果链式列表用增强型for循环、迭代器循环的工夫复杂度是O(n)，相差了一个数量级的工夫，所以链式列表用一般for循环遍历会很慢。

首先，对于列表的增强型for循环，其实是等同于迭代器循环的。

如何看出的？

能够看编译后的class文件，通过反编译能够看到列表的增强型for循环转换为迭代器循环。不过这里要说一下，对于根本类型的数组应用增强型for循环，编译后是转换为一般for循环的，不是转换为迭代器循环，因为根本类型的数组没有定义迭代器循环的办法，所以就转换为了一般for循环。

下面运行程序的testForeachTransform办法，有做了列表的增强型for循环和根本类型数组的增强型for循环的转换比照测试，运行程序后查看编译后的class文件，能够看到转换成了什么代码，前面的剖析会具体开展说。

因为对于列表，增强型for循环转换为迭代器循环，而列表分为程序式和链式，所以从四个方面去剖析：

• 程序式列表的一般for循环
• 程序式列表的增强型for循环
• 链式列表的一般for循环
• 链式列表的增强型for循环

为什么链式列表用了迭代器循环会比一般for循环少一个指数数量级的工夫？咱们能够通过看源码找到答案。

上面手把手地教大家如何看源码，如何从源码中找到遍历效率的答案：

筹备

这里以jdk1.8作为测试，从GitHub找到测试源码，地址：https://github.com/zjhpure/so...

用idea关上，关上如图所示的中央。

1、程序式列表的一般for循环

找到arrayListForTime办法，如下图：

从代码能够看出，记录开始工夫和记录完结工夫之间的代码就是for循环耗费的工夫，遍历的每一次都是调用get办法，所以只有晓得get办法耗费的工夫是多少，就能晓得for循环一共耗费多少工夫。咱们先通过idea的跳转性能，看看get办法的源码，然而跳转后显示的是一个接口，如下图：

怎么办？应该怎样才能找到get办法的源码？

这时候须要通过打断点来调试，能力找到get办法的源码。在get办法处打一个断点，点击调试按钮，程序运行后会跳到get办法处停着，调试时执行Force Step Into，跳入到get办法的源码中，就能够看到get办法的源码，如下图：

咱们能够看到get办法源码是长这样的，如下图：

如果在调试看get办法的源码时又遇到接口，继续执行Force Step Into，跳进办法外部，就能够看到办法的源码。前面还会有很多看源码的操作，就不会再细写怎么找到源码的办法了，同样依照下面的操作就能找到。

回到源码，这里由两局部组成，首先执行rangeCheck办法，再执行elementData办法。第一步的rangeCheck办法，其实就是查看输出的下标是否超过了数组的长度size，源码如下：

    /**     * Checks if the given index is in range.  If not, throws an appropriate     * runtime exception.  This method does *not* check if the index is     * negative: It is always used immediately prior to an array access,     * which throws an ArrayIndexOutOfBoundsException if index is negative.     */    private void rangeCheck(int index) {        if (index >= size)            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }

第二步的elementData办法，源码如下：

    // Positional Access Operations    @SuppressWarnings("unchecked")    E elementData(int index) {        return (E) elementData[index];    }

这里间接就是从elementData数组中取元素，因为是程序式列表，底层是用数组保留元素的，通过idea点击跳转elementData能够看到elementData是一个数组，如下图：

所以综上所述能够看到，对于程序式列表的一般for循环，每次get办法的工夫复杂度是O(1)，遍历n个元素的工夫复杂度是O(n)。

2、程序式列表的增强型for循环

对于列表，增强型for循环会转换为迭代器循环，能够从Java运行后编译的class文件找到答案，咱们先找到testForeachTransform办法，如下图：

点击运行程序，查看编译生成的class文件，咱们能够看到，对于根本类型数组，增强型for循环转换为一般for循环，而对于列表，增强型for循环转换为迭代器循环，如下图：

所以剖析列表的增强型for循环，其实就是剖析列表的迭代器循环，上面剖析程序式列表的迭代器循环

咱们找到arrayListIteratorTime办法，如下图：

遍历的每一次都是调用next办法，所以只有晓得next办法耗费的工夫是多少，就能晓得迭代器循环一共耗费多少工夫。列表arrayList先调用iterator办法获取迭代器iterator，而后每次遍历调用迭代器iterator的next办法，咱们先看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();    }

在iterator办法里，创立一个Itr对象，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;        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();        }    }

正好能够看到Itr类有一个next办法和hasNext办法，在while循环的条件里调用的就是hasNext办法，从源码能够看到，hasNext办法就是判断游标cursor是否等于列表的长度size，一旦等于，while循环完结。

咱们来剖析next办法，next办法的源码只有三句是要害，如下图：

ArrayList.this.elementData就是获取列表的数组，而后cursor=i + 1，就是游标加1，最初从数组elementData中取元素，返回元素。

所以综上所述能够看到，对于程序式列表的增强型for循环(迭代器循环)，每次next办法的工夫复杂度是O(1)，遍历n个元素的工夫复杂度是O(n)。

3、链式列表的一般for循环

找到linkedListForTime办法，如下图：

用同样的办法去浏览源码，咱们能够发现遍历的每一次都是调用get办法，所以只有晓得get办法耗费的工夫是多少，就能晓得for循环一共耗费多少工夫。找到get办法的源码，如下：

    /**     * Returns the element at the specified position in this list.     *     * @param index index of the element to return     * @return the element at the specified position in this list     * @throws IndexOutOfBoundsException {@inheritDoc}     */    public E get(int index) {        checkElementIndex(index);        return node(index).item;    }

先调用checkElementIndex办法，再返回node(index).item。咱们来看checkElementIndex办法的源码，如下：

    private void checkElementIndex(int index) {        if (!isElementIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }

这里调用了isElementIndex办法，再看isElementIndex办法的源码，如下：

    /**     * Tells if the argument is the index of an existing element.     */    private boolean isElementIndex(int index) {        return index >= 0 && index < size;    }

从源码能够看到，这个办法的意思就是判断是否是元素的下标，其实和程序式列表的rangeCheck办法差不多，都是判断下标的合法性。那么再看后面get办法的node(index).item，源码如下：

    /**     * Returns the (non-null) Node at the specified element index.     */    Node<E> node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node<E> x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node<E> x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }

因为是链式列表，底层用链表保留元素。从node办法的源码能够看出整个过程，先判断下标地位是在两头靠右还是两头靠左，如果两头靠左，那就从开始节点往后面一个一个地寻找，如果是两头靠右，那就从完结节点往前面一个一个地寻找，所以链式列表寻找一个元素的工夫复杂度是O(n)。

从这里就能够看出，链式列表寻找一个元素的效率就比程序式列表寻找一个元素的效率要低很多了，因为程序式列表寻找一个元素的工夫复杂度是O(1)，链式列表寻找一个元素的工夫复杂度是O(n)。

因为要有n个元素须要遍历，所以链式列表遍历n个元素的工夫复杂度是O(n^2)，链式列表的一般for循环很慢，比程序式列表的一般for循环慢了一个数量级。

然而链式列表寻找一个元素并不是每一个都要n次能力找到的，依据这里的源码能够发现，会依据下标在两头靠右还是靠左来判断是从开始节点往后还是从完结节点往前，综合起来，寻找的工夫是1，2，3，4...n/2，n/2...4，3，2，1。

总次数：(1+n/2)n/2=3/4n^2，四分之三n的平方，同样也是n的平方的数量级。

所以综上所述能够看到，对于链式列表的一般for循环，每次get办法的工夫复杂度是O(n)，遍历n个元素的工夫复杂度是O(n^2)。

4、链式列表的增强型for循环

对于链式列表，增强型for循环同样也会转换为迭代器循环。

所以剖析列表的增强型for循环，其实就是剖析列表的迭代器循环，上面剖析链式列表的迭代器循环

咱们找到linkedListIteratorTime办法，如下图：

遍历的每一次都是调用next办法，所以只有晓得next办法耗费的工夫是多少，就能晓得迭代器循环一共耗费多少工夫。列表linkedList先调用iterator办法获取迭代器iterator，而后每次遍历调用迭代器iterator的next办法，咱们先看iterator办法的源码，如下：

    /**     * Returns an iterator over the elements in this list (in proper     * sequence).<p>     *     * This implementation merely returns a list iterator over the list.     *     * @return an iterator over the elements in this list (in proper sequence)     */    public Iterator<E> iterator() {        return listIterator();    }

在iterator办法里，调用listIterator办法，源码如下：

    /**     * {@inheritDoc}     *     * <p>This implementation returns {@code listIterator(0)}.     *     * @see #listIterator(int)     */    public ListIterator<E> listIterator() {        return listIterator(0);    }

在listIterator办法里，调动办法listIterator(0)，这里的意思是从链表的第一个元素开始，源码如下：

    /**     * Returns a list-iterator of the elements in this list (in proper     * sequence), starting at the specified position in the list.     * Obeys the general contract of {@code List.listIterator(int)}.<p>     *     * The list-iterator is <i>fail-fast</i>: if the list is structurally     * modified at any time after the Iterator is created, in any way except     * through the list-iterator's own {@code remove} or {@code add}     * methods, the list-iterator will throw a     * {@code ConcurrentModificationException}.  Thus, in the face of     * concurrent modification, the iterator fails quickly and cleanly, rather     * than risking arbitrary, non-deterministic behavior at an undetermined     * time in the future.     *     * @param index index of the first element to be returned from the     *              list-iterator (by a call to {@code next})     * @return a ListIterator of the elements in this list (in proper     *         sequence), starting at the specified position in the list     * @throws IndexOutOfBoundsException {@inheritDoc}     * @see List#listIterator(int)     */    public ListIterator<E> listIterator(int index) {        checkPositionIndex(index);        return new ListItr(index);    }

在另一个listIterator办法里，调用checkPositionIndex办法，而后创立一个ListItr对象，ListItr类是一个外部类，咱们先看checkPositionIndex办法，源码如下：

    private void checkPositionIndex(int index) {        if (!isPositionIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }

在checkPositionIndex办法里，调用isPositionIndex办法，源码如下：

    /**     * Tells if the argument is the index of a valid position for an     * iterator or an add operation.     */    private boolean isPositionIndex(int index) {        return index >= 0 && index <= size;    }

从源码能够看到，isPositionIndex办法的意思就是判断是否是元素的下标，和程序式列表的rangeCheck办法差不多，都是判断下标的合法性。咱们再看ListItr类的源码，如下：

    private class ListItr implements ListIterator<E> {        private Node<E> lastReturned;        private Node<E> next;        private int nextIndex;        private int expectedModCount = modCount;        ListItr(int index) {            // assert isPositionIndex(index);            next = (index == size) ? null : node(index);            nextIndex = index;        }        public boolean hasNext() {            return nextIndex < size;        }        public E next() {            checkForComodification();            if (!hasNext())                throw new NoSuchElementException();            lastReturned = next;            next = next.next;            nextIndex++;            return lastReturned.item;        }        public boolean hasPrevious() {            return nextIndex > 0;        }        public E previous() {            checkForComodification();            if (!hasPrevious())                throw new NoSuchElementException();            lastReturned = next = (next == null) ? last : next.prev;            nextIndex--;            return lastReturned.item;        }        public int nextIndex() {            return nextIndex;        }        public int previousIndex() {            return nextIndex - 1;        }        public void remove() {            checkForComodification();            if (lastReturned == null)                throw new IllegalStateException();            Node<E> lastNext = lastReturned.next;            unlink(lastReturned);            if (next == lastReturned)                next = lastNext;            else                nextIndex--;            lastReturned = null;            expectedModCount++;        }        public void set(E e) {            if (lastReturned == null)                throw new IllegalStateException();            checkForComodification();            lastReturned.item = e;        }        public void add(E e) {            checkForComodification();            lastReturned = null;            if (next == null)                linkLast(e);            else                linkBefore(e, next);            nextIndex++;            expectedModCount++;        }        public void forEachRemaining(Consumer<? super E> action) {            Objects.requireNonNull(action);            while (modCount == expectedModCount && nextIndex < size) {                action.accept(next.item);                lastReturned = next;                next = next.next;                nextIndex++;            }            checkForComodification();        }        final void checkForComodification() {            if (modCount != expectedModCount)                throw new ConcurrentModificationException();        }    }

正好能够看到ListItr类有一个next办法和hasNext办法，在while循环的条件里调用的就是hasNext办法，从源码能够看到，hasNext办法就是判断游标nextIndex是否等于列表的长度size，一旦等于，while循环完结。

咱们来剖析next办法，从next办法的源码能够发现，它在沿着链表一直往后遍历，如下图：

所以迭代器循环遍历n个元素的工夫复杂度是O(n)，比一般for循环遍历n个元素的O(n^2)快了一个数量级。

为什么忽然就升高一个数量级了？

咱们认真比照下面的源码就能够看出，其实迭代器循环的遍历只是扭转了一下思路，对于链式列表的一般for循环，每次查找一个元素都要从链表的开始节点或完结节点往两头一个一个地找，这样找一个元素，那就要O(n)的工夫复杂度了。然而咱们想一下，原本就是要遍历全副元素的，能不能不要每次都从新寻找一次元素？当然能够，因为每一个元素都保留有下一个节点的地址，所以就能够换一个思路了，从开始节点开始遍历，通过节点找到下一个节点，再通过下一个节点找到下下一个节点，直到完结节点，就不须要每次寻找一个元素都要从新寻找一次了。

迭代器循环的遍历就是下面的思路。一个思路的简略扭转，就能把工夫升高一个数量级。

对于链式列表，应用一般for循环遍历，每次get办法的工夫复杂度是O(n)，然而应用迭代器循环遍历，每次next办法的工夫复杂度是O(1)，所以可能大幅减低工夫。而链式列表之所以每次next办法的工夫复杂度是O(1)，是因为每次next办法都是将指针向后挪动一位，而不是像一般for循环的get办法那样从头到尾寻找一次。

所以综上所述能够看到，对于链式列表的增强型for循环(迭代器循环)，每次next办法的工夫复杂度是O(1)，遍历n个元素的工夫复杂度是O(n)。

总结

依据测试后果：

• ArrayList通过一般for循环遍历10万条数据，破费2ms，工夫复杂度O(n)。
• ArrayList通过增强型for循环遍历10万条数据，破费2ms，工夫复杂度O(n)。
• ArrayList通过迭代器循环遍历10万条数据，破费2ms，工夫复杂度O(n)。
• LinkedList通过一般for循环遍历10万条数据，破费4390ms，工夫复杂度O(n^2)，显著慢很多。
• LinkedList通过增强型for循环遍历10万条数据，破费3ms，工夫复杂度O(n)。
• LinkedList通过迭代器循环遍历10万条数据，破费1ms，工夫复杂度O(n)。

论断：

• 对于程序式列表，应用一般for循环遍历数据
• 对于链式列表，应用增强型for循环遍历数据

公众号：纯净编程说(chunjie_tech)

原文链接：https://mp.weixin.qq.com/s/A8...