différence entre linkedhashmap, hashmap, carte à la table de hachage

Je suis en train de préparer pour le logiciel interviews et je suis bloqué à une question de jours maintenant.

Je n'ai pas été en mesure de comprendre la différence entre linkedhashmap, carte, table de hachage, hashmap présents dans la Collection Java API.

Faire tous ces éléments ont les mêmes get et put complexités? Je sais que la carte est la classe d'interface
et hashmap, hashtable, linkedhashmap implémenter cette interface. Donc, est-ce à dire que l'intérieur de la mise en œuvre de ces 3 classes est le même? Comment sont-ils mis en œuvre dans les collections de l'api?

Merci d'Avance!!!

utilisation LinkedHashMap, il s'agit d'une liste liée, il est très rapide de recherche. Table de hachage est une mauvaise impl d'une table de hachage (basée sur l'arbre, pow2 seaux de taille) c'est pire à l'itération et médiocre sur la recherche. Table de hachage est la plus ancienne impl. w/ certaines synchronisations. IdentityHashMap est ce qu'une table de hachage impl devrait être, hélas, c'est uniquement pour de l'identité (==) et identityHashcode

OriginalL'auteur Amm Sokun | 2011-06-17

  1. 13

    Je doute que les différences peuvent s'expliquer nettement mieux que ce qui est déjà écrit dans la documentation Javadoc pour ces classes:

    • Carte est l'interface de base commun à toutes ces classes
    • un Hashtable est une implémentation de cette interface, pour le "vieux" jours où il a été jugé que le fait d'avoir tout synchronisé est une bonne idée (réf. Vecteur). Il propose "une sorte de" filet de sécurité, si vous savez ce que vous faites. Si vous êtes sérieux au sujet d'une carte qui peut être utilisé à partir de plusieurs threads, vous devez absolument vérifier les ConcurrentHashMap et ConcurrentSkipListMap.
    • un HashMap est presque le même comme une table de hachage, mais avec la synchronisation supprimé. C'est le préféré d'usage général, de la Carte de mise en œuvre.
    • un LinkedHashMap en outre maintient une liste liée de ses entrées, ce qui permet de maintenir une commande ou de l'utiliser comme un cache LRU facilement, il suffit de lire la JavaDoc.

    Toutes ces Map implémentations ont leur base get/put opérations (amorti) O(1) temps de la complexité. Il existe des différences mineures dans le traitement de null des valeurs, il est inévitable de vérifier la JavaDoc pour plus de détails.

    Pour avoir une idée de la façon dont ces classes sont mis en oeuvre, avoir un regard sur leur arbre d'héritage:

    • Map (juste l'interface)
      • Dictionary (obsolète classe abstraite)
        • Hashtable (la "vieille" carte de la mise en œuvre vie en soi)
      • AbstractMap (la fonctionnalité de base de la "nouvelle" carte implémentations)
        • HashMap (le premier béton de la carte de mise en œuvre pour un usage général)
          • LinkedHashMap (s'étend HashMap par mainaining la liste chaînée)
    Hashtable s'étend Dictionnaire btw. Dictionnaire est un peu inutile maintenant classe abstraite, personne n'y prête attention. La différence entre la table de hachage et Hashrable (à côté de l'évidence de synchronisation) est la taille de la benne tableau. Table de hachage utilise un pow2 et d'utiliser des hash&(table.length-1) qui est plus rapide que la table de hachage (hash & 0x7FFFFFFF) % tab.length
    Merci pour le Dictionary rappel, ajoute-il.
    peut une classe abstraite de mettre en œuvre une interface?
    Oui, vous pouvez faire de chaque classe abstraite, même si elle ne dispose pas de toutes les méthodes abstraites.
    dans le cas simple oui, mais HashMap a été réimplémentée dans Java4, à utiliser plus difficile algorithme qui demande que la taille de la carte est toujours une puissance de 2.

    OriginalL'auteur Waldheinz

  2. 7

    Ils ont tous honorent le même contrat, mais il ya quelques différences dans la mise en œuvre:

    • LinkedHashMap : les touches sont maintenues dans l'ordre d'insertion
    • Table de hachage : toutes les opérations sont synchronisés, aucune des garanties de classement
    • HashMap : aucune des garanties de classement, de meilleures performances

    Généralement, la meilleure pratique consiste à utiliser Map que le type pour les variables, puis vous instancier un type d'implémentation basée sur les besoins de votre code. HashMap est généralement préférable, à moins que vous avez besoin de certaines garanties d'organisation, auquel cas LinkedHashMap ou TreeMap sont de bons choix.

    stevevls, HashMap est pire à l'itération que LinkedHashMap et pour être rapide: c'est un arbre en fonction de la table de hachage qui suce sur le phénomène de matériel
    Je suis assez sûr un HashMap est pas basée sur l'arbre, seul le TreeMap est.
    ensuite, vous avez BESOIN de vérifier à nouveau. Je suis absolument sûr que c'est. c'est un tableau de seaux et de chaque collision est une liste liée, l'ensemble de la structure est un arbre, mais ce n'est pas binaire, mais l'enfer d'un arbre. Donc, vous n'est pas sûr. L'autre option populaire pour le hachage linéaire de la sonde qui surpasse les arbres, tout à fait bien.
    Vous avez raison, les listes jointes à l'seaux pourrait en effet faire mal localité. +1 pour le comprendre.
    oui il y a un peu plus d'indirections que nécessaire. 1er le seau (la Carte.D'entrée) lui-même peut être omis et il suffit d'utiliser Object[] w/ Clé/Valeur neightbours. Qui supprime les allocations sur mettre et supprime l'indirection sur obtenir. La traversée est bien plus rapide (en gros, c'est la traversée d'une liste de tableaux) et ainsi de suite.

    OriginalL'auteur stevevls

  3. 0

    Toutes les classes implémentent l'interface de la Carte et offre la plupart des mêmes fonctionnalités. La différence la plus importante est l'ordre dans lequel itération à travers les entrées qui va se passer:

    HashMap ne fait absolument aucune garantie sur l'itération de l'ordre. Il peut être (et sera) même changer complètement lorsque de nouveaux éléments sont ajoutés.
    TreeMap va se répéter selon "l'ordre naturel" des clés en fonction de leur compareTo (), méthode (ou un externe fourni Comparateur). En outre, il implémente l'interface SortedMap, qui contient des méthodes qui dépendent de cet ordre de tri.
    LinkedHashMap va se répéter dans l'ordre dans lequel les entrées ont été mis dans la map
    "Hashtable" est le nom générique de hachage à base de cartes. Dans le cadre de l'API Java, table de hachage est un objet de classe de l'époque de Java 1.1 avant les collections cadre existé. Il ne doit pas être utilisé plus, parce que son API est encombré avec des méthodes obsolètes qui double fonctionnalité, et ses méthodes sont synchronisés (qui peut diminuer les performances et est généralement inutile). Utilisation ConcurrrentHashMap au lieu de la table de hachage.

    OriginalL'auteur jigar