¿Por qué LinkedHashMap no proporciona acceso por índice?

De 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.¿Por qué LinkedHashMap no proporciona acceso por índice?

Si es así, entonces ¿por qué no se proporciona acceso a objetos como la Lista de java, list.get (índice);

ACTUALIZACIÓN

había implementado LRU caché utilizando LinkedHashMap. Mi algoritmo requería que tuviera acceso a LRU Object desde el caché. Es por eso que requería acceso aleatorio, pero creo que eso me costará un mal rendimiento, así que cambié la lógica y estoy accediendo al objeto LRU justo cuando el caché está lleno ... usando removeEldestEntry()

Gracias a todos. ..

Fuente

2011-04-14 Eternal Noob

a) Debido a que las entradas están vinculadas, no son accesibles al azar. El rendimiento sería miserable, O(N) si no me equivoco.

b) Porque no hay una interfaz para hacer una copia de seguridad de esta funcionalidad. Así que la elección sería la de cualquiera de introducir una interfaz dedicada sólo para esto (mal desempeño) Implantación o requieren clientes para programar contra las clases de implementación en lugar de interfaces

BTW con Guava hay una solución simple para usted:

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

Y para el almacenamiento en caché mira en Guava MapMaker y sus características de caducidad.

Fuente

2011-04-14 17:04:50

Gracias Sean. Estoy usando LinkedHashMap para implementar LRU Cache ... y quería alguna funcionalidad para mirar el objeto LRU ... pero supongo que iterar sobre el mapa sería muy mal rendimiento ... ¿Conoces alguna otra estructura de datos para dicha funcionalidad? –

+1, buena respuesta. Sin embargo, cabe señalar que no sería peor que el rendimiento proporcionado por, digamos, 'LinkedList', por lo que realmente no veo el argumento. – aioobe

@Eternal Noob, dice en los documentos: * Este tipo de mapa es muy adecuado para crear cachés LRU. *, Y, * iterar * sobre el mapa es tan eficiente como se obtiene (O (n)) – aioobe

Proporciona una interfaz Iterator, cada nodo de la lista está vinculado al anterior y posterior. Tener un método get(i) no sería diferente de iterar sobre todos los elementos en la lista ya que no hay una matriz de respaldo (igual que LinkedList).

Si necesita esta capacidad, que no es de buen calidad Sugiero que se extiende el mapa mismo

Fuente

2011-04-14 17:06:00 Asaf

Entonces, en la lista enlazada, cada vez que accedemos al último elemento, list.get (list.size() - 1), ¿es un acceso aleatorio o O (n) (todos los elementos son iterado)? –

'Proporciona una interfaz Iterator' que no es correcta. El conjunto de entradas del mapa() proporciona el iterador, no el mapa en sí (pero aparte de eso tienes razón) –

favor, eche un vistazo a Apache Commons LinkedMap

Fuente

2011-04-14 17:12:06

Es bueno conocer estas colecciones personalizadas, pero rara vez son útiles. Si los necesita, generalmente tiene un error de diseño en su código en alguna parte :-) –

Mientras pesca en Apache commons, para obtener un mapa, intente LRUMap. –

Desde values() proporciona una colección de respaldo de los valores, se puede resolver como esto:

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

Tal vez no sea muy eficiente (especialmente la memoria a gota), pero debe ser O(N) tal como lo haría esperar que sea.

Por cierto, creo que la pregunta es legítima para todos los List operaciones. (No debe ser más lento que LinkedList de todos modos, ¿verdad?)

me propuse hacer un LinkedHashMapList que se extendió el LinkedHashMap e implementa la interfaz List. Sorprendentemente, parece imposible de hacer, debido al choque para eliminar. El método remove existente devuelve el objeto previamente correlacionado, mientras que el List.remove debe devolver un boolean.

Eso es solo un reflejo, y sinceramente, también me resulta molesto que el LinkedHashMap no se pueda tratar más como un LinkedList.

Fuente

2011-04-14 17:20:33 aioobe

ya, también lo vi ... el método remove() para LinkedHashMap viene de HashMap, ya que LinkedHashMap extiende HashMap ... y eso está en conflicto con remove() de la Lista ... –

Si desea acceso aleatorio que puede hacer

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];

Como se puede ver que el rendimiento es probable que sea muy pobre a menos que almacenar en caché el array entries.

Sin embargo, cuestionaría la necesidad.

Fuente

2011-04-14 17:22:04

No hay ningún problema real para hacer un Mapa con log (N) eficiencia de acceso por índice. Si usa un árbol rojo-negro y almacena para cada nodo la cantidad de elementos en el árbol que comienza en ese nodo, es posible escribir un método get (int index) que sea log (N).

Fuente

2015-12-18 13:30:10 user1707322

Esto no parece responder a la pregunta. –

¿Por qué LinkedHashMap no proporciona acceso por índice?

Respuesta

Cuestiones relacionadas