Java List /ArrayList 三種遍歷方法及性能比較
第一種:
for(Iterator<A> it = list.iterator(); it.hasNext(); ) {
it.next();
....
}
第二種:
for(A a : list) {
.....
}
第三種:
for(int i=0; i<list.size(); i++) {
A a = list.get(i);
...
}
java list三種遍歷方法性能比較：
測試各種遍歷方法的性能，測試方法為在ArrayList中插入1千萬條記錄，然后遍歷ArrayList，發(fā)現(xiàn)了一個奇怪的現(xiàn)象，測試代碼如下：
package com.hisense.tiger.list;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class ListTest {
public static void main(String[] args)
{
List<String> list = new ArrayList<String>();
long t1,t2;
for(int j = 0; j < 10000000; j++)
{
list.add("aaaaaa" + j);
}
System.out.println("List first visit method:");
t1=System.currentTimeMillis();
for(String tmp:list)
{
//System.out.println(tmp);
}
t2=System.currentTimeMillis();
System.out.println("Run Time:" + (t2 -t1) + "(ms)");
System.out.println("List second visit method:");
t1=System.currentTimeMillis();
for(int i = 0; i < list.size(); i++)
{
list.get(i);
//System.out.println(list.get(i));
}
t2=System.currentTimeMillis();
System.out.println("Run Time:" + (t2 -t1) + "(ms)");
System.out.println("List Third visit method:");
Iterator<String> iter = list.iterator();
t1=System.currentTimeMillis();
while(iter.hasNext())
{
iter.next();
//System.out.println(iter.next());
}
t2=System.currentTimeMillis();
System.out.println("Run Time:" + (t2 -t1) + "(ms)");
System.out.println("Finished!!!!!!!!");
}
}
測試結(jié)果如下：
List first visit method:
Run Time:170(ms)
List second visit method:
Run Time:10(ms)
List Third visit method:
Run Time:34(ms)
Finished!!!!!!!!
測試的結(jié)論很奇怪，第一種方法是java語言支持的新語法，代碼最簡潔，但是在三種方法中，性能確是最差的，取size進(jìn)行遍歷性能是最高的，不知道如何解釋
遍歷方法簡介
Java遍歷List的方法主要有：
（1）for each
for(bject o :list)
{
}
（2）Iterator
Iterator iter = list.iterator();
while(iter.hasNext()){
Object o = iter.next();
}
（3）loop without size
int size = list.size();
for(int i=0;i<size;i++){
Object o= list.get(i);
}
（4）loop with size
for(int i=0;i<list.size();i++){
Object o= list.get(i);
}
注：這里我們不比較while和for的形式，這對效率影響幾乎是可以忽略的。
我們是否能簡單的得出結(jié)論，哪個更快，哪個更慢呢？
嚴(yán)謹(jǐn)一點(diǎn)的方法是：基于實驗與數(shù)據(jù)，才能作出判斷。
ArrayList測試分析
經(jīng)過編寫測試代碼，結(jié)果如下：（時間單位：納秒）
Size
10
100
1,000
10,000
100,000
1,000,000
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
可以看出，直接用循環(huán)的方法，get(index)來獲取對象，是最快的方式。而且把i<list.size()放到循環(huán)中去判斷，會影響效率。
For Each的效率最差，用迭代器的效率也沒有很好。但只是相對而言，其實從時間上看最多也就差幾毫秒。
然而，這并不是事實的全部真相?。?！
上面的測試，我們只是用了ArrayList來做為List的實現(xiàn)類。所以才有上面的結(jié)論。
For each其實也是用了迭代器來實現(xiàn)，因此當(dāng)數(shù)據(jù)量變大時，兩者的效率基本一致。也因為用了迭代器，所以速度上受了影響。不如直接get(index)快。
那為何get(index)會比較快呢？
因為ArrayList是通過動態(tài)數(shù)組來實現(xiàn)的，支持隨機(jī)訪問，所以get(index)是很快的。迭代器，其實也是通過數(shù)組名+下標(biāo)來獲取，而且增加了邏輯，自然會比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];
}
}
LinkedList測試分析
接下來，我們用LinkedList試試，看看會產(chǎn)生什么效果：（時間單位：納秒）
Size
10
100
1,000
10,000
100,000
1,000,000
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
結(jié)果確實不簡單，跟ArrayList完全不一樣了。
最突出的就是get(index)的方式，隨著size的增加，急劇上升。到10萬數(shù)據(jù)量時，光遍歷時間都要三四秒，這是很可怕的。
那為何會有這樣的結(jié)果呢？還是和LinkedList的實現(xiàn)方式有關(guān)。
LinkedList是通過雙向鏈表實現(xiàn)的，無法支持隨機(jī)訪問。當(dāng)你要向一個鏈表取第index個元素時，它需要二分后從某一端開始找，一個一個地數(shù)才能找到該元素。這樣一想，就能明白為何get(index)如此費(fèi)時了。
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;
}
而迭代器提供的是獲取下一個的方法，時間復(fù)雜度為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;
}
}
看這迭代器的源代碼還是很理解的。
總結(jié)
（1）對于ArrayList和LinkedList，在size小于1000時，每種方式的差距都在幾ms之間，差別不大，選擇哪個方式都可以。
（2）對于ArrayList，無論size是多大，差距都不大，選擇哪個方式都可以。
（3）對于LinkedList，當(dāng)size較大時，建議使用迭代器或for-each的方式進(jìn)行遍歷，否則效率會有較明顯的差距。
所以，綜合來看，建議使用for-each，代碼簡潔，性能也不差。
另外，當(dāng)效率不是重點(diǎn)時，應(yīng)該在設(shè)計上花更多心思了。實際上，把大量對象放到List里面去，本身就應(yīng)該是要考慮的問題。
至于Vector或Map，就留給感興趣的人去驗證了。
系統(tǒng)信息
最后，附上系統(tǒng)信息：
-- listing properties --
java.vm.version=25.65-b01
java.vm.name=Java HotSpot(TM) 64-BitServer VM
java.runtime.version=1.8.0_65-b17
os.arch=amd64
os.name=Windows 10
java version"1.8.0_66"
Java(TM) SERuntime Environment (build 1.8.0_66-b18)
JavaHotSpot(TM) Client VM (build 25.66-b18, mixed mode)
如對本文有疑問，請?zhí)峤坏浇涣髡搲?，廣大熱心網(wǎng)友會為你解答?。?點(diǎn)擊進(jìn)入論壇
