我們使用容器經(jīng)常會(huì)用到遍歷，而之前幾篇文章都沒有提到這一點(diǎn)。所以疏尿，今天把這塊內(nèi)容補(bǔ)一下。
public class ArrayList<E> extends AbstractList<E>
implements List<E>,
RandomAccess,
Cloneable,
java.io.Serializable
ArrayList 集成 AbstractList 抽象類易桃。AbstractList 中提供了兩個(gè)迭代器的實(shí)現(xiàn)類褥琐，默認(rèn)實(shí)現(xiàn)了迭代器接口，實(shí)現(xiàn)了對(duì)元素的遍歷晤郑，它們就是Itr 和其子類 ListItr敌呈。
ArrayList 實(shí)現(xiàn) List 接口，能對(duì)它進(jìn)行隊(duì)列操作造寝。
ArrayList 實(shí)現(xiàn) RandomAccess 接口磕洪，
ArrayList 實(shí)現(xiàn)了 Cloneable 接口，即覆蓋了函數(shù)clone()诫龙，能克隆析显。
ArrayList 實(shí)現(xiàn) java.io.Serializable 接口，這意味著 LinkedList 支持序列化签赃，能通過序列化去傳輸叫榕。
先看看 ArrayList 的三種遍歷
// 先創(chuàng)建一個(gè)100w元素的ArrayList
for (int i=0; i < 1000000; i++){
arrayList.add(i);
}
long start, end;
// foreach循環(huán)
start = System.currentTimeMillis();
for (Integer item : arrayList) {
//System.out.println(item);
}
end = System.currentTimeMillis();
System.out.println("foreach cost time = " + (end-start) + "ms");
// 普通for循環(huán)浑侥，通過get函數(shù)獲取元素
start = System.currentTimeMillis();
for (int i=0; i < arrayList.size(); i++) {
arrayList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for cost time = " + (end-start) + "ms");
// 迭代器循環(huán)
start = System.currentTimeMillis();
Iterator<Integer> it = arrayList.iterator();
while (it.hasNext()) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator cost time = " + (end-start) + "ms");
foreach cost time = 15ms
for cost time = 7ms
Iterator cost time = 29ms
對(duì)同一個(gè)100w元素的ArrayList進(jìn)行三種不同的循環(huán)，我們發(fā)現(xiàn)晰绎，最快的居然是通過get函數(shù)讀取元素寓落。
那么，foreach循環(huán)是什么東西荞下，怎么會(huì)比迭代器快的呢伶选？
使用foreach結(jié)構(gòu)的類對(duì)象必須實(shí)現(xiàn)了Iterable接口，Java的Collection繼承自此接口尖昏，List實(shí)現(xiàn)了Collection仰税，Collection 這個(gè)接口僅包含一個(gè)函數(shù)，源碼如下：
public interface Iterable<T> {
/**
* Returns an iterator over a set of elements of type T.
*
* @return an Iterator.
*/
Iterator<T> iterator();
}
iterator()用于返回一個(gè)Iterator抽诉，原來陨簇，JAVA中的增強(qiáng)for循環(huán)底層是通過迭代器模式來實(shí)現(xiàn)的。
那為什么遍歷ArrayList使用迭代器就這么慢呢迹淌？
我們看下public interface Iterator<E>接口的實(shí)現(xiàn)：
public Iterator<E> iterator() {
return new Itr();
}
/**
* An optimized version of AbstractList.Itr // 這還是優(yōu)化過的版本呢
*/
private class Itr implements Iterator<E> {
// 數(shù)組的游標(biāo)
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
// prevent creating a synthetic constructor
Itr() {}
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
// 臨時(shí)引用指向數(shù)組
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
// 通過數(shù)組索引訪問元素
cursor = i + 1;
return (E) elementData[lastRet = i];
}
原來河绽，ArrayList的迭代器的next()函數(shù)也是通過索引快速訪問到元素的。如果數(shù)組比較小唉窃，那么不管用哪種遍歷性能都差不多耙饰。如果數(shù)組比較大，那么纹份，我們現(xiàn)在知道苟跪，用普通循環(huán)+get讀取元素來遍歷ArrayList，會(huì)比迭代器快一倍蔓涧。這是因?yàn)?code>get做了內(nèi)聯(lián)優(yōu)化處理件已，節(jié)省大量的函數(shù)調(diào)用進(jìn)出時(shí)間。
所以元暴，如果有面試官問你篷扩，ArrayLsit哪種遍歷最快？為什么昨寞？你會(huì)回答了嗎瞻惋？
接下來厦滤，我們來看看LinedList的定義援岩。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>,
Deque<E>,
Cloneable,
java.io.Serializable
LinkedList 集成AbstractSequentialList抽象類，內(nèi)部使用listIterator迭代器來實(shí)現(xiàn)重要的方法
LinkedList 實(shí)現(xiàn) List 接口掏导，能對(duì)它進(jìn)行隊(duì)列操作享怀。
LinkedList 實(shí)現(xiàn) Deque 接口，即能將LinkedList當(dāng)作雙端隊(duì)列使用趟咆。
LinkedList 實(shí)現(xiàn)了Cloneable接口添瓷，即覆蓋了函數(shù)clone()梅屉，能克隆。
LinkedList 實(shí)現(xiàn)java.io.Serializable接口鳞贷，這意味著LinkedList支持序列化坯汤，能通過序列化去傳輸。
先看 LinkedList 的遍歷搀愧。先插入100w個(gè)元素惰聂，然后用foreach、迭代器咱筛、removeFirst 這三種方法遍歷（循環(huán)get不需要測試了搓幌，簡直慢到難以忍受）。
LinkedList linkedList = new LinkedList();
for (int i=0; i<1000000; i++) {
linkedList.add(i);
}
long start, end;
start = System.currentTimeMillis();
for (Object item : linkedList) {
//System.out.println(item);
}
end = System.currentTimeMillis();
System.out.println("foreach cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
Iterator<Integer> it = linkedList.iterator();
while (it.hasNext()) {
it.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator cost time = " + (end-start) + "ms");
start = System.currentTimeMillis();
while (linkedList.size() != 0) {
linkedList.removeFirst();
}
end = System.currentTimeMillis();
System.out.println("removeFirst cost time = " + (end-start) + "ms");
運(yùn)行代碼得到結(jié)果如下：
foreach cost time = 12ms
Iterator cost time = 11ms
removeFirst cost time = 24ms
印證了之前我們分析的結(jié)論迅箩，foreach就是Iterator溉愁，所以它們的效率都差不多。不過從代碼精簡方面來看饲趋，當(dāng)然是foreach更簡單拐揭。
而某些文章提到用removeFirst會(huì)遍歷更快，但是在筆者的環(huán)境下不成立篙贸。
為什么呢投队？我們先看看next()的實(shí)現(xiàn)：
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
真相大白！原來LinkedList為了用迭代器順序遍歷爵川，用了lastReturned保存最近一次返回的節(jié)點(diǎn)敷鸦，next下一次返回的節(jié)點(diǎn)，nextIndex保存下一個(gè)節(jié)點(diǎn)的索引寝贡。
再將元素增大一倍扒披，就是200萬個(gè)元素。
foreach cost time = 20ms
Iterator cost time = 21ms
removeFirst cost time = 37ms
而removeFirst還是比迭代器多10多毫秒圃泡。證明這個(gè)多10ms應(yīng)該是多了節(jié)點(diǎn)刪除操作的開銷碟案。
ok，那么今天我們的結(jié)論就是
- ArrayList推薦用for循環(huán)get元素遍歷最快颇蜡，不僅是連續(xù)內(nèi)存讀取价说，而且還有內(nèi)聯(lián)優(yōu)化節(jié)省函數(shù)調(diào)用開銷。
- LinkedList推薦用foreach遍歷元素最快风秤，因?yàn)閮?nèi)部實(shí)現(xiàn)是迭代器鳖目。
- 相同的數(shù)據(jù)量，ArrayList最快的遍歷比LinkedList最快遍歷快一倍缤弦。
