Quelle est la vraie différence entre un dictionnaire et d'une table de hachage?

J'ai toujours utilisé des dictionnaires. J'écris en Python.

InformationsquelleAutor TIMEX | 2010-01-13
  1. 181

    Un dictionnaire est un concept général que les cartes des clés à des valeurs. Il existe de nombreuses façons de mettre en œuvre une telle cartographie.

    Une table de hachage est une manière concrète de mettre en œuvre un dictionnaire.

    En plus de tables de hachage, une autre façon de mettre en œuvre des dictionnaires est arbres rouge-noir.

    Chaque méthode a ses propres avantages et inconvénients. Un rouge-noir arbre peut toujours effectuer une recherche en O(log N). Une table de hachage pouvez effectuer une recherche en O(1) temps même si cela peut se décomposer en O(N) en fonction de l'entrée.

    • Je souhaite que je pourrais voter pour celle-ci plus d'une fois.
    • Je vais re-upvote pour vous.
    InformationsquelleAutor R Samuel Klatchko
  2. 25

    Un dictionnaire est une structure de données des cartes clés à des valeurs.

    Une table de hachage est une structure de données des cartes clés à des valeurs en prenant la valeur de hachage de la clé (par l'application de certaines fonction de hachage) et de la cartographie que d'un seau où une ou plusieurs valeurs sont stockées.

    OMI ceci est analogue à demander la différence entre une liste et une liste liée.

    Pour plus de clarté, il peut être important de noter qu'il PEUT être le cas que Python implémente actuellement leurs dictionnaires en utilisant des tables de hachage, et il PEUT être le cas dans l'avenir que Python modifications qui fait sans causer de leurs dictionnaires de cesser d'être des dictionnaires.

    • Ne serait pas la principale différence sera que d'un dictionnaire enregistre également les touches? Donc, vous pouvez interroger un dictionnaire pour th elsit de clés - vous pouvez pas pour une table de hachage
    • Beckett: Non. Les deux peuvent stocker les clés. Le dictionnaire général. La table de hachage est une mise en œuvre spécifique du concept général.
    • Beckett: Hm, intéressant. Est-il nécessairement le cas que d'un dictionnaire des magasins de clés et d'une table de hachage ne l'est pas? Java est Hashtable stocke les clés - n'est-il pas une table de hachage, alors?
    • Penser un peu plus, une table de hachage a nécessairement pour stocker les clés en cas de collisions!
    • Pas de. De stockage de clés n'est pas une caractéristique distinctive. La particularité est que d'un dictionnaire est un concept générique où une table de hachage est une réelle mise en œuvre.
    • Un dictionnaire est un concept général--classes de stocker et de récupérer des valeurs basées sur les touches. Un dictionnaire (dans cette interprétation--vague question) est pas une structure de données-le mot n'implique aucune structure spécifique, mais juste un simple ensemble d'opérations ("store", "récupérer", généralement "énumérer"), que de nombreux réelles structures de données à fournir.
    • Maynard: qu'est-Ce que la distinction ici entre la structure de données et le concept? Pouvez-vous donner un exemple d'un dictionnaire qui n'est pas une structure de données?
    • Serait-il plus acceptable de dire abstraite de la structure de données? J'ai toujours utilisé les deux indifféremment. Je pense que "concept" est un peu trop vague.

    InformationsquelleAutor danben
  3. 16

    "Un dictionnaire" a différentes significations dans la programmation, wikipédia vais vous dire -- "tableau associatif", le sens dans lequel Python utilise le terme (aussi connu comme un "mapping"), est l'un de ces sens (mais "dictionnaire de données", et "les attaques par dictionnaire" dans le mot de passe deviner tentatives, sont également importants).

    Les tables de hachage sont des structures de données importantes; Python utilise pour mettre en œuvre deux types de données intégrés, dict et set.

    Donc, même en Python, vous ne pouvez pas envisager de "table de hachage" pour être un synonyme de "dictionnaire"... depuis une structure de données similaires est également utilisé pour mettre en œuvre les "jeux"!-)

    InformationsquelleAutor Alex Martelli
  4. 9

    Un dictionnaire Python est en interne mis en œuvre avec une table de hachage.

    • Une sous-classe de dict n'est pas le Python de la mise en œuvre d'un dictionnaire; c'est votre propre.
    InformationsquelleAutor Nicolás
  5. 1

    Une table de hachage utilise toujours la fonction d'exploitation sur une valeur pour déterminer si une valeur doit être stockée. Un Dictionnaire (comme je crois vous l'intention) est un terme plus général, et indique simplement un mécanisme de recherche, qui pourrait être une table de hachage ou pourraient être mis en œuvre par une structure plus simple qui ne prend pas en compte la valeur elle-même dans la détermination de son emplacement de stockage.

    InformationsquelleAutor mickeyf
  6. 0

    Dictionnaire est mis en œuvre en utilisant des tables de hachage. À mon avis, la différence entre les 2 peut être considéré comme la différence entre les Piles et les Tableaux où nous serions à l'aide de tableaux pour mettre en œuvre les Piles.

    InformationsquelleAutor Thunderhashy