¿Regla de oro para elegir una implementación de una Colección Java?

Question

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

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

Answer 1

siempre he hecho esas decisiones sobre una base de caso por caso, en función del caso de uso, tales como:

• ¿Es necesario el orden de permanecer?
• ¿Tendré claves/valores nulos? Dups?
• ¿Será acceder por múltiples hilos
• qué necesito un par clave/valor
• ¿Necesito acceso aleatorio?

Y luego romper mi mano 5ª edición de Java en una cáscara de nuez y comparar el ~ 20 o más opciones. Tiene pequeñas y agradables tablas en el Capítulo cinco para ayudar a uno a descubrir lo que es apropiado.

Ok, tal vez si sé por el puño que un simple ArrayList o HashSet hará el truco, no voy a buscarlo todo. ;) pero si hay algo remotamente complejo sobre mi uso indended, apuesto a que estoy en el libro. Por cierto, pensé que se suponía que Vector era 'viejo sombrero' - no he usado en años.

Answer 2

Sobre su primera pregunta ...

La lista, el mapa y el conjunto sirven para diferentes propósitos. Sugiero leer sobre Java Collections Framework en http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html.

a ser un poco más concreto:

• Lista de usar si se necesita una estructura de datos de la matriz similar y que necesita para iterar sobre los elementos
• uso Mapa si necesita algo así como un diccionario
• use un conjunto si solo necesita decidir si algo pertenece al conjunto o no.

Sobre su segunda pregunta ...

La principal diferencia entre el vector y ArrayList es que el primero está sincronizado, este último no está sincronizado. Puede leer más sobre la sincronización en Java Concurrency in Practice.

La diferencia entre Hashtable (tenga en cuenta que la letra T no es mayúscula) y HashMap es similar, la primera está sincronizada, la última no está sincronizada.

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

Answer 3

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

Voy a utilizar un mapa cada vez que necesite realizar una búsqueda.

Para las implementaciones específicas, existen variaciones de Mapas y Conjuntos que preservan la orden, pero en gran parte todo se reduce a la velocidad. Tiendo a usar ArrayList para listas razonablemente pequeñas y HashSet para conjuntos razonablemente pequeños, pero hay muchas implementaciones (incluyendo cualquiera que usted mismo escriba). HashMap es bastante común para Maps. Algo más que "razonablemente pequeño" y debe comenzar a preocuparse por la memoria, de modo que será mucho más específico en términos algorítmicos.

This page tiene lotes de imágenes animadas junto con pruebas de código de muestra LinkedList frente a ArrayList si le interesan los números duros.

EDIT: espero que los siguientes enlaces muestran cómo estas cosas son en realidad elementos de una caja de herramientas, sólo hay que pensar en lo que sus necesidades son: Ver versiones Commons-Colecciones de Map, List y Set.

Answer 4

Supongo que sabes la diferencia entre una lista, un conjunto y un mapa de las respuestas anteriores. Por qué elegirías entre sus clases de implementación es otra cosa. Por ejemplo:

Lista:

1. ArrayList es rápido en la recuperación, pero lento en la inserción. 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. LinkedList tarda en recuperarse, pero se inserta rápidamente. 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.

Set:

1. HashSet no garantiza el orden de iteración, y por lo tanto es más rápido de los conjuntos. Tiene una sobrecarga alta y es más lenta que ArrayList, por lo que no debe usarla, excepto una gran cantidad de datos cuando su velocidad de hashing se convierte en un factor.
2. TreeSet mantiene los datos ordenados, por lo tanto, es más lento que HashSet.

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

Vector y Hashtable no deben ser utilizados. Son implementaciones sincronizadas, antes del lanzamiento de la nueva jerarquía de Colección, por lo tanto, lenta. Si se necesita sincronización, use Collections.synchronizedCollection().

Answer 5

Encontré Bruce Eckel pensando en Java para ser muy útil. Él compara muy bien las diferentes colecciones. Solía ​​mantener un diagrama que publicó mostrando la herencia heirachy en la pared de mi cubo como una referencia rápida. Una cosa que sugiero que hagas es tener en cuenta la seguridad de los hilos. Rendimiento por lo general significa no hilo seguro.

Answer 6

Para no ordenados, la mejor opció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 suficientemente ricas 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á usando un índice para indicar su posición, entonces eso requiere iterar a través de la lista para encontrar el nodo correcto. ArrayList es casi siempre más rápido.

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

Answer 7

Teóricamente hay 0 Big-Oh intercambios útiles, pero en la práctica, estos casi nunca importan.

En puntos de referencia del mundo real, ArrayList supera LinkedList incluso con listas grandes 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 a 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 las características de acceso a la memoria son mucho peores.

Mi regla es:

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

Answer 8

me gusta mucho esta hoja de trucos de Sergiy Kovalchuk de blog entry:

más detallada Alexander Zagniotov's flowchart from his site.

Answer 9

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

ArrayList:

• La mayoría de los casos en los que sólo tiene que almacenar o se puede recorrer un "montón de cosas" y luego iterar a través de ellos. La iteración es más rápida ya que su índice está basado.
• Siempre que se crea un ArrayList, una cantidad fija de memoria se asigna a ella y una vez exceeeded, se copia todo el conjunto

LinkedList:

• Utiliza lista doblemente enlazada de modo de inserción y la operación de eliminación será rápida ya que solo agregará o eliminará un nodo.
• Recuperar es lento, ya que tendrá que recorrer los nodos.

HashSet:

• Hacer otros sí o no decisiones sobre un artículo, por ejemplo, "es el elemento una palabra de inglés", "¿está el elemento en la base de datos?" , "es el artículo en esta categoría?" etc.

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

HashMap:

• Se utiliza en los casos en que hay que decir "para un X dado, ¿cuál es la Y"? A menudo es útil para implementar cachés o índices en memoria, es decir, pares de valores clave. Por ejemplo: Para un ID de usuario dado, ¿cuál es su nombre en caché/objeto de usuario?
• Siempre vaya con HashMap para realizar una búsqueda.

Vector y Hashtable están sincronizados y, por lo tanto, son un poco más lentos y si se necesita sincronización, use Collections.synchronizedCollection(). Compruebe This para las colecciones ordenadas. Espero que esto me encanta.