En quoi l'implémentation de LinkedHashMap est-elle différente de HashMap?

Question

Si la complexité temporelle de LinkedHashMap est identique à la complexité de HashMap, pourquoi avons-nous besoin de HashMap? Quels sont tous les frais supplémentaires liés à LinkedHashMap par rapport à HashMap en Java?

Answer 1

LinkedHashMap prendra plus de mémoire. Chaque entrée dans un HashMap normal a juste la clé et la valeur. Chaque entrée LinkedHashMap a ces références et les références aux entrées suivantes et précédentes. Il y a aussi un peu plus de tâches ménagères à faire, bien que cela ne soit généralement pas pertinent.

Answer 2

Si LinkedHashMap du temps de la complexité est la même que HashMap la complexité pourquoi avons-nous besoin de table de hachage?

Vous ne devez pas confondre complexité et les performances. Deux algorithmes ont la même complexité, mais on peut toujours faire mieux que les autres.

Rappelez-vous que f(N) is O(N) signifie que:

C1*N <= limit(f(N), N -> infinity) <= C2*N  

où C1 et C2 sont des constantes strictement positives. La complexité ne dit rien sur la façon de petite ou grande, l' C des valeurs sont. Pour les deux algorithmes différents, les constantes seront probablement différents.

(Et n'oubliez pas que le big-O complexité est sur le comportement de performance N devient très grande. Il vous dit rien sur le comportement / performance pour petite N valeurs).

Answer 3

• LinkedHashMap maintient en outre une liste à double liaison parcourant toutes ses entrées, qui fournira un ordre reproductible. Cette liste chaînée définit l'ordre d'itération, qui est normalement l'ordre dans lequel les clés ont été insérées dans la carte (ordre d'insertion).
• HashMap n'a pas ces coûts supplémentaires (temps d'exécution, espace) et devrait être préféré à LinkedHashMap lorsque vous ne vous souciez pas de l'ordre d'insertion.

Answer 4

LinkedHashMap est une infrastructure de données utile lorsque vous avez besoin de connaître l'ordre d'insertion dans la carte. Un cas d'utilisation approprié concerne la mise en œuvre d'un cache LRU. En raison du maintien de l'ordre du LinkedHashMap, les performances de la structure de données sont légèrement inférieures à celles d'une carte aléatoire telle que HashMap. Si vous n'avez pas besoin de connaître l'ordre d'insertion, vous devez toujours opter pour le HashMap pour de meilleures performances.

Answer 5

Il y a une autre différence majeure entre HashMap et LinkedHashMap :Itération est plus efficace dans le cas de LinkedHashMap.

En tant qu'Éléments dans LinkedHashMap sont connectés avec chaque autre, de sorte itération nécessite du temps proportionnel à la taille de la carte, quelle que soit sa capacité. Mais dans le cas de la table de hachage; comme il n'y a pas de commande fixe, de sorte que l'itération sur il faut du temps proportionnel à sa capacité.

J'ai mis plus de détails sur mon blog.