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

От Джавадока:
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 заполнен... using removeEldestEntry()

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

Ответы

Ответ 1

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

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

Btw с Guava есть простое решение для вас:

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

И для кэширования посмотрите на Guava MapMaker и его возможности истечения срока действия.

Ответ 2

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

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

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

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

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

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

Ответ 4

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

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

Ответ 5

Если вам нужен произвольный доступ, вы можете сделать

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.

Я бы поставил под сомнение его необходимость.

Ответ 6

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