java 为什么 LinkedHashMap 不提供按索引访问？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5666820/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Why doesn't LinkedHashMap provide access by index?
提问by Eternal Noob
From 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.
来自 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.
If it is so, then why doesn't it provide object access like List in java, list.get(index);
如果是这样，那它为什么不提供像java中的List这样的对象访问，list.get(index);
UPDATE
更新
I had implemented LRU Cache using LinkedHashMap. My algorithm required me to access LRU Object from the cache. That's why I required random access, but I think that will cost me bad performance, so I have changed the logic and I am accessing the LRU object just when Cache is full...using removeEldestEntry()
我已经使用 LinkedHashMap 实现了 LRU 缓存。我的算法要求我从缓存中访问 LRU 对象。这就是为什么我需要随机访问的原因，但我认为这会降低我的性能，所以我改变了逻辑，并且在缓存已满时访问 LRU 对象......使用 removeEldestEntry()
Thank you all...
谢谢你们...
回答by Sean Patrick Floyd
a)Because the entries are linked, not randomly accessible. The performance would be miserable, O(N)if I'm not in error.
a)因为条目是链接的，不能随机访问。O(N)如果我没有记错的话，表演会很糟糕。
b)Because there is no interface to back up this functionality. So the choice would be to either introduce a dedicated interface just for this (badly performing) Implementation or require clients to program against implementation classes instead of interfaces
b)因为没有接口来备份这个功能。因此，选择是要么为此（性能不佳的）实现引入专用接口，要么要求客户端针对实现类而不是接口进行编程
Btw with Guavathere's a simple solution for you:
顺便说一句，使用番石榴有一个简单的解决方案：
Iterables.get(map.values(), offset);
And for caching look at Guava's MapMakerand it's expiration features.
对于缓存，请查看 GuavaMapMaker及其过期功能。
回答by aioobe
Since values()provides a backing collection of the values, you can solve it like this:
由于values()提供了值的支持集合，您可以像这样解决它：
map.values().remove(map.values().toArray()[index]);
Perhaps not very efficient (especially memory-wise), but it should be O(N)just as you would expect it to be.
也许效率不高（尤其是在内存方面），但它应该O(N)正如您所期望的那样。
Btw, I think the question is legitimate for all Listoperations. (It shouldn't be slower than LinkedListanyway, right?)
顺便说一句，我认为这个问题对所有List操作都是合理的。（它不应该比LinkedList任何时候都慢，对吧？）
I set out to do a LinkedHashMapListwhich extended the LinkedHashMapand implemented the Listinterface. Surprisingly it seems impossible to do, due to the clash for remove. The existing removemethod returns the previously mapped object, while the List.removeshould return a boolean.
我着手做一个LinkedHashMapList扩展LinkedHashMap并实现了List接口的工作。令人惊讶的是，由于删除冲突，这似乎是不可能的。现有的remove方法返回之前映射的对象，而List.remove应该返回一个boolean.
That's just a reflection, and honestly, I also find it annoying that the LinkedHashMapcan't be treated more like a LinkedList.
这只是一种反思，老实说，我也觉得LinkedHashMap不能像LinkedList.
回答by Piyush Mattoo
Please take a look at Apache Commons LinkedMap
回答by Asaf
It provides an Iteratorinterface, each node in the list is linked to the one before it and after it. Having a get(i)method would be no different than iterating over all the elements in the list since there is no backing array (same as LinkedList).
它提供了一个Iterator接口，列表中的每个节点都链接到它之前和之后的节点。拥有一个get(i)方法与迭代列表中的所有元素没有什么不同，因为没有后备数组（与 相同LinkedList）。
If you require this ability which isn't very performant I suggest extending the map yourself
如果您需要这种性能不佳的能力，我建议您自己扩展地图
回答by Peter Lawrey
If you want random access you can do
如果你想要随机访问，你可以做
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];
As you can see the performance is likely to be very poor unless you cache the entriesarray.
如您所见，除非您缓存entries阵列，否则性能可能会很差。
I would question the need for it however.
然而，我会质疑它的必要性。
回答by user1707322
There is no real problem to make a Map with log(N) efficiency of access by index. If you use a red-black tree and store for each node the number of elements in the tree starting at that node it is possible to write a get(int index) method that is log(N).
使用索引访问的 log(N) 效率制作 Map 没有实际问题。如果您使用红黑树并为每个节点存储树中从该节点开始的元素数，则可以编写 log(N) 的 get(int index) 方法。
