ArrayList哪種循環效率更好你真的清楚嗎

ArrayList簡介

<code>聲明：以下內容都是基於jdk1.8的 

/<code>

• ArrayList 是一個數組隊列，相當於 動態數組。與Java中的數組相比，它的容量能動態增長。它繼承於AbstractList，實現了List, RandomAccess, Cloneable, java.io.Serializable這些接口。
  看過ArrayList 源碼的同學有沒有注意過有這麼一個細節：為什麼ArrayList實現了RandomAccess這個接口，但是 LinkedList卻沒有實現這個接口？這是一個空接口，裡面沒有任何的方法，有什麼作用呢？
  答案: RandomAccess 是一個標誌接口，表明實現這個這個接口的 List 集合是支持快速隨機訪問的。也就是說，實現了這個接口的集合是支持 快速隨機訪問 策略的。而LinkedList是不能實現隨機訪問的。

ArrayList數據結構

ArrayList包含了兩個重要的對象：elementData 和 size。

• elementData 是"Object[]類型的數組"，它保存了添加到ArrayList中的元素。實際上，elementData是個動態數組。
  那是不是有人就會問既然ArrayList本質是數組，那為啥它的長度可以改變?
  首先，數組的確長度不能改變。不過，ArrayList內部有一系列騷操作，大概就是它每次覺得長度不夠就會 創建一個新數組，這個新數組的容量比原來多出50%，把原來的數組copy過來，然後把以前的數組銷燬掉。
• size 則是動態數組的實際大小。

ArrayList遍歷方式

• 第1種，普通for循環隨機訪問，通過索引值去遍歷。

<code>     // 隨機訪問
     List<string> list = new ArrayList<>();
     int size = list.size();
     for (int i = 0; i < size; i++) {
         value = list.get(i);
     }
/<string>/<code>

• 第2種，通過迭代器遍歷。即通過Iterator去遍歷。

<code>     // 增強for循環
    for (String s : list) {
        value = s;
    }
/<code>

• 第3種，增強for循環遍歷。

<code>     // 迭代器遍歷
    Iterator<string> iter = list.iterator();
    while (iter.hasNext()) {
        value = iter.next();
    }
/<string>/<code>

• 第4種 forEach + lambda 循環遍歷

<code>     list.forEach(p -> {
                p.hashCode();
            });
/<code>

既然有4種遍歷，那我們看看哪種遍歷效率下面我們通過一個實驗來看下這四種循環的耗時吧：測試代碼

<code>/**
 * @Date: 2020/4/23 
 * @Description:
 */
public class ArrayListTest {
    public static void main(String[] args) {
        // 數據預熱
       /* List<string> testList = createTestList(10);
        testForEach(testList);
        testFor(testList);
        testRandFor(10,testList);*/
        List<integer> integers = Arrays.asList(10, 50, 100,500,1000, 10000, 50000, 100000, 5000000, 10000000,30000000);
        for (Integer i : integers) {
            testRand(i);
        }

    }

    private static void testRand(int size) {
        System.out.println("-----------次數:" + size + "------------");
        List<string> list = createTestList(size);
        // 隨機訪問通過索引值去遍歷。
        long time1 = System.nanoTime();
        testRandFor(size, list);
        long time2 = System.nanoTime();
        // 增強for循環
        testFor(list);
        long time3 = System.nanoTime();
        // 迭代器遍歷
        testIterator(list);
        long time4 = System.nanoTime();
        // forEach + lambda
        testForEach(list);
        long time5 = System.nanoTime();
 

        System.out.println("隨機訪問\\t\\t" + (time2 - time1) / 1000 + " ms");
        System.out.println("增強for遍歷\\t\\t" + (time3 - time2) / 1000 + " ms");
        System.out.println("迭代器遍歷\\t\\t" + (time4 - time3) / 1000 + " ms");
        System.out.println("forEach遍歷\\t\\t" + (time5 - time4) / 1000 + " ms");
        System.out.println();
    }

    private static void testRandFor(int size, List<string> list) {
        for (int i = 0; i < size; i++) {
            list.get(i).hashCode();
        }
    }

    private static void testFor(List<string> list) {
        for (String s : list) {
            s.hashCode();
        }
    }

    private static void testIterator(List<string> list) {
        Iterator<string> iter = list.iterator();
        while (iter.hasNext()) {
            iter.next().hashCode();
        }
    }

    private static void testForEach(List<string> list) {
        list.forEach(p -> {
            p.hashCode();
        });
    }

    public static List<string> createTestList(int size) {
        List<string> list = new ArrayList<>(size);
        for (int i = 0; i < size; i++) {
            list.add(UUID.randomUUID().toString());
        }
        return list;
    }
}

/<string>/<string>/<string>/<string>/<string>/<string>/<string>/<string>/<integer>/<string>/<code>

測試數據結果如下：

<code>-----------次數:10------------
隨機訪問\t\t8 ms 

增強for遍歷\t\t5 ms
迭代器遍歷\t\t2 ms
forEach遍歷\t\t40358 ms

-----------次數:50------------
隨機訪問\t\t4 ms
增強for遍歷\t\t8 ms
迭代器遍歷\t\t7 ms
forEach遍歷\t\t5 ms

-----------次數:100------------
隨機訪問\t\t13 ms
增強for遍歷\t\t18 ms
迭代器遍歷\t\t14 ms
forEach遍歷\t\t10 ms

-----------次數:500------------
隨機訪問\t\t54 ms
增強for遍歷\t\t28 ms
迭代器遍歷\t\t24 ms
forEach遍歷\t\t57 ms

-----------次數:1000------------
隨機訪問\t\t106 ms
增強for遍歷\t\t56 ms
迭代器遍歷\t\t50 ms
forEach遍歷\t\t37 ms

-----------次數:10000------------
隨機訪問\t\t1192 ms
增強for遍歷\t\t892 ms
迭代器遍歷\t\t861 ms
forEach遍歷\t\t594 ms

-----------次數:50000------------
隨機訪問\t\t3651 ms
增強for遍歷\t\t2908 ms
迭代器遍歷\t\t2563 ms
forEach遍歷\t\t2712 ms 


-----------次數:100000------------
隨機訪問\t\t10693 ms
增強for遍歷\t\t5273 ms
迭代器遍歷\t\t9294 ms
forEach遍歷\t\t3638 ms

-----------次數:5000000------------
隨機訪問\t\t238922 ms
增強for遍歷\t\t29914 ms
迭代器遍歷\t\t30533 ms
forEach遍歷\t\t28016 ms

-----------次數:10000000------------
隨機訪問\t\t431047 ms
增強for遍歷\t\t47151 ms
迭代器遍歷\t\t46371 ms
forEach遍歷\t\t38943 ms

-----------次數:30000000------------
隨機訪問\t\t1163935 ms
增強for遍歷\t\t137710 ms
迭代器遍歷\t\t139211 ms
forEach遍歷\t\t129960 ms
/<code>

• 結論：如果數據量比較少的話貌似四種循環耗時都差不多，但是隨著數據量的增長會發現foreach的效率是最好的。
  但是從上面我們會發現一個奇怪的現象，第一次循環的時候forEach遍歷的時間是最長的儘管數據量非常少也會這樣。但是後面的耗時就正常了。如果放開測試裡面的預熱代碼，每次跑出來的耗時也是正常的。
• 這個結論貌似和網上的一些結論有點誤差：如果你在百度上搜索java for foreach java8 等關鍵詞會出現很多的搜索結果，比如這幾個循環效率的對比。並且很多博主的結論是java8的foreach循環是真的菜，效率不是差的一點點！！！慎用，之類的。
  若java8的foreach效率如此低下，為何還要推出？難道jdk的開發人員不會優化一下？帶著這個思考，我仔細看了“已往之不諫”的博主最後為java8 正名的博客，寫的不錯，測試也很充分（說實話，沒有仔細的閱讀）但是結論很明顯。java8勝了。作者為了證明java8不是吃素的，確實下了不少功夫。最後的最後，作者提到了，“java8的foreach預熱是jvm級別的，需要預熱。”原文鏈接感興趣的可以去看下。

ArrayList刪除數據

雖然有四種遍歷方式，但是能夠正確刪除數據的方式只有兩種

• 第1種通過迭代器進行刪除。這種方式的話，也是《阿里代碼規約》所推薦的。

<code> Iterator<string> iter = list.iterator();
        while (iter.hasNext()) {
            iter.next().hashCode();
            iter.remove();
        } 

/<string>/<code>

• 第2種倒序循環刪除

<code>  for(int i = list.size()-1;i>=0;i--){
            list.remove(i);
        }
/<code>

下面再演示下錯誤的刪除操作

• 普通for循環正序刪除，刪除過程中元素向左移動，不能刪除重複的元素

<code>        List<string> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("2");
        for(int i=0;i<list.size>           list.remove(i);
        }
        System.out.println(String.join(",",list));
/<list.size>/<string>/<code>

結果輸出：1

• 增強for循環刪除會拋出 java.util.ConcurrentModificationException

ArryList注意點

• 謹慎使用ArrayList中的subList方法ArrayList的subList結果不可強轉成ArrayList，否則會拋出ClassCastException 異常，即 java.util.RandomAccessSubList cannot be cast to java.util.ArrayList. 說明：subList 返回的是 ArrayList 的內部類 SubList，並不是 ArrayList ，而是 ArrayList 的一個視圖，對於 SubList 子列表的所有操作最終會反映到原列表上。

<code>  List<string> list = new ArrayList<>();
                list.add("1");
                list.add("1");
                list.add("2");
                ArrayList<string> strings =  (ArrayList)list.subList(0, 1);
      
      運行結果：
      Exception in thread "main" java.lang.ClassCastException: java.util.ArrayList$SubList cannot be cast to java.util.ArrayList
      \tat com.workit.demo.listener.ArrayListTest.main(ArrayListTest.java:29)/<string>/<string>/<code>

• 在 subList 場景中，高度注意對原集合元素個數的修改，會導致子列表的遍歷、增加、 刪除均會產ConcurrentModificationException 異常。

<code>   List<string> list = new ArrayList<>();
        list.add("1");
        list.add("1");
        list.add("2");
        List<string> subList =  list.subList(0, 1);
        // 對原List增加一個值
        list.add("10");
        subList.add("11"); // 這一行會報 java.util.ConcurrentModificationException

/<string>/<string>/<code>

• 初始化List的時候儘量指定它的容量大小。(儘量減少擴容次數)

閱讀更多 JAVA 的文章

關鍵字: 循環 數據結構 哪種