clase - generar numeros aleatorios en java del 1 al 100

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

¿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?

Acerca de su primera pregunta ...

Lista, mapa y conjunto sirven para 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 List si necesita una estructura de datos tipo array y necesita iterar sobre los elementos
usa Map si necesitas algo 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 Vector y ArrayList es que el primero está sincronizado, el ú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 el T no es una letra mayúscula) y HashMap es similar, el primero está sincronizado, el último no está sincronizado.

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

Creo que el pensamiento de Bruce Eckel en Java fue 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.

En teoría, hay intercambios de Big-Oh útiles, pero en la práctica, estos casi nunca importan.

En los puntos de referencia del mundo real, ArrayList a 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:

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

Las listas permiten elementos duplicados, mientras que Sets permite solo una instancia.

Utilizaré un Mapa cada vez que necesite realizar una búsqueda.

Para las implementaciones específicas, existen variaciones de mapas y conjuntos que preservan el 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.

Esta página tiene muchas imágenes animadas junto con el código de muestra que prueba LinkedList vs. ArrayList si le interesan los números duros.

EDITAR: Espero que los siguientes enlaces demuestren cómo estas cosas son realmente solo elementos en una caja de herramientas, solo tienes que pensar cuáles son tus necesidades: ver las versiones de Colecciones, mapas y listas de Commons.

Para las mejores opciones no ordenadas, más de nueve de cada diez veces serán: 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 tree / sorted. Los algoritmos de hash tienden a tener un rendimiento O (1), mientras que los árboles serán O (log n).

Asumiré 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 :

ArrayList es rápido de recuperar, 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.
LinkedList tarda en recuperarse, pero es rápido de 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.

Conjunto:

HashSet no garantiza el orden de iteración, y por lo tanto es el 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 hash se convierta en un factor.
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 paralelos a las implementaciones de 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, son lentas. Si se necesita sincronización, use Collections.synchronizedCollection ().

Siempre tomé esas decisiones caso por caso, dependiendo del caso de uso, como por ejemplo:

¿Necesito el pedido para permanecer?
¿Tendré claves / valores nulos? Dups?
¿Será accedido por múltiples hilos?
¿Necesito un par clave / valor?
¿Necesitaré acceso aleatorio?

Y luego saco mi práctica 5ta edición Java in a Nutshell y comparo las ~ 20 opciones más o menos. 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.

Me gusta mucho esta hoja de trucos de la entrada de blog de Sergiy Kovalchuk:

Más detallado es el diagrama de flujo de Alexander Zagniotov de su sitio .

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,

Lista de arreglo:

La mayoría de los casos en los que solo necesita almacenar o repetir a través de 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.
Cada vez que crea una ArrayList, se le asigna una cantidad fija de memoria y una vez que se supera, copia la matriz completa.

Lista enlazada:

Utiliza una lista doblemente vinculada, 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 iterar a través de los nodos.

HashSet:

Tomar otras decisiones de sí o no sobre un elemento, 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", por ejemplo, al hacer un rastreo web;

HashMap:

Se usa en casos en los que necesita decir "para una X determinada, ¿qué 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 determinado, ¿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. Si se necesita sincronización, use Collections.synchronizedCollection (). Verifique esto para las colecciones ordenadas. Espero esto hepled.