Почему LinkedHashMap не предоставляет доступ по индексу?

Question

Из 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.

Если это так, то почему он не обеспечивает доступ к объектам, как List в Java, list.get (индекс);

UPDATE

Я реализовал LRU Cache, используя LinkedHashMap. Мой алгоритм требовал от меня доступа к объекту LRU из кеша. Вот почему мне потребовался произвольный доступ, но я думаю, что это будет стоить мне плохой производительности, поэтому я изменил логику, и я получаю доступ к объекту LRU только тогда, когда Cache заполнен ... используя removeEldestEntry ()

Спасибо всем ...

Answer 1

а) Поскольку записи связаны, не доступны в случайном порядке. Производительность была бы жалкой, O(N), если я не ошибаюсь.

b) Поскольку нет интерфейса для резервного копирования этой функции. Поэтому выбор будет заключаться в том, чтобы либо ввести выделенный интерфейс только для этой (плохо работающей) реализации, либо потребовать, чтобы клиенты программировали с использованием классов реализации вместо интерфейсов

---

Кстати, с Гуава для вас есть простое решение:

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

А для кэширования посмотрите на MapMaker в Guava и его функциях истечения срока действия.

Answer 2

Поскольку values() предоставляет вспомогательный набор значений, вы можете решить его следующим образом:

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

Возможно, не очень эффективно (особенно в отношении памяти), но оно должно быть O(N) простокак и следовало ожидать.

---

Кстати, я думаю, что вопрос правомерен для всех операций List.(В любом случае, оно не должно быть медленнее, чем LinkedList, верно?)

Я решил сделать LinkedHashMapList, который расширил бы LinkedHashMap и реализовал интерфейс List.Удивительно, но это кажется невозможным из-за столкновения для удаления.Существующий метод remove возвращает ранее отображенный объект, в то время как List.remove должен возвращать boolean.

Это просто отражение, и, честно говоря, меня тоже раздражает, что LinkedHashMap может 'к нему больше относятся как LinkedList.

Answer 3

Пожалуйста, посмотрите на Apache Commons LinkedMap

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

Предоставляет интерфейс Iterator, каждый узел в списке связан с тем, который находится до и после него. Наличие метода get(i) ничем не отличается от итерации по всем элементам в списке, поскольку нет резервного массива (аналогично LinkedList).

Если вам нужна эта способность, которая не очень эффективна, я предлагаю расширить карту самостоятельно

Answer 6

Нет реальной проблемы сделать Map с log (N) эффективностью доступа по индексу.Если вы используете красно-черное дерево и сохраняете для каждого узла количество элементов в дереве, начиная с этого узла, можно написать метод get (int index), который является log (N).