12

来自 Javadoc：
Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

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

更新

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

谢谢你们...

4

6 回答 6

15

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

b)因为没有接口来备份这个功能。因此，选择是为这个（性能不佳的）实现引入一个专用接口，或者要求客户端针对实现类而不是接口进行编程

顺便说一句，Guava为您提供了一个简单的解决方案：

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

对于缓存，请查看 GuavaMapMaker及其过期功能。

于 2011-04-14T17:04:50.830 回答
7

由于values()提供了值的支持集合，您可以像这样解决它：

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

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

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

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

这只是一种反映，老实说，我也觉得LinkedHashMap不能像LinkedList.

于 2011-04-14T17:20:33.110 回答
3

请查看Apache Commons LinkedMap

于 2011-04-14T17:12:06.397 回答
1

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

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

于 2011-04-14T17:06:00.550 回答
1

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

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如您所见，除非您缓存阵列，否则性能可能很差。

然而，我会质疑它的必要性。

于 2011-04-14T17:22:04.527 回答
0

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

于 2015-12-18T13:30:10.767 回答