爲什麼LinkedHashMap不提供按索引訪問？

從的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.爲什麼LinkedHashMap不提供按索引訪問？

如果是這樣，那麼爲什麼沒有提供像在Java中， list.get（指數）列出對象訪問;

UPDATE

我一直在使用LinkedHashMap實現LRU緩存。我的算法要求我從緩存中訪問LRU對象。這就是爲什麼我需要隨機訪問，但我認爲這會損失我的糟糕的性能，所以我改變了邏輯，並且當緩存滿時訪問LRU對象...使用removeEldestEntry（）

謝謝大家。 ..

來源

2011-04-14 Eternal Noob

一個）由於條目被鏈接，而不是隨機訪問的。如果我沒有錯誤，性能會很糟糕，O(N)。

b）中因爲沒有界面備份此功能。因此，選擇是要麼引進的專用接口只爲這（性能糟糕的）實施或要求客戶端程序對實現類，而不是接口

順便說一句與Guava有你一個簡單的辦法：

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

而對於緩存看看番石榴的MapMaker和它的到期功能。

來源

2011-04-14 17:04:50

謝謝肖恩。我正在使用LinkedHashMap來實現LRU緩存......並且希望有一些功能來查看LRU對象......但是我猜測迭代映射將會是非常糟糕的表現......您是否知道用於此類功能的任何其他數據結構？ – 2011-04-14 17:21:30

+1，很好的答案。然而，應該指出的是，它不會比由'LinkedList'提供的性能差，所以我沒有真正看到這個論點。 – aioobe 2011-04-14 17:22:05

@Eternal菜鳥，它說在docs：*這種地圖是非常適合於構建LRU緩存*和*，*迭代在地圖上是有效的，因爲它得到（O（n））的 – aioobe 2011-04-14 17:39:50

它提供了一個接口Iterator，列表中的每個節點被鏈接到之前和之後的一個。具有get(i)方法不會比在列表中的所有元素進行迭代，因爲沒有背襯陣列（同LinkedList）不同。

如果你需要這種能力是不是很高性能的，我建議擴大地圖自己

來源

2011-04-14 17:06:00 Asaf

所以，鏈表，當我們進入最後一個元素，list.get（則爲list.size（） - 1），它是一個隨機存取或O（n）的（所有元素都迭代）？ – 2011-04-14 17:10:37

它提供了一個不正確的Iterator接口。該地圖的的entrySet（）提供了迭代器，而不是地圖本身（但除此之外，你是對的） – 2011-04-14 17:11:17

請看看Apache Commons LinkedMap

來源

2011-04-14 17:12:06

很高興知道這些自定義集合，但他們很少有用。如果你需要的時候，你通常有一個設計缺陷在你的代碼某處:-) – 2011-04-14 17:13:41

當你周圍阿帕奇百科全書釣魚，一個LRU地圖，嘗試LRUMap。 – 2012-07-06 17:37:52

由於values()提供值的後盾集合，你可以解決它像這樣的：

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

也許不是很有效（尤其是內存明智），但它應該是O(N)就像你希望它是。

順便說一句，我認爲這個問題是正當的，所有的List操作。（這不應該是慢LinkedList無論如何，對不對？）

我着手做了LinkedHashMapList這延長了LinkedHashMap並實施了List接口。令人驚訝的是，由於刪除衝突，似乎不可能做到。現有remove方法返回先前映射對象，而List.remove應返回boolean。

這只是一個反映，說實話，我也覺得這惱人的是，LinkedHashMap無法治療更像是一個LinkedList。

來源

2011-04-14 17:20:33 aioobe

雅，我看到過...移除LinkedHashMap的（）方法是從HashMap的到來爲LinkedHashMap的擴展HashMap中......而這與列表的remove（）相沖突... – 2011-04-14 17:25:42

如果你想隨機訪問，你可以做

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-14 17:22:04

沒有使通過索引訪問日誌（N）效率的地圖真正的問題。如果使用紅黑樹併爲每個節點存儲從該節點開始的樹中元素的數量，則可以編寫log（N）的get（int index）方法。

來源

2015-12-18 13:30:10 user1707322

這似乎並沒有回答這個問題。 – 2015-12-18 13:40:22

爲什麼LinkedHashMap不提供按索引訪問？

回答

相關問題