根据javadoc上面的的解释是:
RandomAccess 是一个标记接口,用于标明实现该接口的List支持快速随机访问,主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。
我们可以简单的看下Collections下的binarySearch方法的源码:
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c) {
if (c==null)
return binarySearch((List<? extends Comparable<? super T>>) list, key);
if (list instanceof RandomAccess || list.size()<BINARYSEARCH_THRESHOLD)
return Collections.indexedBinarySearch(list, key, c);
else
return Collections.iteratorBinarySearch(list, key, c);
从源码中我们可以看到,在进行二分查找的时候,list会先判断是否是RandomAccess也即是否实现了RandomAccess接口,接着在调用想用的二分查找算法来进行,(其中: BINARYSEARCH_THRESHOLD Collections的一个常量(5000),它是二分查找的阀值。)如果实现了RandomAccess接口的List,执行indexedBinarySearch方法,否则执行 iteratorBinarySearch方法。
分别看下这两个方法的实现:
一、indexedBinarySearch 方法:[java] view p
private static <T> int indexedBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
int low = 0;
int high = l.size()-1;
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = l.get(mid);
int cmp = c.compare(midVal, 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
}
indexedBinarySearch 方法是直接通过get来访问元素
Arraylist 的get方法:
public E get(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
return (E) elementData[index];
}
elementData 是数组,可以直接索引快速找到
二、iteratorBinarySearch方法:
private static <T> int iteratorBinarySearch(List<? extends T> l, T key, Comparator<? super T> c) {
int low = 0;
int high = l.size()-1;
ListIterator<? extends T> i = l.listIterator();
while (low <= high) {
int mid = (low + high) >>> 1;
T midVal = get(i, mid);
int cmp = c.compare(midVal, 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
}
iteratorBinarySearch中ListIterator来查找相应的元素
LinkedList get()方法:
checkElementIndex() 方法是检查是否角标越界,note(index)方法是查找方法,可以看出LinkedList是双链表结构
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
总之:RandomAccess 是一个标记接口,用于标明实现该接口的List支持快速随机访问,主要目的是使算法能够在随机和顺序访问的list中表现的更加高效。