Performances de HashMap et ArrayList, est-ce correct ?

Question

Je le crois actuellement :

• Lorsque vous avez besoin d'une structure à partir de laquelle vous récupérez des éléments de manière aléatoire, utilisez une structure de type HashMap
• Lorsque vous récupérez des éléments dans l'ordre (par exemple, à l'aide d'une boucle for), utilisez une balise de type ArrayList

Est-ce que je suis généralement correct ? Y a-t-il des situations où ce n'est pas correct ?

Answer 1

Une carte est un carte, ou "tableau associatif". . Il a une disposition clé->valeur. Une liste est par contre un liste qui est une collection ordonnée d'éléments.

Une comparaison plus directe pourrait être faite entre Définir et Liste : Les deux contiennent des valeurs, où la liste est explicitement ordonnée (vous pouvez obtenir l'élément # x), et l'ensemble n'est (typiquement) pas ordonné (bien, à moins que ce soit une SortedSet (dans ce cas, l'ordre d'itération sera ordonné par un comparateur).

Les deux implémentations les plus courantes pour Set et List sont HashSet et ArrayList. . Pour vérifier si un élément appartient à une liste de tableaux (contains(element)), l'implémentation itère sur tous les éléments de celle-ci, en vérifiant si l'on a trouvé l'élément en utilisant la méthode equals(). Pour vérifier si un élément appartient à un hashset, on calcule d'abord le hashCode() de l'élément, puis on se rend "directement" à la position où cet élément devrait réside, et vérifie s'il s'y trouve.

Ainsi, une différence significative entre ArrayList et HashSet est la vitesse de contains() .

Sur une liste, vous pouvez demander l'élément# x, en plus de ce que vous pouvez faire sur un ensemble, c'est-à-dire ajouter, enlever, demander s'il est présent (contient), et itérer sur tous les éléments.

Sur une carte, vous pouvez demander un élément par sa clé, plutôt que par son index comme vous le faites avec une liste.

Un HashSet est actuellement implémenté simplement par un HashMap où la partie valeur de la relation clé->valeur n'est pas utilisée. C'est complètement absurde et cela ne sert à rien d'autre qu'à gaspiller au moins 4 octets, voire 12, pour tous les éléments insérés dans le HashSet.

Answer 2

En général, oui, vous avez raison. Il existe également une structure de données combinée, la Cartouche de hachage qui offre un accès rapide à des éléments arbitraires ainsi qu'un ordonnancement prévisible.

Toutefois, il convient de noter que ArrayList et HashMap ne sont que deux implémentations des interfaces List et Map, respectivement. Il existe d'autres implémentations de chacune d'elles qui pourraient être plus adaptées à des besoins plus spécifiques. Par exemple, une LinkedList peut offrir de meilleures performances qu'une ArrayList pour certaines exigences en matière de mise en file d'attente/défilement.

Answer 3

Je dirais que vous êtes généralement correct, mais pas entièrement exact. Vous utilisez un HashMap pour la recherche de données, mais pas toujours de façon aléatoire. Vous utilisez un ArrayList pour l'itération mais vous pouvez également l'utiliser pour les recherches via l'index.

Plus généralement, vous utilisez un Map lorsque vous avez besoin de récupérer efficacement des éléments par consultation, c'est-à-dire en récupérant quelque chose sur la base de la clé - comme dans les dictionnaires, les caches, les référentiels, etc.

Vous utilisez un List mise en œuvre lorsque vous voulez simplement une structure de données où vous pouvez itérer sur vos données, généralement lorsque vous les voulez dans un ordre prédéterminé et/ou prévisible.

En d'autres termes, vous utilisez Map comme une structure de données d'indexation, et vous utilisez les List comme vous le feriez habituellement avec des tableaux.

Answer 4

Pour moi, il s'agit plutôt de savoir si je me soucie de l'ordre des éléments de la collection. Si vous vous souciez de l'ordre, utilisez ArrayList. Si vous ne vous souciez pas de l'ordre (vous voulez juste stocker un tas d'éléments), vous pouvez utiliser un HashMap.

Answer 5

N'oubliez pas qu'il est également beaucoup plus rapide d'atteindre un élément spécifique avec une carte (si vous avez la clé) qu'avec un tableau (à moins que vous n'ayez un index, mais une clé vous permettra toujours d'obtenir la bonne valeur alors qu'un index peut ne pas fonctionner si de nouveaux éléments sont insérés ou si les anciens sont supprimés).