Règle générale pour choisir une implémentation d'une collection Java ?

Question

Quelqu'un a-t-il une bonne règle générale pour choisir entre différentes implémentations d'interfaces Java Collection telles que List, Map ou Set ?

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

Answer 1

J'ai toujours pris ces décisions au cas par cas, en fonction du cas d'utilisation, comme :

• Ai-je besoin que la commande reste ?
• Aurai-je des clés/valeurs nulles ?Des dupes ?
• Sera-t-il accessible par plusieurs threads
• 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 bref et comparez la vingtaine d’options.Il contient de jolis petits tableaux au chapitre cinq pour 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 chercherai pas tout.;) mais s'il y a quelque chose de complexe à propos de mon utilisation prévue, vous pariez que je suis dans le livre.BTW, je pensais que Vector est censé être un « vieux chapeau » - je ne l'ai pas utilisé depuis des années.

Answer 2

J'aime beaucoup cette aide-mémoire de Sergiy Kovalchuk entrée de blog:

L'organigramme d'Alexandre Zagniotov était plus détaillé, mais malheureusement il est hors ligne.

Answer 3

Je suppose que vous connaissez la différence entre une liste, un ensemble et une carte à partir des réponses ci-dessus.Pourquoi choisiriez-vous entre leurs classes d’implémentation est une autre chose.Par exemple:

Liste:

1. Liste des tableaux est rapide à récupérer, mais lent à insérer.C'est bon pour une implémentation qui lit beaucoup mais n'insère/supprime pas beaucoup.Il conserve ses données dans un bloc de mémoire continu, de sorte qu'à chaque fois qu'il a besoin d'être développé, il copie l'intégralité du tableau.
2. Liste liée est lent à récupérer, mais rapide à insérer.C'est bon pour une implémentation qui insère/supprime beaucoup mais ne lit pas beaucoup.Il ne conserve pas l'intégralité du tableau dans un seul bloc de mémoire continu.

Ensemble:

1. Jeu de hachage 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 qu'ArrayList, vous ne devriez donc pas l'utiliser, sauf pour une grande quantité de données lorsque sa vitesse de hachage devient un facteur.
2. Ensemble d'arbres conserve les données ordonnées, 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 une synchronisation est nécessaire, utilisez Collections.synchronizedCollection().

Answer 4

Théoriquement, il y a des choses utiles Gros-Oh des compromis, mais dans la pratique, ceux-ci n'ont presque jamais d'importance.

Dans les benchmarks du monde réel, ArrayList surperforme LinkedList Même avec de grandes listes et avec des opérations comme "Beaucoup d'insertions près du front". Les universitaires ignorent le fait que les algorithmes réels ont des facteurs constants qui peuvent submerger 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 une création plus lente d'un nœud et des caractéristiques d'accès à la mémoire bien pires.

Ma règle est la suivante :

1. Commencez toujours par ArrayList, HashSet et HashMap (c'est-à-direpas LinkedList ou TreeMap).
2. Les déclarations de type doivent toujours être une interface (c'est-à-direList, Set, Map), donc si un profileur ou une révision de code prouve le contraire, vous pouvez modifier l'implémentation sans rien casser.

Answer 5

A propos de votre première question...

List, Map et Set servent à des fins différentes.Je suggère de lire sur le Java Collections Framework sur 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 parcourir 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.

A propos de 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 La concurrence Java en pratique.

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

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

Answer 6

Pour les non triés, le meilleur choix, plus de neuf fois sur dix, sera :ArrayList, HashMap, HashSet.

Vector et Hashtable sont synchronisés et peuvent donc être un peu plus lents.Il est rare que vous souhaitiez des implémentations synchronisées, et lorsque vous le faites, leurs interfaces ne sont pas suffisamment riches pour que leur synchronisation soit utile.Dans le cas de Map, ConcurrentMap ajoute des opérations supplémentaires pour rendre l'interface utile.ConcurrentHashMap est une bonne implémentation de ConcurrentMap.

LinkedList n'est presque jamais une bonne idée.Même si vous effectuez beaucoup d'insertions et de suppressions, si vous utilisez un index pour indiquer la position, cela nécessite de parcourir la liste pour trouver le bon nœud.ArrayList est presque toujours plus rapide.

Pour Map et Set, les variantes de hachage seront plus rapides que l'arborescence/triée.Les algorithmes de hachage ont tendance à avoir des performances O(1), alors que les arbres seront O(log n).

Answer 7

Les listes autorisent les éléments en double, tandis que les ensembles n'autorisent qu'une seule instance.

J'utiliserai une carte chaque fois que j'aurai besoin d'effectuer une recherche.

Pour les implémentations spécifiques, il existe des variantes de cartes et d'ensembles qui préservent l'ordre, mais cela dépend en grande partie de la vitesse.J'aurai tendance à utiliser ArrayList pour des listes raisonnablement petites et HashSet pour des ensembles raisonnablement petits, mais il existe de nombreuses implémentations (y compris celles que vous écrivez vous-même).HashMap est assez courant pour Maps.Tout ce qui est plus que « raisonnablement petit » et vous devez commencer à vous soucier de la mémoire, ce sera donc beaucoup plus spécifique sur le plan algorithmique.

Cette page a beaucoup d'images animées ainsi que des exemples de code testant LinkedList vs.ArrayList si vous êtes intéressé par les chiffres précis.

MODIFIER: J'espère que les liens suivants démontrent à quel point ces éléments ne sont en réalité que des éléments dans une boîte à outils, il vous suffit de réfléchir à vos besoins :Voir les versions Commons-Collections de Carte, Liste et Ensemble.

Answer 8

Comme suggéré dans d'autres réponses, il existe différents scénarios pour utiliser la collecte correcte en fonction du cas d'utilisation.J'énumère quelques points,

Liste des tableaux:

• Dans la plupart des cas, il vous suffit de stocker ou de parcourir un "tas de choses", puis de les parcourir ultérieurement.L'itération est plus rapide car elle est basée sur un index.
• Chaque fois que vous créez une ArrayList, une quantité fixe de mémoire lui est allouée et une fois dépassée, elle copie l'intégralité du tableau.

Liste liée :

• Il utilise une liste doublement chaînée, donc les opérations d'insertion et de suppression seront rapides car elles ajouteront ou supprimeront uniquement un nœud.
• La récupération est lente car elle devra parcourir les nœuds.

Ensemble de hachage :

• Prendre d'autres décisions oui ou non concernant un élément, par ex."L'élément est-il un mot d'anglais", "L'élément est-il dans la base de données?" , "L'article est-il dans cette catégorie?" etc.

• Se souvenir des "éléments que vous avez déjà traités", par ex.lors d'une exploration du Web ;

Carte de hachage :

• Utilisé dans les cas où il faut dire « pour un X donné, quel est le Y » ?Il est souvent utile pour implémenter des caches ou des index en mémoire, c'est-à-dire des paires clé-valeur. Par exemple :Pour un ID utilisateur donné, quel est son nom/objet utilisateur mis en cache ?.
• Utilisez toujours HashMap pour effectuer une recherche.

Vector et Hashtable sont synchronisés et donc un peu plus lents et si une synchronisation est nécessaire, utilisez Collections.synchronizedCollection().Vérifier Ce pour les collections triées.J'espère que cela a aidé.

Answer 9

J'ai trouvé Thinking in Java de Bruce Eckel très utile.Il compare très bien les différentes collections.J'avais l'habitude de conserver un diagramme qu'il publiait montrant la hiérarchie d'héritage sur mon mur de cube comme référence rapide.Une chose que je vous suggère de faire est de garder à l’esprit la sécurité des threads.Les performances signifient généralement qu’elles ne sont pas thread-safe.

Answer 10

Eh bien, cela dépend de ce dont vous avez besoin.Les directives générales sont les suivantes :

Liste est une collection où les données sont conservées par ordre d'insertion et où chaque élément a un index.

Ensemble est un sac d'éléments sans duplication (si vous réinsérez le même élément, il ne sera pas ajouté).Les données n'ont pas la notion d'ordre.

Carte Vous accédez et écrivez vos éléments de données par leur clé, qui peut être n'importe quel objet possible.

Attribution: https://stackoverflow.com/a/21974362/2811258

Pour plus d'informations sur les collections Java, regarde cet article.