ArrayList 為什么要實(shí)現(xiàn) RandomAccess 接口？
點(diǎn)擊上方藍(lán)色“程序猿DD”，選擇“設(shè)為星標(biāo)”
回復(fù)“資源”獲取獨(dú)家整理的學(xué)習(xí)資料！
在我們的開(kāi)發(fā)中，List接口是最常見(jiàn)不過(guò)，而且我們幾乎每天都在用ArrayList或者LinkedList，但是細(xì)心的同學(xué)有沒(méi)有發(fā)現(xiàn)，ArrayList中實(shí)現(xiàn)了RandomAccess接口，而LinkedList卻沒(méi)有實(shí)現(xiàn)RandomAccess接口，這是為什么呢？
public?class?ArrayList<E>?extends?AbstractList<E>
????????implements?List<E>,?RandomAccess,?Cloneable,?java.io.Serializable
public?class?LinkedList<E>
????extends?AbstractSequentialList<E>
????implements?List<E>,?Deque<E>,?Cloneable,?java.io.Serializable
RandomAccess接口中是空的，RandomAccess接口又是什么呢？
public?interface?RandomAccess?{
}
RandomAccess接口
RandomAccess是一個(gè)標(biāo)記接口，官方解釋是只要List實(shí)現(xiàn)這個(gè)接口，就能支持快速隨機(jī)訪問(wèn)。而什么是隨機(jī)訪問(wèn)呢？接下來(lái)我們來(lái)舉例說(shuō)明。
Collections是集合的一個(gè)工具類，我們看一下Collections源碼中的二分搜索方法。
public?static?
????int?binarySearch(Listsuper?T>>?list,?T?key)?{
????????if?(list?instanceof?RandomAccess?||?list.size()????????????return?Collections.indexedBinarySearch(list,?key);
????????else
????????????return?Collections.iteratorBinarySearch(list,?key);
????}
在源碼中可以看出，判斷l(xiāng)ist是否是RandomAccess的實(shí)例，如果是，則執(zhí)行indexedBinarySearch方法，如果不是，則執(zhí)行iteratorBinarySearch方法。接下來(lái)看一下這兩個(gè)方法。
private?static?
int?indexedBinarySearch(Listsuper?T>>?list,?T?key)?{
????int?low?=?0;
????int?high?=?list.size()-1;
????while?(low?<=?high)?{
????????int?mid?=?(low?+?high)?>>>?1;
????????Comparablesuper?T>?midVal?=?list.get(mid);
????????int?cmp?=?midVal.compareTo(key);
????????if?(cmp?0)
????????????low?=?mid?+?1;
????????else?if?(cmp?>?0)
????????????high?=?mid?-?1;
????????else
????????????return?mid;?//?key?found
????}
????return?-(low?+?1);??//?key?not?found
}
private?static?
int?iteratorBinarySearch(Listsuper?T>>?list,?T?key)
{
????int?low?=?0;
????int?high?=?list.size()-1;
????ListIteratorsuper?T>>?i?=?list.listIterator();
????while?(low?<=?high)?{
????????int?mid?=?(low?+?high)?>>>?1;
????????Comparablesuper?T>?midVal?=?get(i,?mid);
????????int?cmp?=?midVal.compareTo(key);
????????if?(cmp?0)
????????????low?=?mid?+?1;
????????else?if?(cmp?>?0)
????????????high?=?mid?-?1;
????????else
????????????return?mid;?//?key?found
????}
????return?-(low?+?1);??//?key?not?found
}
上述兩個(gè)方法的源碼表示，實(shí)現(xiàn)了RandomAccess接口的List使用索引遍歷，而未實(shí)現(xiàn)RandomAccess接口的List使用迭代器遍歷。那么為什么要這么設(shè)計(jì)呢？
既然涉及到二分搜索的遍歷操作，那么現(xiàn)在我們來(lái)分析一下ArrayList和LinkedList遍歷元素的性能如何？
public?class?CollectionTest?{
????public?static?void?main(String[]?args){
????????long?arrayListIndexedTime?=?arrayListIndexed();
????????long?arrayListIteratorTime?=?arrayListIterator();
????????long?linkedListIndexedTime?=?linkedListIndexed();
????????long?linkedListIteratorTime?=?linkedListIterator();
????????System.out.println("測(cè)試ArrayList通過(guò)for遍歷所消耗時(shí)間："?+?arrayListIndexedTime);
????????System.out.println("測(cè)試ArrayList通過(guò)iterator遍歷所消耗時(shí)間："?+?arrayListIteratorTime);
????????System.out.println("測(cè)試LinkedList通過(guò)for遍歷所消耗時(shí)間："?+?linkedListIndexedTime);
????????System.out.println("測(cè)試LinkedList通過(guò)iterator遍歷所消耗時(shí)間："?+?linkedListIteratorTime);
????}
????//測(cè)試ArrayList通過(guò)for遍歷所消耗時(shí)間
????public?static?long?arrayListIndexed()?{
????????List?arrayList?=?new?ArrayList<>();
????????for?(int?i?=?0;?i?10000;?i++)?{
????????????arrayList.add(i);
????????}
????????//記錄開(kāi)始時(shí)間
????????long?startTime?=?System.currentTimeMillis();
????????for?(int?i?=?0;?i?????????????arrayList.get(i);
????????}
????????//記錄結(jié)束時(shí)間
????????long?endTime?=?System.currentTimeMillis();
????????//遍歷消耗時(shí)間
????????long?resultTime?=?endTime?-?startTime;
????????return?resultTime;
????}
????//測(cè)試ArrayList通過(guò)iterator遍歷所消耗時(shí)間
????public?static?long?arrayListIterator()?{
????????List?arrayList?=?new?ArrayList<>();
????????for?(int?i?=?0;?i?10000;?i++)?{
????????????arrayList.add(i);
????????}
????????//記錄開(kāi)始時(shí)間
????????long?startTime?=?System.currentTimeMillis();
????????Iterator?iterator?=?arrayList.iterator();
????????while?(iterator.hasNext())?{
????????????iterator.next();
????????}
????????//記錄結(jié)束時(shí)間
????????long?endTime?=?System.currentTimeMillis();
????????//遍歷消耗時(shí)間
????????long?resultTime?=?endTime?-?startTime;
????????return?resultTime;
????}
????//測(cè)試LinkedList通過(guò)for遍歷所消耗時(shí)間
????public?static?long?linkedListIndexed()?{
????????List?linkedList?=?new?LinkedList<>();
????????for?(int?i?=?0;?i?10000;?i++)?{
????????????linkedList.add(i);
????????}
????????//記錄開(kāi)始時(shí)間
????????long?startTime?=?System.currentTimeMillis();
????????for?(int?i?=?0;?i?????????????linkedList.get(i);
????????}
????????//記錄結(jié)束時(shí)間
????????long?endTime?=?System.currentTimeMillis();
????????//遍歷消耗時(shí)間
????????long?resultTime?=?endTime?-?startTime;
????????return?resultTime;
????}
????//測(cè)試LinkedList通過(guò)iterator遍歷所消耗時(shí)間
????public?static?long?linkedListIterator()?{
????????List?linkedList?=?new?LinkedList<>();
????????for?(int?i?=?0;?i?10000;?i++)?{
????????????linkedList.add(i);
????????}
????????//記錄開(kāi)始時(shí)間
????????long?startTime?=?System.currentTimeMillis();
????????Iterator?iterator?=?linkedList.iterator();
????????while?(iterator.hasNext())?{
????????????iterator.next();
????????}
????????//記錄結(jié)束時(shí)間
????????long?endTime?=?System.currentTimeMillis();
????????//遍歷消耗時(shí)間
????????long?resultTime?=?endTime?-?startTime;
????????return?resultTime;
????}
}
測(cè)試結(jié)果如下
測(cè)試ArrayList通過(guò)for遍歷所消耗時(shí)間：1
測(cè)試ArrayList通過(guò)iterator遍歷所消耗時(shí)間：2
測(cè)試LinkedList通過(guò)for遍歷所消耗時(shí)間：47
測(cè)試LinkedList通過(guò)iterator遍歷所消耗時(shí)間：1
我們來(lái)分析一下測(cè)試結(jié)果：ArrayList通過(guò)for遍歷比通過(guò)iterator遍歷要稍快，LinkedList通過(guò)iterator遍歷比通過(guò)for遍歷要快。
所以說(shuō)在我們的應(yīng)用中，要考慮使用List接口的哪種實(shí)現(xiàn)類，可以更好更高效的滿足實(shí)際場(chǎng)景需求。所以在這里通過(guò)實(shí)現(xiàn)RandomAccess接口來(lái)區(qū)分List的哪種實(shí)現(xiàn)類。
總結(jié)
最后總結(jié)一句話：實(shí)現(xiàn)RandomAccess接口的List可以通過(guò)for循環(huán)來(lái)遍歷數(shù)據(jù)比使用iterator遍歷數(shù)據(jù)更高效，未實(shí)現(xiàn)RandomAccess接口的List可以通過(guò)iterator遍歷數(shù)據(jù)比使用for循環(huán)來(lái)遍歷數(shù)據(jù)更高效。
往期推薦
歡迎加入我的知識(shí)星球，聊技術(shù)、說(shuō)職場(chǎng)、侃社會(huì)。
