二分查找之RandomAccess的作用

二分查找之RandomAccess的作用

在Java集合里，大致分为以数组为基础的随机访问数据结构和以链表为基础的链式访问（不随机）数据结构。

例如，使用java.util.Collections#binarySearch(java.util.List<? extends java.lang.Comparable<? super T>>, T)进行二分查找时（前提是保证升序，否则使用带有比较器的二分查找方法）是不是RandomAccess的List就有了实现区别。如果不了解二分查找请看这里。这里以集合元素可比较（实现java.lang.Comparable接口）为例，带有比较器的查找方法大体一致，查找方法为java.util.Collections#binarySearch(java.util.List<? extends T>, T, java.util.Comparator<? super T>)。

看源码所知，查找之前先判断List是否可以RandomAccess（或者判断集合大小，不足5000时也走随机访问），如图：

1、如果是java.util.ArrayList或者java.util.Arrays.ArrayList等实现RandomAccess的List，那么就进行数组访问方式的二分查找

2、如果是java.util.LinkedList等通过链表访问的List，就进行java.util.ListIterator双向迭代器访问，

其中get方法为双向游标获取元素

3、另外，在java.util.Collections集合工具类中有很多静态方法和静态内部类，包含

java.util.Collections.CheckedList未实现RandomAccess随机访问；

java.util.Collections.CopiesList实现RandomAccess随机访问；

java.util.Collections.EmptyList实现RandomAccess随机访问；

java.util.Collections.SingletonList实现RandomAccess随机访问；

java.util.Collections.SynchronizedList未实现RandomAccess随机访问；

java.util.Collections.SynchronizedRandomAccessList实现RandomAccess随机访问；

java.util.Collections.UnmodifiableList未实现RandomAccess随机访问。