5

在 RandomAccess 标记接口描述中它是这样写的：

 * <p>The best algorithms for manipulating random access lists (such as
 * <tt>ArrayList</tt>) can produce quadratic behavior when applied to
 * sequential access lists (such as <tt>LinkedList</tt>).  Generic list
 * algorithms are encouraged to check whether the given list is an
 * <tt>instanceof</tt> this interface before applying an algorithm that would
 * provide poor performance if it were applied to a sequential access list,
 * and to alter their behavior if necessary to guarantee acceptable
 * performance.

在集合类 synchronisedList 方法中，检查 RandomAccess 并且如果成功创建 SynchronizedRandomAccessList 对象，但它们也没有关于算法的详细信息。

public static <T> List<T> synchronizedList(List<T> list) {
    return (list instanceof RandomAccess ?
                new SynchronizedRandomAccessList<T>(list) :
                new SynchronizedList<T>(list));
    }

该算法何时应用以及在哪里应用（它是本机代码）？

4

1 回答 1

4

其中一个例子是Collections.binarySearch：

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);
}

这里不同的二进制搜索算法实现用于随机访问和顺序访问列表。代码是一个实现细节，但在这里区分列表是合理的。

正如Collections.binarySearch的文档中指定的那样：

此方法在 log(n) 时间内针对“随机访问”列表（提供接近恒定时间的位置访问）运行。如果指定的列表没有实现 RandomAccess 接口并且很大，则此方法将执行基于迭代器的二进制搜索，执行 O(n) 链接遍历和 O(log n) 元素比较。

于 2013-03-12T08:45:41.447 回答