Comment sont Python ' s construit en dictionnaires mis en œuvre

Question

Quelqu'un sait-il comment le dictionnaire intégré type pour python est mis en œuvre ? Ma compréhension est que c’est une sorte de table de hachage, mais je n’ai pas pu trouver toute sorte de réponse définitive.

Answer 1

Ici, c'est tout à propos de Python dicts que j'étais capable de mettre ensemble (probablement plus que quiconque voudrais savoir; mais la réponse est plus complète).

• Python dictionnaires sont mis en œuvre comme les tables de hachage.
• Les tables de hachage doit permettre de collisions de hachage même si deux touches ont la même valeur de hachage, la mise en œuvre de la table doit avoir une stratégie pour insérer et extraire la clé et la valeur des paires sans ambiguïté.
• Python dict utilise en abordant pour résoudre les collisions de hachage (expliqué ci-dessous) (voir dictobject.c:296-297).
• Python table de hachage est juste un continguous bloc de mémoire (un peu comme un tableau, de sorte que vous pouvez le faire O(1) recherche par index).
• Chaque fente de la table peut stocker une et une seule entrée. C'est important
• Chaque entrée dans la table en fait une combinaison de ces trois valeurs . Il est implémenté sous forme d'une structure C (voir dictobject.h:51-56)

• La figure ci-dessous est une représentation logique d'un python de la table de hachage. Dans la figure ci-dessous, 0, 1, ..., i, ... sur la gauche sont les indices des fentes dans la table de hachage (ils le sont uniquement à des fins d'illustration et ne sont pas stockées avec la table, évidemment!).

  # Logical model of Python Hash table
  -+-----------------+
  0| <hash|key|value>|
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+
  

• Lorsqu'un nouveau dict est initialisé, il commence avec 8 slots. (voir dictobject.h:49)

• Lors de l'ajout d'entrées à la table, nous commençons avec quelques fente, i qui est basé sur le hachage de la clé. Disponible utilise initiale i = hash(key) & mask. Où mask = PyDictMINSIZE - 1, mais ce n'est pas vraiment important). Il suffit de noter que la première fente, j', qui est vérifié dépend du hachage de la clé.
• Si ce logement est vide, l'entrée est ajoutée à la fente (par l'entrée, je veux dire, <hash|key|value>). Mais que faire si ce logement est occupé!? La plus probable, car une autre entrée a le même hachage (hash collision!)
• Si le logement est occupé, Disponible (et même PyPy) compare le hachage ET la clé (par comparer, je veux dire == comparaison pas l' is comparaison) de l'entrée dans le logement à l'encontre de la clé de l'entrée actuelle pour être inséré (dictobject.c:337,344-345). Si les deux correspondent, alors elle pense que l'entrée existe déjà, abandonne et passe à l'entrée suivante à être inséré. Si l'une de hachage ou de la clé ne correspond pas, il commence à sonder.
• Sondage signifie simplement qu'il recherche les emplacements par logement pour trouver un logement vide. Techniquement, nous pourrions aller un par un, i+1, i+2, ... et l'utilisation de la premier disponible (linear probing). Mais, pour les raisons expliquées magnifiquement dans les commentaires (voir dictobject.c:33-126), Disponible utilise aléatoire de sondage. Au hasard de sondage, le premier logement est pris dans un pseudo ordre aléatoire. L'entrée est ajoutée à la première logement vide. Pour cette discussion, le réel de l'algorithme utilisé pour choisir le prochain emplacement n'est pas vraiment important (voir dictobject.c:33-126 pour l'algorithme pour sonder). Ce qui est important, c'est que les fentes sont sondé jusqu'au premier emplacement vide est trouvé.
• La même chose se produit pour les recherches, tout commence par la première fente i (où i dépend de la valeur de hachage de la clé). Si le hachage et la clé ne correspond pas à l'entrée dans le logement, il commence à sonder, jusqu'à ce qu'il trouve un logement avec une allumette. Si tous les emplacements sont épuisées, il signale un échec.
• BTW, le dict sera redimensionnée si c'est aux deux tiers. Cela évite de ralentir les recherches. (voir dictobject.h:64-65)

NOTE: j'ai fait la recherche sur le langage Python Dict mise en œuvre en réponse à ma propre question à propos de la façon dont plusieurs entrées dans un dict peuvent avoir les mêmes valeurs de hachage. J'ai posté un peu modifié la version de la réponse ici parce que toutes les recherches, est très pertinent pour cette question.

Answer 2

Python utilisation des Dictionnaires en abordant (référence à l'intérieur de Beau code)

NB! En abordant, une.k.un fermé de hachage doit, comme indiqué dans Wikipédia, à ne pas confondre avec son contraire ouvrir le hachage! (ce que nous voyons dans l'acceptation de réponse).

En abordant signifie que le dict utilise la matrice de fentes, et lorsque l'objet principal du poste est pris dans le dict, de l'objet spot est demandée à un autre indice dans le même tableau, à l'aide d'une "perturbation", où le hachage de l'objet de valeur joue un rôle.

Answer 3

À PyCon 2010, Brandon Craig Rhodes a donné une excellente intervention sur le dictionnaire Python. Il offre un bon aperçu de la mise en œuvre du dictionnaire avec des exemples et des visuels. Si vous avez 45 minutes (ou même simplement 15), je recommande de regarder l’exposé avant de procéder à la mise en oeuvre effective.

Answer 4

Voici un lien vers mise en oeuvre effective dans le référentiel SVN de python. Cela devrait être la réponse plus précise.

Answer 5

Implémentation de dictionnaire Python pur

Pour ceux curieux de voir comment l’application dict de CPython fonctionne, j’ai écrit une implémentation de Python en utilisant les mêmes algorithmes.