對啊我就是認定你不知道ArrayList為什麼要實現RandomAccess接口

本文轉載自【微信公眾號：java進階架構師，ID:java_jiagoushi】經微信公眾號授權轉載，如需轉載與原文作者聯繫

在我們的開發中，List接口是最常見不過，而且我們幾乎每天都在用ArrayList或者LinkedList，但是細心的同學有沒有發現，ArrayList中實現了RandomAccess接口，而LinkedList卻沒有實現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是一個標記接口，官方解釋是只要List實現這個接口，就能支持快速隨機訪問。而什麼是隨機訪問呢？接下來我們來舉例說明。

Collections是集合的一個工具類，我們看一下Collections源碼中的二分搜索方法。

public static <T>int binarySearch(List<? extends Comparable<? super T>> list, T key) { if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD) return Collections.indexedBinarySearch(list, key); else return Collections.iteratorBinarySearch(list, key); }

在源碼中可以看出，判斷list是否是RandomAccess的實例，如果是，則執行indexedBinarySearch方法，如果不是，則執行iteratorBinarySearch方法。接下來看一下這兩個方法。

private static <T>int indexedBinarySearch(List<? extends Comparable<? super T>> list, T key) {int low = 0; int high = list.size()-1; while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super 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 <T>int iteratorBinarySearch(List<? extends Comparable<? super T>> list, T key){int low = 0; int high = list.size()-1; ListIterator<? extends Comparable<? super T>> i = list.listIterator(); while (low <= high) { int mid = (low + high) >>> 1; Comparable<? super 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}

上述兩個方法的源碼表示，實現了RandomAccess接口的List使用索引遍歷，而未實現RandomAccess接口的List使用迭代器遍歷。那麼為什麼要這麼設計呢？既然涉及到二分搜索的遍歷操作，那麼現在我們來分析一下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("測試ArrayList通過for遍歷所消耗時間：" + arrayListIndexedTime); System.out.println("測試ArrayList通過iterator遍歷所消耗時間：" + arrayListIteratorTime); System.out.println("測試LinkedList通過for遍歷所消耗時間：" + linkedListIndexedTime); System.out.println("測試LinkedList通過iterator遍歷所消耗時間：" + linkedListIteratorTime); } //測試ArrayList通過for遍歷所消耗時間 public static long arrayListIndexed() { List<Integer> arrayList = new ArrayList<>(); for (int i = 0; i < 10000; i++) { arrayList.add(i); } //記錄開始時間 long startTime = System.currentTimeMillis(); for (int i = 0; i < arrayList.size(); i++) { arrayList.get(i); } //記錄結束時間 long endTime = System.currentTimeMillis(); //遍歷消耗時間 long resultTime = endTime - startTime; return resultTime; } //測試ArrayList通過iterator遍歷所消耗時間 public static long arrayListIterator() { List<Integer> arrayList = new ArrayList<>(); for (int i = 0; i < 10000; i++) { arrayList.add(i); } //記錄開始時間 long startTime = System.currentTimeMillis(); Iterator<Integer> iterator = arrayList.iterator(); while (iterator.hasNext()) { iterator.next(); } //記錄結束時間 long endTime = System.currentTimeMillis(); //遍歷消耗時間 long resultTime = endTime - startTime; return resultTime; } //測試LinkedList通過for遍歷所消耗時間 public static long linkedListIndexed() { List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 10000; i++) { linkedList.add(i); } //記錄開始時間 long startTime = System.currentTimeMillis(); for (int i = 0; i < linkedList.size(); i++) { linkedList.get(i); } //記錄結束時間 long endTime = System.currentTimeMillis(); //遍歷消耗時間 long resultTime = endTime - startTime; return resultTime; } //測試LinkedList通過iterator遍歷所消耗時間 public static long linkedListIterator() { List<Integer> linkedList = new LinkedList<>(); for (int i = 0; i < 10000; i++) { linkedList.add(i); } //記錄開始時間 long startTime = System.currentTimeMillis(); Iterator<Integer> iterator = linkedList.iterator(); while (iterator.hasNext()) { iterator.next(); } //記錄結束時間 long endTime = System.currentTimeMillis(); //遍歷消耗時間 long resultTime = endTime - startTime; return resultTime; }}

測試結果如下

測試ArrayList通過for遍歷所消耗時間：1測試ArrayList通過iterator遍歷所消耗時間：2測試LinkedList通過for遍歷所消耗時間：47測試LinkedList通過iterator遍歷所消耗時間：1

我們來分析一下測試結果：ArrayList通過for遍歷比通過iterator遍歷要稍快，LinkedList通過iterator遍歷比通過for遍歷要快。

所以說在我們的應用中，要考慮使用List接口的哪種實現類，可以更好更高效地滿足實際場景需求。所以在這裡通過實現RandomAccess接口來區分List的哪種實現類。

總結

最後總結一句話：實現RandomAccess接口的List可以通過for循環來遍歷數據比使用iterator遍歷數據更高效，未實現RandomAccess接口的List可以通過iterator遍歷數據比使用for循環來遍歷數據更高效。