题 图:pexels
出 处:https://dwz.cn/aqL14tuI
预 计 阅 读 时 间:5.99分钟
在我们的开发中,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 方法。** 接下来看一下这两个方法。
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);
}
}
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 循环来遍历数据更高效。
-END-