Règle de base pour choisir une implémentation D'une Collection Java?

j'aime vraiment cette feuille de tricherie de Sergiy Kovalchuk entrée de blog :

plus détaillé est Alexander zagniotov flowchart de son site .

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

Liste :

1. ArrayList est rapide sur la récupération, mais lent sur l'insertion. C'est bon pour une implémentation qui lit beaucoup mais qui n'insère pas/n'enlève pas beaucoup. Il conserve ses données dans un bloc continu de mémoire, donc à chaque fois qu'il a besoin de s'étendre, il copie tout le tableau.
2. LinkedList est lent sur la récupération, mais rapide sur l'insertion. C'est bon pour une implémentation qui insère/supprime beaucoup mais ne lit pas beaucoup. Il ne garde pas le tableau entier dans un bloc continu de mémoire.

Set:

1. HashSet ne garantit pas le afin de l'itération, et est donc plus rapide des ensembles. Il a la tête haute et est plus lent que ArrayList, donc vous ne devriez pas l'utiliser sauf pour une grande quantité de données quand sa vitesse de hachage devient un facteur.
2. TreeSet conserve les données commandées, est donc plus lent que le HashSet.

Map: la performance et le comportement de HashMap et TreeMap sont parallèles aux implémentations Set.

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

en théorie, il y a des compromis utiles Big-Oh , mais dans la pratique, ces compromis n'ont presque jamais d'importance.

Dans le monde réel des repères, des ArrayList effectue 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 submerger la courbe asymptotique. Par exemple, les listes liées nécessitent une allocation d'objet supplémentaire pour chaque nœud, ce qui signifie plus lent à créer un nœud et des caractéristiques d'accès à la mémoire bien pires.

ma règle est:

1. toujours commencer avec ArrayList et HashSet et HashMap (i.e. pas LinkedList ou TreeMap).
Les déclarations de Type
2. devraient toujours être une interface (i.e. List, Set, Map) donc si un profileur ou une révision de code prouve le contraire, vous pouvez changer l'implémentation sans rien casser.

à propos de votre première question...

la Liste, la Carte et Définir les finalités sont différentes. Je suggère de lire à propos de La Java Collections Framework à http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html .

Pour être un peu plus concret:

• utiliser la liste si vous avez besoin d'une structure de données de type tableau et que vous devez itérer au-dessus des éléments
• utiliser la carte si vous avez besoin de quelque chose comme un dictionnaire
• l'utilisation d'un Ensemble si vous avez seulement besoin de décider si quelque chose appartient à l'ensemble ou pas.

à propos de votre deuxième question...

la principale différence entre vectoriel et ArrayList est que le premier est synchronisé, le dernier n'est pas synchronisé. Vous pouvez en savoir plus sur la synchronisation dans Java Competiency in Practice .

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

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.

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

et le 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 faites cela, leurs interfaces ne sont pas suffisamment riches pour que leur synchronisation soit utile. Dans le cas de Map, Concourtmap ajoute des opérations supplémentaires pour rendre l'interface utile. Competienthashmap est un bon mise en œuvre de ConcurrentMap.

LinkedList n'est presque jamais une bonne idée. Même si vous faites beaucoup d'insertions et de suppression, si vous utilisez un index pour indiquer la position puis qui nécessite une itération à travers la liste pour trouver le bon noeud. ArrayList est presque toujours plus rapide.

pour la carte et L'ensemble, les variantes de hachage seront plus rapides que l'arbre/trié. Les algues de Hash ont tendance à avoir une performance O(1), alors que les arbres seront O(log n).

permettent les doublons, tandis que les Sets 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 y a des variations de cartes et D'ensembles qui préservent l'ordre, mais en grande partie cela se réduit à de la vitesse. Je vais avoir tendance à utiliser ArrayList pour des listes raisonnablement petites et HashSet pour des ensembles raisonnablement petits, mais il y a de nombreuses implémentations (y compris celles que vous écrivez vous-même). HashMap is assez courant pour les cartes. N'importe quoi de plus que "raisonnablement petit" et vous devez commencer à vous soucier de la mémoire de sorte que ce sera beaucoup plus spécifique algorithmique.

cette page contient lots d'images animées ainsi qu'un exemple de code testing LinkedList vs. ArrayList si vous êtes intéressé par les nombres durs.

EDIT: j'espère que les liens suivants montrent comment ces choses sont vraiment juste articles dans une boîte à outils, vous avez juste à penser à ce que vos besoins sont: Voir communes-Collections versions de carte , liste et ensemble .

comme le suggèrent d'autres réponses, il existe différents scénarios pour utiliser la collecte correcte selon le cas d'utilisation. J'énumère quelques points,

ArrayList:

• la plupart des cas où vous avez juste besoin de stocker ou itérer à travers un "tas de choses" et plus tard itérer à travers eux. L'itération est plus rapide que son indice de base.
• chaque fois que vous créez un ArrayList, une quantité fixe de mémoire est attribué à lui et une fois dépassé, il copie l'ensemble du tableau

LinkedList:

• il utilise une liste doublement liée de sorte que l'opération d'insertion et de suppression sera rapide car elle ne fera qu'ajouter ou supprimer un noeud.
La récupération de
• est lente car elle devra itérer à travers les noeuds.

HashSet:

• de Faire d'autres oui-pas de décisions à propos d'un élément, par exemple, "est l'élément d'un mot d'anglais", "est l'élément dans la base de données?", "le sujet est-il dans cette catégorie?" etc.

• Se souvenir "des articles que vous avez déjà traités", p.ex. lors d'une recherche sur le web;

HashMap:

• utilisé dans les cas où vous devez dire" pour un X donné, qu'est-ce que le Y"? Il est souvent utile pour implémenter des caches ou des index en mémoire I. e paires de valeurs clés par exemple: Pour un ID utilisateur donné, Quel est leur nom/objet utilisateur mis en cache?.
• toujours utiliser HashMap pour effectuer une recherche.

vecteur et Hashtable sont synchronisés et donc un peu plus lents et si la synchronisation est nécessaire, utiliser les Collections.synchronizedCollection (). Vérifier ce pour les collections triées. Espérons que ce hepled.

J'ai trouvé la pensée de Bruce Eckel en Java très utile. Il compare très bien les différentes collections. J'avais l'habitude de garder un diagramme qu'il a publié montrant l'héritage heirachy sur mon mur de cube comme une référence rapide. Une chose que je vous suggère de faire est de garder à l'esprit la sécurité des fils. La Performance signifie généralement que le filet n'est pas sûr.