Cuándo usar HashMap sobre LinkedList o ArrayList y viceversa

82

¿Cuál es la razón por la que no siempre podemos usar un HashMap, a pesar de que es mucho más eficiente que ArrayList o LinkedList en operaciones de agregar, eliminar, también independientemente del número de elementos?

Lo busqué en Google y encontré algunas razones, pero siempre había una solución para usar HashMap, con ventajas aún vivas.

java arrays arraylist linked-list hashmap
fuente
11
Listsy Mapsson dos estructuras de datos completamente diferentes, con operaciones e invariantes diferentes. ¿Puede explicar el contexto / los requisitos en los que está pensando dónde ambas serían soluciones aceptables?
Mark Peters
3
Aparentemente, nunca ha necesitado mantener un conjunto de cosas en un orden en particular ...
Brian Roach
52
Downvote, ¿por qué? Creo que esta es una pregunta adecuada. Sin embargo, muestra falta de conocimiento, pero la pregunta SO no debe ser rechazada por mostrar falta de conocimiento. De hecho, una pregunta siempre es el resultado de la falta de conocimiento.

Respuestas:

96

Las listas representan un orden secuencial de elementos. Los mapas se utilizan para representar una colección de pares clave / valor.

Si bien puede usar un mapa como lista, existen algunas desventajas definidas de hacerlo.

Mantener el orden: - Se ordena una lista por definición. Agrega elementos y luego puede volver a recorrer la lista en el orden en que insertó los elementos. Cuando agrega elementos a un HashMap, no se le garantiza recuperar los elementos en el mismo orden en que los puso. Hay subclases de HashMap como LinkedHashMap que mantendrán el orden, pero en general el orden no está garantizado con un Mapa.

Semántica de clave / valor: - El propósito de un mapa es almacenar elementos basados ​​en una clave que se puede utilizar para recuperar el elemento en un momento posterior. Una funcionalidad similar solo se puede lograr con una lista en el caso limitado de que la clave sea la posición en la lista.

Legibilidad del código Considere los siguientes ejemplos. 

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Funcionalidad de colección Algunas funciones de gran utilidad están disponibles para listas a través de la clase Colecciones. Por ejemplo ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);

Espero que esto ayude,

polster
fuente
A menudo se dice que las LinkedLists son malas debido a problemas de rendimiento. Con frecuencia uso LinkedLists sobre ArrayLists debido al orden de los elementos. ¿Sería mejor (para rendimiento y memoria) si usara HashMaps con posiciones como claves?
Cesar Castro
33

Las listas y los mapas son estructuras de datos diferentes. Los mapas se utilizan para cuando desea asociar una clave con un valor y las listas son una colección ordenada.

Map es una interfaz en Java Collection Framework y HashMap es una implementación de la interfaz Map. HashMap es eficiente para localizar un valor basado en una clave e insertar y eliminar valores basados ​​en una clave. Las entradas de un HashMap no están ordenadas.

ArrayList y LinkedList son una implementación de la interfaz List. LinkedList proporciona acceso secuencial y generalmente es más eficiente para insertar y eliminar elementos en la lista, sin embargo, es menos eficiente para acceder a elementos en una lista. ArrayList proporciona acceso aleatorio y es más eficiente para acceder a elementos, pero generalmente es más lento para insertar y eliminar elementos.

jazzdawg
fuente
1

Pondré aquí algunos ejemplos de casos reales y escenarios en los que usar uno u otro, podría ser de ayuda para alguien más:

HashMap

Cuando tienes que usar caché en tu aplicación. Redis y membase son algún tipo de HashMap extendido. (No importa el orden de los elementos, necesita acceso de lectura rápido (O (1)) (un valor), usando una clave).

Lista enlazada

Cuando el orden es importante (se ordenan como se agregaron a LinkedList), se desconoce la cantidad de elementos (no desperdicie la asignación de memoria) y se requiere un tiempo de inserción rápido (O (1)). Una lista de tareas pendientes que se pueden enumerar secuencialmente a medida que se agregan es un buen ejemplo.

vhbazan
fuente
0

La desventaja de ArrayList y LinkedList es que al iterar a través de ellos, dependiendo del algoritmo de búsqueda, el tiempo que se tarda en encontrar un elemento aumenta con el tamaño de la lista.

La belleza del hash es que, aunque sacrifica algo de tiempo extra buscando el elemento, el tiempo necesario no aumenta con el tamaño del mapa. Esto se debe a que HashMap encuentra información convirtiendo el elemento que está buscando, directamente en el índice, para que pueda dar el salto.

En pocas palabras ... LinkedList : consume un poco más de memoria que ArrayList, bajo costo para inserciones (agregar y quitar) ArrayList : consume poca memoria, pero es similar a LinkedList, y toma más tiempo buscar cuando es grande. HashMap : puede realizar un salto al valor, haciendo que el tiempo de búsqueda sea constante para mapas grandes. Consume más memoria y tarda más en encontrar el valor que las listas pequeñas.

Simon Walker
fuente