¿Regla general para elegir una implementación de una colección Java?

Question

¿Alguien tiene una buena regla general para elegir entre diferentes implementaciones de interfaces de la Colección Java como List, Map o Set?

Por ejemplo, ¿generalmente por qué o en qué casos preferiría usar un Vector o un ArrayList, un Hashtable o un HashMap?

Answer 1

Siempre he tomado esas decisiones caso por caso, según el caso de uso, como por ejemplo:

• ¿Necesito que el pedido permanezca?
• ¿Tendré claves/valores nulos?¿Duplicaciones?
• ¿Será accedido por múltiples hilos?
• ¿Necesito un par clave/valor?
• ¿Necesitaré acceso aleatorio?

Y luego les presento mi práctica quinta edición. Java en pocas palabras y compare las aproximadamente 20 opciones.Tiene pequeñas tablas agradables en el Capítulo cinco para ayudar a uno a determinar qué es apropiado.

Ok, tal vez si sé de antemano que un simple ArrayList o HashSet funcionará, no lo buscaré todo.;) pero si hay algo remotamente complejo sobre mi uso previsto, puedes apostar que estoy en el libro.Por cierto, pensé que se supone que Vector es un "viejo sombrero"; no lo he usado en años.

Answer 2

Me gusta mucho esta hoja de trucos de Sergiy Kovalchuk. Entrada de blog:

Más detallado fue el diagrama de flujo de Alexander Zagniotov, pero desafortunadamente no está disponible.

Answer 3

Asumiré que conoces la diferencia entre Lista, Conjunto y Mapa a partir de las respuestas anteriores.Por qué elegirías entre sus clases de implementación es otra cosa.Por ejemplo:

Lista:

1. Lista de arreglo es rápido para recuperar, pero lento para insertar.Es bueno para una implementación que lee mucho pero no inserta/elimina mucho.Mantiene sus datos en un bloque continuo de memoria, por lo que cada vez que necesita expandirse, copia toda la matriz.
2. Lista enlazada es lento para recuperar, pero rápido para insertar.Es bueno para una implementación que inserta/elimina mucho pero no lee mucho.No mantiene toda la matriz en un bloque continuo de memoria.

Colocar:

1. Conjunto de hash no garantiza el orden de iteración y, por lo tanto, es el más rápido de los conjuntos.Tiene una gran sobrecarga y es más lento que ArrayList, por lo que no deberías usarlo excepto para una gran cantidad de datos cuando su velocidad de hash se convierte en un factor.
2. Conjunto de árboles Mantiene los datos ordenados, por lo tanto es más lento que HashSet.

Mapa: El rendimiento y el comportamiento de HashMap y TreeMap son paralelos a las implementaciones de Set.

No se deben utilizar vectores ni Hashtable.Son implementaciones sincronizadas, antes del lanzamiento de la nueva jerarquía de Colección, por lo que son lentas.Si es necesaria la sincronización, utilice Collections.synchronizedCollection().

Answer 4

Teóricamente son útiles. grande-oh compensaciones, pero en la práctica casi nunca importan.

En puntos de referencia del mundo real, ArrayList supera LinkedList Incluso con grandes listas y con operaciones como "muchas inserciones cerca del frente". Los académicos ignoran el hecho de que los algoritmos reales tienen factores constantes que pueden abrumar la curva asintótica.Por ejemplo, las listas enlazadas requieren una asignación de objetos adicional para cada nodo, lo que significa que es más lento crear un nodo y características de acceso a la memoria mucho peores.

Mi regla es:

1. Comience siempre con ArrayList, HashSet y HashMap (es decir,no LinkedList o TreeMap).
2. Las declaraciones de tipo siempre deben ser una interfaz (es decir,Lista, Conjunto, Mapa) de modo que si un generador de perfiles o una revisión del código demuestra lo contrario, puede cambiar la implementación sin romper nada.

Answer 5

Sobre tu primera pregunta...

Lista, Mapa y Conjunto tienen diferentes propósitos.Sugiero leer sobre Java Collections Framework en http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

Para ser un poco más concreto:

• use Lista si necesita una estructura de datos similar a una matriz y necesita iterar sobre los elementos
• use Map si necesita algo como un diccionario
• use un Conjunto si solo necesita decidir si algo pertenece al conjunto o no.

Sobre tu segunda pregunta...

La principal diferencia entre Vector y ArrayList es que el primero está sincronizado y el segundo no.Puede leer más sobre la sincronización en Concurrencia de Java en la práctica.

La diferencia entre Hashtable (tenga en cuenta que la T no es una letra mayúscula) y HashMap es similar: el primero está sincronizado y el segundo no.

Yo diría que no existe una regla general para preferir una implementación u otra, realmente depende de tus necesidades.

Answer 6

Para los no clasificados la mejor elección, más de nueve de cada diez veces, será:ArrayList, HashMap, HashSet.

Vector y Hashtable están sincronizados y, por lo tanto, pueden ser un poco más lentos.Es raro que desee implementaciones sincronizadas y, cuando lo hace, sus interfaces no son lo suficientemente ricas como para que su sincronización sea útil.En el caso de Map, ConcurrentMap agrega operaciones adicionales para que la interfaz sea útil.ConcurrentHashMap es una buena implementación de ConcurrentMap.

LinkedList casi nunca es una buena idea.Incluso si está realizando muchas inserciones y eliminaciones, si está utilizando un índice para indicar la posición, entonces será necesario recorrer la lista para encontrar el nodo correcto.ArrayList casi siempre es más rápido.

Para Map y Set, las variantes de hash serán más rápidas que las de árbol/ordenadas.Los algoritmos hash tienden a tener un rendimiento O(1), mientras que los árboles serán O(log n).

Answer 7

Las listas permiten elementos duplicados, mientras que los conjuntos permiten solo una instancia.

Usaré un mapa siempre que necesite realizar una búsqueda.

Para implementaciones específicas, existen variaciones de mapas y conjuntos que preservan el orden, pero en gran medida todo se reduce a la velocidad.Tenderé a usar ArrayList para listas razonablemente pequeñas y HashSet para conjuntos razonablemente pequeños, pero hay muchas implementaciones (incluidas las que usted mismo escribe).HashMap es bastante común para Maps.Cualquier cosa más que "razonablemente pequeña" y tienes que empezar a preocuparte por la memoria, por lo que será algorítmicamente mucho más específica.

Esta página tiene lotes de imágenes animadas junto con código de muestra que prueba LinkedList vs.ArrayList si está interesado en números concretos.

EDITAR: Espero que los siguientes enlaces demuestren cómo estas cosas son en realidad solo elementos en una caja de herramientas, solo tienes que pensar en cuáles son tus necesidades:Consulte las versiones Commons-Collections de Mapa, Lista y Colocar.

Answer 8

Como se sugiere en otras respuestas, existen diferentes escenarios para utilizar la recopilación correcta según el caso de uso.Estoy enumerando algunos puntos,

Lista de arreglo:

• En la mayoría de los casos, solo necesita almacenar o iterar a través de un "montón de cosas" y luego iterar a través de ellas.La iteración es más rápida ya que se basa en índices.
• Cada vez que crea una ArrayList, se le asigna una cantidad fija de memoria y, una vez excedida, copia toda la matriz.

Lista enlazada:

• Utiliza una lista doblemente enlazada, por lo que la operación de inserción y eliminación será rápida ya que solo agregará o eliminará un nodo.
• La recuperación es lenta ya que tendrá que recorrer los nodos.

Conjunto de hash:

• Tomar otras decisiones de sí o no sobre un elemento, p."¿Es el artículo una palabra de inglés", "¿El elemento en la base de datos?" , "¿Está el artículo en esta categoría?" etc.

• Recordar "qué elementos ya ha procesado", p.al realizar un rastreo web;

Mapa Hash:

• Se utiliza en los casos en los que es necesario decir "para una X determinada, ¿cuál es la Y"?A menudo es útil para implementar cachés o índices en memoria, es decir, pares clave-valor. Por ejemplo:Para una ID de usuario determinada, ¿cuál es su nombre almacenado en caché/objeto de usuario?
• Utilice siempre HashMap para realizar una búsqueda.

Vector y Hashtable están sincronizados y, por lo tanto, son un poco más lentos. Si se necesita sincronización, use Collections.synchronizedCollection().Controlar Este para colecciones ordenadas.Espero que esto haya ayudado.

Answer 9

El Thinking in Java de Bruce Eckel me pareció muy útil.Compara muy bien las diferentes colecciones.Solía ​​​​guardar un diagrama que publicó que muestra la herencia hereditaria en la pared de mi cubo como referencia rápida.Una cosa que te sugiero que hagas es tener en cuenta la seguridad de los hilos.El rendimiento generalmente significa que no es seguro para subprocesos.

Answer 10

Bueno, depende de lo que necesites.Las pautas generales son:

Lista es una colección donde los datos se guardan en orden de inserción y cada elemento tiene un índice.

Colocar es una bolsa de elementos sin duplicación (si reinsertas el mismo elemento, no se agregará).Los datos no tienen la noción de orden.

Mapa Usted accede y escribe sus elementos de datos mediante su clave, que podría ser cualquier objeto posible.

Atribución: https://stackoverflow.com/a/21974362/2811258

Para obtener más información sobre las colecciones de Java, mira este artículo.