为什么LinkedHashMap不提供通过索引访问的功能？

Question

来自 Javadoc：
HashMap 和 LinkedList 实现 Map 接口，具有可预测的迭代顺序。这个实现与 HashMap 不同之处在于它维护了一个双向链表，链接着所有的条目。

如果是这样，为什么它不像 Java 中的 List 那样提供对象访问，比如 list.get(index);

更新

我使用 LinkedHashMap 实现了 LRU 缓存。我的算法需要我从缓存中访问 LRU 对象。因此我需要随机访问，但我觉得那会影响性能，所以我改变了逻辑，在 Cache 满时仅仅访问 LRU 对象...使用 removeEldestEntry()

谢谢大家...

- Eternal Noob

Answer 1

a) 由于这些条目是链接的，而不是随机可访问的。如果我没有错的话，性能会非常糟糕，O(N)。

b) 因为没有界面来支持此功能。所以选择要么引入一个专门的界面只为此（性能差）实现或要求客户端针对实现类而不是界面进行编程。

---

顺便说一句，使用 Guava，你有一个简单的解决方案：

Iterables.get(map.values(), offset);

对于缓存，请查看Guava的MapMaker和它的过期特性。

- Sean Patrick Floyd

---

谢谢Sean。我正在使用LinkedHashMap来实现LRU缓存...并且想要一些功能来查看LRU对象...但是我猜测遍历映射会非常影响性能...你知道其他可以实现这种功能的数据结构吗？ - Eternal Noob

+1，很好的回答。不过需要注意的是，这种性能并不比例如LinkedList提供的性能差，所以我真看不出争议在哪里。 - aioobe

@Eternal Noob，文档中说：这种类型的映射非常适合构建LRU缓存，而且遍历映射的效率是最高的（O(n)）。 - aioobe

@aioobe 这就是为什么 LinkedList 没有实现 RandomAccess 的原因。 - Sean Patrick Floyd

Answer 2

由于values()提供了值的后备集合，因此可以像这样解决：

map.values().remove(map.values().toArray()[index]);

也许不是很高效（尤其是在内存方面），但它应该是 O(N)，就像你所期望的一样。

---

顺便说一句，我认为这个问题适用于所有 List 操作。（它不应该比 LinkedList 更慢，对吧？）

我准备做一个扩展了 LinkedHashMap 并实现了 List 接口的 LinkedHashMapList。令人惊讶的是，由于删除方式冲突，似乎无法实现。现有的 remove 方法返回之前映射的对象，而 List.remove 应该返回一个 boolean。

那只是一种反思，老实说，我也觉得 LinkedHashMap 不能更像一个 LinkedList 有些让人恼火。

- aioobe

---

是的，我也看到了...LinkedHashMap 的 remove() 方法来自于 HashMap，因为 LinkedHashMap 继承了 HashMap...这与 List 的 remove() 方法产生了冲突... - Eternal Noob

Answer 3

如果您想要随机访问，可以这样做：

Map<K,V> map = new LinkedHashMap<K,V>();
Map.Entry<K,V>[] entries = (Map.Entry<K,V>[]) map.toArray(new Map.Entry[map.size()]);
Map.Entry<K,V> entry_n = entry[n];

正如您所见，如果不缓存entries数组，性能很可能非常差。

然而，我会质疑是否有必要这样做。

- Peter Lawrey

Answer 4

它提供了一个“迭代器”接口，列表中的每个节点都链接到其前面和后面的节点。拥有一个“get(i)”方法与遍历列表中所有元素没有什么不同，因为没有支持数组（与LinkedList相同）。

如果您需要这种能力，但性能不佳，我建议您自己扩展映射。

- Asaf

---

在链表中，每当我们访问最后一个元素时，list.get(list.size()-1)，这是随机访问还是O(n)（所有元素都被迭代）？ - Eternal Noob

“它提供了一个迭代器接口”，这是不正确的。地图的entrySet()提供了迭代器，而不是Map本身（但除此之外你是正确的）。 - Sean Patrick Floyd

@EternalNoob 这是一个旧评论，但对于未来的读者来说，回答你的旧问题是值得的：LinkedList 知道它的大小，并且在访问高于列表一半的元素索引时会向后迭代。因此，访问最后一个元素与访问第一个元素一样便宜。只有中间的元素需要迭代费用。 - Holger

Answer 5

使用红黑树并为每个节点存储从该节点开始的树中元素数量，可以实现具有log(N)索引访问效率的Map。这样就可以编写一个get(int index)方法，其时间复杂度为log(N)，因此没有真正的问题。

- user1707322

---

这似乎并没有回答问题。 - Neil Masson