小白學Java：奇怪的RandomAccess
- RandomAccess是個啥
- forLoop與Iterator的差別
- 判斷是否為RandomAccess

小白學Java：奇怪的RandomAccess

我們之前在分析那三個集合源碼的時候，曾經說到：ArrayList和Vector繼承了

RandomAccess

接口，但是LinkedList并沒有，我們還知道繼承了這個接口，就意味着其中元素支援快速随機通路（fast random access）。

RandomAccess是個啥

出于好奇，我特意去檢視了RandomAccess的官方文檔，讓我覺得異常驚訝的是！這個接口中啥也沒有！是真的奇怪！（事實上和它類似的還有

Cloneable

和

java.io.Serializable

，這倆之後會探讨）隻留下一串冰冷的英文。

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

哎，不管他，翻譯就完事了,今天的生活也是鬥志滿滿的搬運工生活呢！

我用我自己的語言組織一下：

它是個啥呢？這個接口本身隻是一個标記接口，是以沒有方法也是情有可原的。
标記啥呢？它用來作為List接口的實作類們是否支援快速随機通路的标志，這樣的通路通常隻需要常數的時間。
為了啥呢？在通路清單時，根據它們是否是RandomAccess的标記，來選擇通路他們的方法以提升性能。

我們知道，ArrayList和Vector底層基于數組實作，記憶體中占據連續的存儲空間，每個元素的下标其實是偏移首位址的偏移量，這樣子查詢元素隻需要根據：元素位址 = 首位址+(元素長度*下标），就可以迅速完成查詢，通常隻需要花費常數的時間，是以它們理應實作該接口。但是連結清單不同，連結清單依據不同節點之間的位址互相引用完成聯系，本身不要求位址連續，查詢的時候需要周遊的過程，這樣子會導緻，在資料量比較大的時候，查詢元素消耗的時間會很長。

RandomAccess接口的所有實作類：

ArrayList, AttributeList, CopyOnWriteArrayList, RoleList, RoleUnresolvedList, Stack, Vector

the given list is an instanceof this interface before applying an algorithm that would provide poor performance if it were applied to a sequential access list, and to alter their behavior if necessary to guarantee acceptable performance.

可以通過

xxList instanceof RandomAccess)

判斷該清單是否為該接口的執行個體，如果是順序通路的清單（如LinkedList），就不應該通過下标索引的方式去查詢其中的元素，這樣效率會很低。

/*for循環周遊*/
for (int i=0, n=list.size(); i < n; i++)
    list.get(i);
/*Iterator周遊*/
for (Iterator i=list.iterator(); i.hasNext();)
    i.next();

對于實作RandomAccess接口，支援快速随機通路的清單來說,for循環+下标索引周遊的方式比疊代器周遊的方式要更快。

forLoop與Iterator的差別

對此，我們是否可以猜想，如果是LinkedList這樣并不支援随即快速通路的清單，是否是Iterator更快呢？于是我們進行一波嘗試：

定義關于for循環和Iterator的測試方法

/*for循環周遊的測試*/
    public static void forTest(List list){
        long start = System.currentTimeMillis();
        for (int i = 0,n=list.size(); i < n; i++) {
            list.get(i);
        }
        long end = System.currentTimeMillis();
        long time = end - start;
        System.out.println(list.getClass()+" for循環周遊測試 cost:"+time);
    }
    /*Iterator周遊的測試*/
    public static void iteratorTest(List list){
        long start = System.currentTimeMillis();
        Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            iterator.next();
        }
        long end = System.currentTimeMillis();
        long time = end-start;
        System.out.println(list.getClass()+"疊代器周遊測試 cost:"+time);
    }

測試如下

public static void main(String[] args) {    
        List<Integer> linkedList = new LinkedList<>();
        List<Integer> arrayList = new ArrayList<>();
        /*ArrayList不得不加大數量觀察它們的差別，其實差别不大*/
        for (int i = 0; i < 5000000; i++) {
            arrayList.add(i);
        }
        /*LinkedList 這個量級就可以展現比較明顯的差別*/
        for(int i = 0;i<50000;i++){
            linkedList.add(i);
        }
        /*方法調用*/
        forTest(arrayList);
        iteratorTest(arrayList);
        forTest(linkedList);
        iteratorTest(linkedList);
    }

測試效果想當的明顯

小白學Java：奇怪的RandomAccess小白學Java：奇怪的RandomAccess

我們可以發現：

對于支援随機通路的清單（如ArrayList），for循環＋下标索引的方式和疊代器循環周遊的方式通路數組元素，差别不是很大，在加大數量時，for循環周遊的方式更快一些。
對于不支援随機通路的清單（如LinkedList），兩種方式就相當明顯了，用for循環＋下标索引是相當的慢，因為其每個元素存儲的位址并不連續。
綜上，如果清單并不支援快速随機通路，通路其元素時，建議使用疊代器；若支援，則可以使用for循環+下标索引。

判斷是否為RandomAccess

上面也提到了，這個空空的接口就是承擔着标記的職責（Marker），标記着是否支援随機快速通路，如果不支援的話，還使用索引來周遊的話，效率相當之低。既然有标記，那我們一定有方法去區分标記。這時，我們需要使用

instanceof

關鍵字幫助我們做區分，以選擇正确的通路方式。

public static void display(List<?> list){
    if(list instanceof RandomAccess){
        //如果支援快速随機通路
        forTest(list);
    }else {
        //不支援快速随機通路，就用疊代器
        iteratorTest(list);
    }
}

再進行一波測試看看，他倆都找到了自己的歸宿：

小白學Java：奇怪的RandomAccess小白學Java：奇怪的RandomAccess

事實上，集合工具類

Collections

中有許多操作集合的方法，我們随便舉一個從前往後填充集合的方法：

public static <T> void fill(List<? super T> list, T obj) {
        int size = list.size();
            
        if (size < FILL_THRESHOLD || list instanceof RandomAccess) {
            //for周遊
            for (int i=0; i<size; i++)
                list.set(i, obj);
        } else {
            //疊代器周遊
            ListIterator<? super T> itr = list.listIterator();
            for (int i=0; i<size; i++) {
                itr.next();
                itr.set(obj);
            }
        }
    }

還有許多這樣的方法，裡面有許多值得學習的地方。我是一個正在學習Java的小白，也許我的知識還未有深度，但是我會努力把自己學習到的做一個體面的總結。對了，如果文章有了解錯誤，或叙述不清之處，還望大家評論區批評指正。

參考資料：JDK1.8官方文檔