在 RandomAccess 标记接口(interface)描述中写道:
* <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.
在集合类 synchronizedList 方法中，检查 RandomAccess，如果成功则创建 SynchronizedRandomAccessList 对象，但它们也没有关于算法的详细信息。
public static <T> List<T> synchronizedList(List<T> list) {
return (list instanceof RandomAccess ?
new SynchronizedRandomAccessList<T>(list) :
new SynchronizedList<T>(list));
}
这个算法什么时候适用以及在哪里(它是 native 代码)？
最佳答案
其中一个示例是 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);
}
此处不同的二进制搜索算法实现用于随机访问和顺序访问列表。代码是一个实现细节，但在这里区分列表是合理的。
如 documenation for Collections.binarySearch 中所述:
This method runs in log(n) time for a "random access" list (which provides near-constant-time positional access). If the specified list does not implement the RandomAccess interface and is large, this method will do an iterator-based binary search that performs O(n) link traversals and O(log n) element comparisons.
关于java - 何时应用操纵随机访问列表的算法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15356535/