JavaArrayList为什么要实现RandomAccess接口？

作者：红颜弹指老a刹那芳华_623 | 来源：互联网 | 2023-09-10 15:23

总结：ArrayList通过for遍历比通过iterator遍历要稍快，LinkedList通过iterator遍历比通过for遍历要快。所以说在我们

总结&＃xff1a;
ArrayList通过for遍历比通过iterator遍历要稍快&＃xff0c;LinkedList通过iterator遍历比通过for遍历要快。

所以说在我们的应用中&＃xff0c;要考虑使用List接口的哪种实现类&＃xff0c;可以更好更高效的满足实际场景需求。所以在这里通过实现RandomAccess接口来区分List的哪种实现类。

在我们的开发中&＃xff0c;List接口是最常见不过&＃xff0c;而且我们几乎每天都在用ArrayList或者LinkedList&＃xff0c;但是细心的同学有没有发现&＃xff0c;ArrayList中实现了RandomAccess接口&＃xff0c;而LinkedList却没有实现RandomAccess接口&＃xff0c;这是为什么呢&＃xff1f;

public class ArrayList extends AbstractListimplements List, RandomAccess, Cloneable, java.io.Serializable public class LinkedListextends AbstractSequentialListimplements List, Deque, Cloneable, java.io.Serializable

RandomAccess接口中是空的&＃xff0c;RandomAccess接口又是什么呢&＃xff1f;

public interface RandomAccess { }

RandomAccess接口

RandomAccess是一个标记接口&＃xff0c;官方解释是只要List实现这个接口&＃xff0c;就能支持快速随机访问。而什么是随机访问呢&＃xff1f;接下来我们来举例说明。
Collections是集合的一个工具类&＃xff0c;我们看一下Collections源码中的二分搜索方法。

public static int binarySearch(List> list, T key) {if (list instanceof RandomAccess || list.size()

在源码中可以看出&＃xff0c;判断list是否是RandomAccess的实例&＃xff0c;如果是&＃xff0c;则执行indexedBinarySearch方法&＃xff0c;如果不是&＃xff0c;则执行iteratorBinarySearch方法。接下来看一下这两个方法。

private static int indexedBinarySearch(List> list, T key) {int low &＃61; 0;int high &＃61; list.size()-1;

while (low <&＃61; high) {int mid &＃61; (low &＃43; high) >>> 1;Comparable midVal &＃61; list.get(mid);int cmp &＃61; midVal.compareTo(key);if (cmp <0)low &＃61; mid &＃43; 1;else if (cmp > 0)high &＃61; mid - 1;elsereturn mid; // key found } return -(low &＃43; 1); // key not found

}
private static
int iteratorBinarySearch(List> list, T key)
{
int low &＃61; 0;
int high &＃61; list.size()-1;
ListIterator> i &＃61; list.listIterator();

while (low <&＃61; high) {int mid &＃61; (low &＃43; high) >>> 1;Comparable midVal &＃61; get(i, mid);int cmp &＃61; midVal.compareTo(key);if (cmp <0)low &＃61; mid &＃43; 1;else if (cmp > 0)high &＃61; mid - 1;elsereturn mid; // key found } return -(low &＃43; 1); // key not found

}

上述两个方法的源码表示&＃xff0c;实现了RandomAccess接口的List使用索引遍历&＃xff0c;而未实现RandomAccess接口的List使用迭代器遍历。那么为什么要这么设计呢&＃xff1f;
既然涉及到二分搜索的遍历操作&＃xff0c;那么现在我们来分析一下ArrayList和LinkedList遍历元素的性能如何&＃xff1f;

public class CollectionTest {public static void main(String[] args){long arrayListIndexedTime &＃61; arrayListIndexed();long arrayListIteratorTime &＃61; arrayListIterator();long linkedListIndexedTime &＃61; linkedListIndexed();long linkedListIteratorTime &＃61; linkedListIterator();System.out.println("测试ArrayList通过for遍历所消耗时间&＃xff1a;" &＃43; arrayListIndexedTime);System.out.println("测试ArrayList通过iterator遍历所消耗时间&＃xff1a;" &＃43; arrayListIteratorTime);System.out.println("测试LinkedList通过for遍历所消耗时间&＃xff1a;" &＃43; linkedListIndexedTime);System.out.println("测试LinkedList通过iterator遍历所消耗时间&＃xff1a;" &＃43; linkedListIteratorTime);}

//测试ArrayList通过for遍历所消耗时间 public static long arrayListIndexed() {List arrayList &＃61; new ArrayList<>();for (int i &＃61; 0; i <10000; i&＃43;&＃43;) {arrayList.add(i);}//记录开始时间long startTime &＃61; System.currentTimeMillis();for (int i &＃61; 0; i }//测试ArrayList通过iterator遍历所消耗时间 public static long arrayListIterator() {List arrayList &＃61; new ArrayList<>();for (int i &＃61; 0; i <10000; i&＃43;&＃43;) {arrayList.add(i);}//记录开始时间long startTime &＃61; System.currentTimeMillis();Iterator iterator &＃61; arrayList.iterator();while (iterator.hasNext()) {iterator.next();}//记录结束时间long endTime &＃61; System.currentTimeMillis();//遍历消耗时间long resultTime &＃61; endTime - startTime;return resultTime; }//测试LinkedList通过for遍历所消耗时间 public static long linkedListIndexed() {List linkedList &＃61; new LinkedList<>();for (int i &＃61; 0; i <10000; i&＃43;&＃43;) {linkedList.add(i);}//记录开始时间long startTime &＃61; System.currentTimeMillis();for (int i &＃61; 0; i }//测试LinkedList通过iterator遍历所消耗时间 public static long linkedListIterator() {List linkedList &＃61; new LinkedList<>();for (int i &＃61; 0; i <10000; i&＃43;&＃43;) {linkedList.add(i);}//记录开始时间long startTime &＃61; System.currentTimeMillis();Iterator iterator &＃61; linkedList.iterator();while (iterator.hasNext()) {iterator.next();}//记录结束时间long endTime &＃61; System.currentTimeMillis();//遍历消耗时间long resultTime &＃61; endTime - startTime;return resultTime; }

}

测试结果如下

测试ArrayList通过for遍历所消耗时间&＃xff1a;1 测试ArrayList通过iterator遍历所消耗时间&＃xff1a;2 测试LinkedList通过for遍历所消耗时间&＃xff1a;47 测试LinkedList通过iterator遍历所消耗时间&＃xff1a;1

我们来分析一下测试结果&＃xff1a;ArrayList通过for遍历比通过iterator遍历要稍快&＃xff0c;LinkedList通过iterator遍历比通过for遍历要快。