HashMap vs ArrayList performances suis-je correct

Je crois actuellement que:

  • Lorsque vous avez besoin d’une structure à partir de laquelle vous allez extraire des éléments de manière aléatoire, utilisez un HashMap
  • Lorsque vous récupérerez des éléments dans l’ordre (par exemple, en utilisant une boucle for), utilisez une liste de ArrayList

Suis-je généralement correct? Y a-t-il des situations où ce n’est pas correct?

En général, oui, vous avez raison. Il existe également une structure de données combinée, la LinkedHashMap , qui offre un access rapide à des éléments arbitraires ainsi qu’un ordre 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 chacun d’entre eux qui pourraient être plus adaptées à des besoins plus spécifiques. Par exemple, une LinkedList peut fournir des performances supérieures à ArrayList pour certaines exigences de mise en queue / de mise en queue.

Une carte est une carte ou “tableau associatif” . Il a une disposition clé-> valeur. Une liste est en revanche une liste , qui est une collection ordonnée d’éléments.

Une comparaison plus directe pourrait être faite entre Set et List: ces deux valeurs contiennent des valeurs, où la liste est explicitement ordonnée (vous pouvez obtenir l’élément # x), et l’ensemble n’est généralement pas ordonné (à moins qu’il s’agisse d’un SortedSet , auquel cas l’ordre d’itération sera commandé par un comparateur).

HashSet et ArrayList sont les deux implémentations les plus courantes de Set et List . Pour vérifier si un élément appartient à une arraylist (contains (element)), l’implémentation parcourt tous ses éléments, vérifiant si 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 “va” directement à la position où cet élément devrait résider, et vérifie s’il existe.

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

Sur une liste, vous pouvez demander l’élément # x, en plus de ce que vous pouvez faire sur un ensemble, à savoir append, supprimer, demander-si-présent (contient) et itérer 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. Ceci est complètement absurde et n’a aucune utilité autre que celle de perdre au moins 4 octets, on pourrait en dire 12, pour tous les éléments insérés dans le HashSet.

Je dirais que vous avez généralement raison, mais pas tout à fait exact. Vous utilisez un HashMap pour la récupération de données, mais pas toujours de manière aléatoire. Vous utilisez une ArrayList pour l’itération, mais vous pouvez également l’utiliser pour des recherches via l’index.

Plus généralement, vous utilisez une implémentation de Map lorsque vous avez besoin de récupérer efficacement des éléments par recherche, c’est-à-dire de récupérer quelque chose en fonction de la clé – tels que des dictionnaires, des caches, des référentiels, etc.

Vous utilisez une implémentation de List lorsque vous souhaitez simplement une structure de données dans laquelle vous pouvez effectuer une itération sur vos données, généralement lorsque vous les souhaitez dans un ordre prédéterminé et / ou prévisible.

En d’autres termes, vous utilisez Map s comme une structure de données d’indexation et vous utilisez List s comme vous utiliseriez habituellement des tableaux.

Pour moi, c’est plus important si je me soucie de la commande des articles de la collection. Si vous vous souciez de la commande, utilisez la liste de tableaux. Si vous ne vous souciez pas de la commande (vous voulez simplement stocker un tas d’éléments), vous pouvez utiliser une HashMap.

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

Je suis en désaccord légèrement. Pour moi, cela dépend plus de la façon dont je veux récupérer les éléments. Si je veux le faire en fonction de quelque chose comme leur ordre (par index, pour être précis), j’aurais tendance à utiliser une structure linéaire comme un ArrayList (ou même un tableau). Si je dois rechercher des éléments, j’utiliserais une structure de carte telle que HashMap.

Un autre facteur de complication concerne les insertions et l’ordre, comme l’a souligné dan.