Quand utiliser HashMap plutôt que LinkedList ou ArrayList et vice-versa ?

Question

Quelle est la raison pour laquelle nous ne pouvons pas toujours utiliser un HashMap, même s'il est beaucoup plus efficace que ArrayList ou LinkedList dans les opérations d'ajout et de retrait, quel que soit le nombre d'éléments.

J'ai cherché sur Google et j'ai trouvé quelques raisons, mais il y avait toujours une solution de rechange pour utiliser HashMap, avec des avantages toujours présents.

Answer 1

Les listes représentent un ordre séquentiel d'éléments. Les cartes sont utilisées pour représenter une collection de paires clé/valeur.

Vous pouvez utiliser une carte comme une liste, mais cela présente des inconvénients certains.

Maintenir l'ordre : - Par définition, une liste est ordonnée. Vous ajoutez des éléments et vous êtes ensuite en mesure d'itérer dans la liste dans l'ordre dans lequel vous avez inséré les éléments. Lorsque vous ajoutez des éléments à un HashMap, vous n'avez pas la garantie de récupérer les éléments dans le même ordre que celui dans lequel vous les avez insérés. Il existe des sous-classes de HashMap comme LinkedHashMap qui maintiennent l'ordre, mais en général, l'ordre n'est pas garanti avec une Map.

Sémantique clé/valeur : - Le but d'une carte est de stocker des éléments sur la base d'une clé qui peut être utilisée pour retrouver l'élément à un moment ultérieur. Une fonctionnalité similaire ne peut être obtenue avec une liste que dans le cas limité où la clé se trouve être la position dans la liste.

Lisibilité du code Considérez les exemples suivants.

    // Adding to a List
    list.add(myObject);         // adds to the end of the list
    map.put(myKey, myObject);   // sure, you can do this, but what is myKey?
    map.put("1", myObject);     // you could use the position as a key but why?

    // Iterating through the items
    for (Object o : myList)           // nice and easy
    for (Object o : myMap.values())   // more code and the order is not guaranteed

Fonctionnalité de la collection De grandes fonctions utilitaires sont disponibles pour les listes via la classe Collections. Par exemple ...

    // Randomize the list
    Collections.shuffle(myList);

    // Sort the list
    Collections.sort(myList, myComparator);  

J'espère que cela vous aidera,

Answer 2

Les listes et les cartes sont des structures de données différentes. Les cartes sont utilisées lorsque vous souhaitez associer une clé à une valeur, tandis que les listes constituent une collection ordonnée.

Map est une interface dans le cadre de la collection Java et un HashMap est une implémentation de l'interface Map. Les HashMap sont efficaces pour localiser une valeur en fonction d'une clé et pour insérer et supprimer des valeurs en fonction d'une clé. Les entrées d'un HashMap ne sont pas ordonnées.

ArrayList et LinkedList sont une implémentation de l'interface List. LinkedList fournit un accès séquentiel et est généralement plus efficace pour insérer et supprimer des éléments dans la liste, mais elle est moins efficace pour accéder aux éléments d'une liste. ArrayList fournit un accès aléatoire et est plus efficace pour accéder aux éléments mais est généralement plus lent pour insérer et supprimer des éléments.

Answer 3

Je vais présenter ici quelques exemples de cas réels et de scénarios dans lesquels il convient d'utiliser l'un ou l'autre, cela pourrait être utile à quelqu'un d'autre :

HashMap

Lorsque vous devez utiliser un cache dans votre application. Redis et membase sont des sortes de HashMap étendus. (Peu importe l'ordre des éléments, vous avez besoin d'un accès rapide ( O(1) ) en lecture (une valeur), en utilisant une clé).

LinkedList

Lorsque l'ordre est important (ils sont classés comme ils ont été ajoutés à la liste chaînée), le nombre d'éléments est inconnu (ne gaspillez pas l'allocation de mémoire) et vous avez besoin d'un temps d'insertion rapide ( O(1) ). Une liste d'éléments à faire qui peuvent être énumérés séquentiellement au fur et à mesure qu'ils sont ajoutés est un bon exemple.

Answer 4

L'inconvénient des listes matricielles et des listes chaînées est que, lors de l'itération, selon l'algorithme de recherche, le temps nécessaire pour trouver un élément augmente avec la taille de la liste.

La beauté du hachage est que, bien que vous sacrifiiez un peu de temps supplémentaire pour rechercher l'élément, le temps pris ne croît pas avec la taille de la carte. Cela est dû au fait que le HashMap trouve des informations en convertissant l'élément que vous recherchez, directement dans l'index, ce qui lui permet de faire le saut.

Pour faire court... LinkedList : Consomme un peu plus de mémoire que ArrayList, faible coût pour les insertions (add & remove) Liste de tableaux : Consomme peu de mémoire, mais est similaire à LinkedList, et prend un temps supplémentaire pour la recherche lorsqu'elle est grande. HashMap : Peut effectuer un saut vers la valeur, rendant le temps de recherche constant pour les grandes cartes. Consomme plus de mémoire et prend plus de temps pour trouver la valeur que les petites listes.