作者:蔡先森_caiyq
www.jianshu.com/p/3e2a9e4c9e01
在我们的开发中,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是一个标记接口,官方解释是只要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循环来遍历数据更高效。
推荐阅读(点击即可跳转阅读)
1. SpringBoot内容聚合
2. 面试题内容聚合
3. 设计模式内容聚合
4. Mybatis内容聚合
5. 多线程内容聚合