LinkedHashMap vs HashMap! = LinkedList vs ArrayList
J'ai lu que LinkedHashMap a plus vite itération de la vitesse de HashMap parce que ses éléments sont doublement liés les uns aux autres. En outre, à cause de cela, LinkedHashMap est plus lente lors de l'insertion ou la suppression d'éléments. Sans doute parce que ces liens doivent également être mis à jour.
Bien que je peux voir une analogie avec la LinkedList vs ArrayList, en ce que les éléments de LinkedList sont également doublement lié, j'ai lu qu'il itère plus lent que ArrayList, et est plus rapide d'insertion et de suppression.
Pourquoi est-ce? Peut-être que je fais une erreur quelque part?
Cheers!
source d'informationauteur Markos Fragkakis
Vous devez vous connecter pour publier un commentaire.
L'analogie ne fonctionne pas. LinkedList et ArrayList sont deux indépendants des implémentations d'une Liste. LinkedHashMap, cependant, est la même structure de données que d'une table de hachage, mais avec une LinkedList tissé pour faire itération plus rapides et cohérentes.
La raison que LinkedHashMap itération est plus rapide que la HashMap itération est que HashMap itération a pour itérer sur tous les seaux, même le vide. Le fait que LinkedHashMap a une liste de pointage pour les données signifie qu'il peut ignorer le vide les seaux. La liste dans la LinkedHashMap est une liste, parce que la suppression des temps de rester constante (plutôt que de O(n) si c'était un arrray soutenu la liste).
Listes liées itération run-temps (l'accès à chaque élément) sont "théoriquement" la même chose qu'une liste de tableau. Les deux nécessitent O(n) (Big-O Notation) de l'exécution. Toutefois, en raison de l'allocation de mémoire pour les tableaux est plus un bloc continu de la mémoire (lié listes d'éléments sont attribués individuellement et peuvent être n'importe où en mémoire), la mise en cache d'entrée en vigueur.
Quelques détails:
L'itérateur de commande pour LinkedHashMap est le même que l'ordre d'insertion dans la carte. Donc, la LinkedList partie n'a qu'à "insérer" à la fin (qui est O(1) pour une liste, qui conserve la trace de la queue), et la partie de Carte seulement une carte encart qui est O(1). Un général de liste liée insert est en O(N) et une liste de tableaux insérer à la matrice de copier le contenu de plus de 1 fente avant une insertion peut se produire.
Pour itérer une liste chaînée, on doit suivre chaque référence (lien) dans chaque élément. Ces références peuvent point presque n'importe où, il n'y a aucune garantie que le prochain élément qui suit est le cas actuellement dans la mémoire, ce qui est mauvais pour la mise en cache. Parce que chaque référence doit être récupéré, il est plus lent.
Les tableaux sont en continu dans la mémoire et l'élément suivant est juste l'emplacement de la mémoire de l'élément courant correspond à la taille de l'élément.
Pour une liste doublement chaînée, d'insertion n'importe où dans le tableau est très rapide, car seules les références de ce qui précède et d'éléments suivants doivent être modifiés. Un tableau, en revanche, est plus lent en raison de l'insertion à tout point de l'ensemble du tableau à copier pour faire de la place pour le nouvel élément. Même en ajoutant un élément également causer de l'ensemble du tableau à copier quand il n'y a pas assez de continue de la mémoire allouée pour le tableau plus récemment l'ajout d'un élément.
Vous aurez surtout l'avis de l'insertion des différences lorsque vous traitez avec de grands ensembles de données. Peu importe à quelle vitesse
arraycopy()
peut être une liste doublement chaînée est toujours plus rapide pour l'insertion. Parce que HashMaps sont rarement répétées et de s'appuyer sur l'insertion et de l'ordre, une liste doublement chaînée peut lui donner un boost de performance.