Règle empirique pour choisir une implémentation d'une collection Java ?

Question

Quelqu'un connaît-il une bonne règle empirique pour choisir entre différentes implémentations des interfaces de collection Java comme List, Map ou Set ?

Par exemple, en général, pourquoi ou dans quels cas préférerais-je utiliser un Vector ou un ArrayList, un Hashtable ou un HashMap ?

Answer 1

J'aime beaucoup cette antisèche tirée du blog de Sergiy Kovalchuk, mais elle est malheureusement hors ligne. Cependant, la Wayback Machine a un copie historique :

L'organigramme d'Alexander Zagniotov, également hors ligne et donc historique, était plus détaillé. copie du blog :

Extrait du blog sur les préoccupations soulevées dans les commentaires : "Cette antisèche n'inclut pas les classes rarement utilisées comme WeakHashMap, LinkedList, etc. car elles sont conçues pour des tâches très spécifiques ou exotiques et ne devraient pas être choisies dans 99 % des cas."

Answer 2

Je suppose que vous connaissez la différence entre une liste, un ensemble et une carte d'après les réponses ci-dessus. La raison pour laquelle vous choisiriez entre leurs classes d'implémentation est une autre chose. Par exemple :

Liste :

1. Liste de tableaux est rapide à la récupération, mais lent à l'insertion. C'est une bonne solution pour une implémentation qui lit beaucoup mais ne fait pas beaucoup d'insertions et de retraits. Il conserve ses données dans un bloc de mémoire continu, donc à chaque fois qu'il a besoin de s'étendre, il copie le tableau entier.
2. LinkedList est lent à la récupération, mais rapide à l'insertion. C'est une bonne solution pour une implémentation qui insère/retire beaucoup mais ne lit pas beaucoup. Il ne conserve pas le tableau entier dans un bloc de mémoire continu.

Set :

1. HashSet ne garantit pas l'ordre d'itération, et est donc le plus rapide des ensembles. Il a une surcharge élevée et est plus lent que ArrayList, donc vous ne devriez pas l'utiliser sauf pour une grande quantité de données lorsque sa vitesse de hachage devient un facteur.
2. Ensemble d'arbres garde les données ordonnées, et est donc plus lent que HashSet.

Carte : Les performances et le comportement de HashMap et TreeMap sont parallèles aux implémentations Set.

Vector et Hashtable ne doivent pas être utilisés. Ce sont des implémentations synchronisées, avant la sortie de la nouvelle hiérarchie Collection, donc lentes. Si la synchronisation est nécessaire, utilisez Collections.synchronizedCollection().

Answer 3

J'ai toujours pris ces décisions au cas par cas, selon le cas d'utilisation, par exemple :

• Ai-je besoin de la commande pour rester ?
• Aurai-je des clés/valeurs nulles ? Des doublons ?
• Sera-t-il accessible par plusieurs fils ?
• Ai-je besoin d'une paire clé/valeur
• Aurai-je besoin d'un accès aléatoire ?

Et puis je sors ma 5ème édition pratique Java en quelques mots et comparez les quelque 20 options. Le chapitre 5 contient de jolis petits tableaux pour vous aider à déterminer ce qui est approprié.

Ok, peut-être que si je sais d'emblée qu'un simple ArrayList ou HashSet fera l'affaire, je ne regarderai pas tout ;) mais s'il y a quoi que ce soit de complexe dans mon utilisation prévue, vous pouvez être sûr que je suis dans le livre. BTW, je pensais que Vector était censé être "vieux jeu" - je n'en ai pas utilisé depuis des années.

Answer 4

Théoriquement, il existe des Big-Oh mais en pratique, ils n'ont presque jamais d'importance.

Dans les repères du monde réel, ArrayList surpasse les performances de LinkedList même avec de grandes listes et avec des opérations comme "beaucoup d'insertions près de l'avant". Les universitaires ignorent le fait que les algorithmes réels ont des facteurs constants qui peuvent dépasser la courbe asymptotique. Par exemple, les listes chaînées nécessitent une allocation d'objet supplémentaire pour chaque nœud, ce qui signifie que la création d'un nœud est plus lente et que les caractéristiques d'accès à la mémoire sont bien pires.

Ma règle est la suivante :

1. Commencez toujours par ArrayList et HashSet et HashMap (c'est-à-dire pas LinkedList ou TreeMap).
2. Les déclarations de type doivent toujours être des interfaces (par exemple, List, Set, Map). Ainsi, si un profileur ou une revue de code prouve le contraire, vous pouvez modifier l'implémentation sans rien casser.

Answer 5

Pour votre première question...

La liste, la carte et le jeu ont des objectifs différents. Je vous suggère de vous renseigner sur le cadre des collections Java à l'adresse http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html .

Pour être un peu plus concret :

• utilisez List si vous avez besoin d'une structure de données de type tableau et que vous devez itérer sur les éléments.
• utilisez Map si vous avez besoin de quelque chose comme un dictionnaire
• Utilisez un ensemble si vous avez seulement besoin de décider si quelque chose appartient à l'ensemble ou non.

Pour votre deuxième question...

La principale différence entre Vector et ArrayList est que le premier est synchronisé, le second ne l'est pas. Vous pouvez en savoir plus sur la synchronisation dans Java Concurrency en pratique .

La différence entre Hashtable (notez que le T n'est pas une majuscule) et HashMap est similaire, le premier est synchronisé, le second ne l'est pas.

Je dirais qu'il n'y a pas de règle empirique pour préférer une implémentation ou une autre, cela dépend vraiment de vos besoins.