java - 为什么 RandomAccess 不在列表层次结构中？

Question

RandomAccess是 List 使用的 Java 标记接口(interface)实现表明他们可以快速随机访问他们的元素。由于它是专门为 List 设计的实现，为什么不在 List 中等级制度？例如，考虑以下需要 RandomAccess 的方法列表作为输入并返回一个随机元素:

public <E, L extends List<E> & RandomAccess> E getRandomElement(L list) {...}

我必须将匿名列表或声明类型为 ArrayList<E> 的列表传递给此方法，一个具体的类，而不是用像 List<E> 这样的接口(interface)声明的列表.但是，如果 RandomAccess参数化和扩展 List<E> ，那么我的方法可能如下所示:

public <E, L extends RandomAccess<E>> E getRandomElement(L list) {...}

我可以将一个声明类型为 RandomAccess<E> 的列表传递给它，这是一个接口(interface)，而不是一个具体的类。 ArrayList<E> etc 将执行 RandomAccess<E> , 而不是 List<E> .

Answer 1

我认为答案可能在 documentation 中RandomAccess(强调我的)。

Marker interface used by List implementations to indicate that they support fast (generally constant time) random access. The primary purpose of this interface is to allow generic algorithms to alter their behavior to provide good performance when applied to either random or sequential access lists.

The best algorithms for manipulating random access lists (such as ArrayList) can produce quadratic behavior when applied to sequential access lists (such as LinkedList). Generic list algorithms are encouraged to check whether the given list is an instanceof 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.

他们似乎并不打算为集合类层次结构增加额外的复杂性，而只是为算法提供优化机会。

这对我来说确实有些道理。算法的用户通常不需要关心实现细节。在实现 RandomAccess 的 List 上工作的每个算法也将在不这样做的 List 上工作。唯一的区别是性能。

考虑以下情况:

• 对于不提供有效随机访问的 List，没有办法重写算法以提高效率。 (或者还没有人愿意这样做。)在这种情况下，有一个缓慢的算法可能仍然比根本没有更好。如果用户经常需要该算法，则应切换到不同的 List 实现。
• 该算法可以用两种略有不同的方式重写，每种方式都能为支持和不支持高效随机访问的 List 产生最佳性能。在这里，用户通常更愿意简单地放入 List 并让算法决定使用哪个版本。如果使用重载决策而不是运行时类型自省(introspection)，则在处理抽象 List 类型时，用户可能会意外错过优化版本。让调用者每次都检查 List 是否是 instanceof RandomAccess 比在算法本身中执行一次要多。最后，如果一个算法后来被改进以支持两个版本，我们不需要去更改客户端代码。

因此，我认为他们这样做是为了积极地防止您希望使用的界面。当然，这种选择可能会对合法用途产生负面影响，但这似乎是一种合理的权衡。