Comment est la mise en œuvre de LinkedHashMap différente de la table de hachage?

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

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 comment petit ou grand la C valeurs. Pour les deux algorithmes différents, l'une des constantes sera probablement différents.

(Et rappelez-vous que big-O complexité est sur le comportement /performance N devient très grande. Il vous dit rien sur le comportement /performance pour les petites N valeurs).

---

Cela dit, la différence de performance entre HashMap et LinkedHashMap opérations de l'équivalent des cas d'utilisation est relativement faible. Souvent, la mémoire supplémentaire de frais généraux que les plus pertinentes.

LinkedHashMap est utile structure de données lorsque vous avez besoin de savoir l'ordre d'insertion des clés de la Carte. Un cas d'utilisation pour la mise en œuvre d'un cache LRU. En raison de maintien de l'ordre de la LinkedHashMap, la structure de données des besoins de la mémoire supplémentaire par rapport à la table de hachage. Dans le cas où la commande d'insertion n'est pas une obligation, vous devriez toujours aller pour la table de hachage.

HashMap ne maintient pas l'ordre d'insertion, donc ne soutient aucune liste doublement chaînée.

Plus saillant de LinkedHashMap est qu'il maintient l'ordre d'insertion des paires clé-valeur. LinkedHashMap utilise Liste doublement chaînée pour le faire.

Entrée de LinkedHashMap ressemble à ceci:

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

Par l'aide avant et après l' - nous garder une trace de l'entrée nouvellement ajoutée dans LinkedHashMap, qui nous aide dans le maintien de l'ordre d'insertion.

Avant de se reporter à l'entrée et
après se réfère à la prochaine entrée dans LinkedHashMap.

Pour les schémas et explication étape par étape, veuillez vous référer http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

• Re-dimensionnement est censé être plus rapide qu'elle parcourt son
  double-liste liée à transférer le contenu dans un nouveau tableau de tableau.
• containsValue() est Substituée à profiter de la plus rapide
  itérateur.
• LinkedHashMap peut également être utilisé pour créer un cache LRU. Un spécial
  LinkedHashMap(capacité, loadFactor, accessOrderBoolean) constructeur
  est prévu de créer un lien de hachage de la carte dont l'ordre d'itération est
  l'ordre dans lequel ses entrées ont été dernier accès, de
  moins récemment accédé à la plus récente. Dans ce cas, simplement
  l'interrogation de la carte avec get() est une modification structurelle.