为什么 LinkedHashMap 不提供索引访问？

Question

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

如果是这样，那么为什么它不提供像 java 中的 List 那样的对象访问， 列表.get(索引);

更新

我使用 LinkedHashMap 实现了 LRU 缓存。我的算法要求我从缓存中访问 LRU 对象。这就是为什么我需要随机访问，但我认为这会降低我的性能，所以我改变了逻辑，我在缓存已满时访问LRU对象...使用removeEldestEntry()

谢谢大家...

Answer 1

a) 因为条目是链接的，不能随机访问。如果我没有出错的话，性能会很糟糕，O(N)。

b) 因为没有接口来支持此功能。因此，选择要么为此（性能不佳）实现引入专用接口，要么要求客户端针对实现类进行编程，而不是

---

使用 Guava 为您提供了一个简单的解决方案：

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

对于缓存，请查看 Guava 的 MapMaker 及其过期功能。

Answer 2

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

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

也许不是很有效（尤其是内存方面），但它应该是 O(N) code> 正如您所期望的那样。

---

顺便说一句，我认为这个问题对于所有 List 操作都是合法的。 （无论如何，它不应该比 LinkedList 慢，对吧？）

我开始做一个 LinkedHashMapList ，它扩展了 LinkedHashMap 并实现了 <代码>列表接口。令人惊讶的是，由于删除冲突，这似乎不可能做到。现有的 remove 方法返回先前映射的对象，而 List.remove 应返回一个 boolean。

这只是一种反映，老实说，我还发现不能将 LinkedHashMap 视为更像 LinkedList ，这很烦人。

Answer 3

它提供了一个Iterator接口，列表中的每个节点都链接到它之前和之后的节点。使用 get(i) 方法与迭代列表中的所有元素没有什么不同，因为没有后备数组（与 LinkedList 相同）。

如果您需要这种性能不是很好的功能，我建议您自己扩展地图

Answer 4

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

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 数组，否则性能可能会很差。

但我会质疑这样做的必要性。

Answer 5

制作一个索引访问效率为 log(N) 的 Map 并没有什么实际问题。如果您使用红黑树并为每个节点存储从该节点开始的树中的元素数量，则可以编写一个 get(int index) 方法，即 log(N)。