1.遍歷方法簡介
Java遍歷List的方法主要有四種：
- for each
for(Object o :list) { }
- Iterator
Iterator iter = list.iterator(); while(iter.hasNext()){ Object o = iter.next(); }
- loop without size
int size = list.size(); for(int i=0;i<size;i++){ Object o= list.get(i); }
- loop with size
for(int i=0;i<list.size();i++){ Object o= list.get(i); }
注：這里我們不比較while和for的形式，這對效率影響幾乎是可以忽略的，
我們是否能簡單的得出結論，哪個更快，哪個更慢呢？
嚴謹一點的方法是：基于實驗與資料，才能作出判斷，
1.1. ArrayList測驗分析
經過撰寫測驗代碼，結果如下：（時間單位：納秒）
| Size | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| Foreach | 448,319 | 558,757 | 732,009 | 2,074,092 | 6,169,315 | 15,347,540 |
| IteratorWay | 22,169 | 54,603 | 86,215 | 513,186 | 4,786,587 | 14,032,553 |
| WithoutSize | 14,369 | 32,023 | 158,472 | 828,897 | 3,685,905 | 9,457,398 |
| WithSize | 29,149 | 47,213 | 91,963 | 557,936 | 5,148,280 | 10,051,462 |
可以看出，直接用回圈的方法，get(index)來獲取物件，是最快的方式，而且把i<list.size()放到回圈中去判斷，會影響效率，
For Each的效率最差，用迭代器的效率也沒有很好，但只是相對而言，其實從時間上看最多也就差幾毫秒，
然而，這并不是事實的全部真相！！！
上面的測驗，我們只是用了ArrayList來做為List的實作類，所以才有上面的結論，
For each其實也是用了迭代器來實作，因此當資料量變大時，兩者的效率基本一致，也因為用了迭代器，所以速度上受了影響，不如直接get(index)快，
那為何get(index)會比較快呢？
因為ArrayList是通過動態陣列來實作的，支持隨機訪問，所以get(index)是很快的，迭代器，其實也是通過陣列名+下標來獲取，而且增加了邏輯，自然會比get(index)慢，
看ArrayList的迭代器的源代碼就清楚了，
public boolean hasNext() { return cursor != size; } public Object next() { checkForComodification(); int i = cursor; if(i >= size) throw new NoSuchElementException(); Object aobj[] = elementData; if(i >= aobj.length) { throw new ConcurrentModificationException(); } else { cursor = i + 1; return aobj[lastRet = i]; } }
1.2.LinkedList測驗分析
接下來，我們用LinkedList試試，看看會產生什么效果：（時間單位：納秒）
| Size | 10 | 100 | 1000 | 10000 | 100000 | 1000000 |
| Foreach | 542,745 | 388,379 | 952,063 | 2,257,196 | 9,426,607 | 12,141,976 |
| IteratorWay | 25,454 | 62,814 | 110,848 | 753,767 | 5,875,361 | 12,141,976 |
| WithoutSize | 27,096 | 95,248 | 3,343,097 | 51,302,568 | 3,720,958,713 | 692,276,304,569 |
| WithSize | 13,138 | 98,531 | 2,137,726 | 40,157,815 | 3,671,762,259 | 668,285,601,444 |
結果確實不簡單，跟ArrayList完全不一樣了，
最突出的就是get(index)的方式，隨著size的增加，急劇上升，到10萬資料量時，光遍歷時間都要三四秒，這是很可怕的，
那為何會有這樣的結果呢？還是和LinkedList的實作方式有關，
LinkedList是通過雙向鏈表實作的，無法支持隨機訪問，當你要向一個鏈表取第index個元素時，它需要二分后從某一端開始找，一個一個地數才能找到該元素，這樣一想，就能明白為何get(index)如此費時了，
public Object get(int i) { checkElementIndex(i); return node(i).item; } Node node(int i) { if(i < size >> 1) { Node node1 = first; for(int j = 0; j < i; j++){ node1 = node1.next; return node1; } Node node2 = last; for(int k = size - 1; k > i; k--) node2 = node2.prev; return node2; } }
而迭代器提供的是獲取下一個的方法，時間復雜度為O(1)，所以會比較快，
public boolean hasNext() { return nextIndex < size; } public Object next() { checkForComodification(); if(!hasNext()) { throw new NoSuchElementException(); } else { lastReturned = next; next = next.next; nextIndex++; return lastReturned.item; } }
看這迭代器的源代碼還是很理解的，
2.總結
- 對于ArrayList和LinkedList，在size小于1000時，每種方式的差距都在幾ms之間，差別不大，選擇哪個方式都可以，
- 對于ArrayList，無論size是多大，差距都不大，選擇哪個方式都可以，
- 對于LinkedList，當size較大時，建議使用迭代器或for-each的方式進行遍歷，否則效率會有較明顯的差距，
所以，綜合來看，建議使用for-each，代碼簡潔，性能也不差，
另外，當效率不是重點時，應該在設計上花更多心思了，實際上，把大量物件放到List里面去，本身就應該是要考慮的問題，
至于Vector或Map，就留給感興趣的人去驗證了，
博文轉載自：
Java遍歷List四種方法的效率對比，感謝博主提供博文支持，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/297707.html
標籤：Java
上一篇：【Java代碼之美】 -- 通過Value獲取Map中的鍵值Key的四種方法
下一篇：7張圖了解kafka基本概念