Comment les dictionnaires intégrés de Python sont-ils implémentés?

Quelqu'un sait-il comment le type de dictionnaire intégré pour python est implémenté? Je crois comprendre qu'il s'agit d'une sorte de table de hachage, mais je n'ai pas pu trouver de réponse définitive.

Voici tout ce qui concerne les dictés Python que j'ai pu rassembler (probablement plus que quiconque voudrait en savoir; mais la réponse est complète).

• Les dictionnaires Python sont implémentés sous forme de tables de hachage .
• Les tables de hachage doivent permettre les collisions de hachage, c'est-à-dire que même si deux clés distinctes ont la même valeur de hachage, l'implémentation de la table doit avoir une stratégie pour insérer et récupérer les paires clé / valeur sans ambiguïté.
• Python dictutilise l'adressage ouvert pour résoudre les collisions de hachage (expliqué ci-dessous) (voir dictobject.c: 296-297 ).
• La table de hachage Python n'est qu'un bloc de mémoire contigu (un peu comme un tableau, vous pouvez donc faire une O(1)recherche par index).
• Chaque emplacement du tableau peut stocker une et une seule entrée. C'est important.
• Chaque entrée du tableau est en fait une combinaison des trois valeurs: <hachage, clé, valeur> . Ceci est implémenté comme une structure C (voir dictobject.h: 51-56 ).

• La figure ci-dessous est une représentation logique d'une table de hachage Python. Dans la figure ci-dessous, 0, 1, ..., i, ...à gauche sont des indices des emplacements dans la table de hachage (ils sont juste à des fins d'illustration et ne sont pas stockés 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 par 8 emplacements . (voir dictobject.h: 49 )

• Lors de l'ajout d'entrées à la table, nous commençons par un emplacement i, qui est basé sur le hachage de la clé. CPython utilise initialement i = hash(key) & mask(où mask = PyDictMINSIZE - 1, mais ce n'est pas vraiment important). Notez simplement que l'emplacement initial i, qui est vérifié dépend du hachage de la clé.
• Si cet emplacement est vide, l'entrée est ajoutée à l'emplacement (par entrée, je veux dire, <hash|key|value>). Mais que faire si cet emplacement est occupé!? Très probablement parce qu'une autre entrée a le même hachage (collision de hachage!)
• Si l'emplacement est occupé, CPython (et même PyPy) compare le hachage ET la clé (par comparer j'entends la ==comparaison et non la iscomparaison) de l'entrée dans l'emplacement par rapport au hachage et la clé de l'entrée actuelle à insérer ( dictobject.c : 337,344-345 ) respectivement. Si les deux correspondent, il pense que l'entrée existe déjà, abandonne et passe à l'entrée suivante à insérer. Si le hachage ou la clé ne correspondent pas, il commence à sonder .
• Le sondage signifie simplement qu'il recherche les emplacements par emplacement pour trouver un emplacement vide. Techniquement, nous pourrions simplement aller un par un i+1, i+2, ...et utiliser le premier disponible (c'est-à-dire le sondage linéaire). Mais pour des raisons expliquées magnifiquement dans les commentaires (voir dictobject.c: 33-126 ), CPython utilise un sondage aléatoire . En sondage aléatoire, le créneau suivant est sélectionné dans un ordre pseudo aléatoire. L'entrée est ajoutée au premier emplacement vide. Pour cette discussion, l'algorithme réel utilisé pour choisir l'emplacement suivant n'est pas vraiment important (voir dictobject.c: 33-126 pour l'algorithme de sondage). Ce qui est important, c'est que les logements soient sondés jusqu'à ce que le premier logement vide soit trouvé.
• La même chose se produit pour les recherches, commence juste avec l'emplacement initial i (où i dépend du hachage de la clé). Si le hachage et la clé ne correspondent pas à l'entrée de l'emplacement, il commence à sonder jusqu'à ce qu'il trouve un emplacement avec une correspondance. Si tous les emplacements sont épuisés, il signale un échec.
• BTW, le dictsera redimensionné s'il est plein aux deux tiers. Cela évite de ralentir les recherches. (voir dictobject.h: 64-65 )

REMARQUE: j'ai fait des recherches sur l'implémentation de Python Dict en réponse à ma propre question sur la façon dont plusieurs entrées dans un dict peuvent avoir les mêmes valeurs de hachage. J'ai posté une version légèrement modifiée de la réponse ici parce que toutes les recherches sont également très pertinentes pour cette question.

Comment les dictionnaires intégrés de Python sont-ils implémentés?

Voici le petit cours:

• Ce sont des tables de hachage. (Voir ci-dessous pour les détails de l'implémentation de Python.)
• Une nouvelle disposition et un nouvel algorithme, à partir de Python 3.6, les rendent
  • triés par insertion de clé, et
  • prendre moins de place,
  • à pratiquement aucun coût de performance.
• Une autre optimisation permet d'économiser de l'espace lorsque les dict partagent des clés (dans des cas spéciaux).

L'aspect ordonné n'est pas officiel à partir de Python 3.6 (pour donner aux autres implémentations une chance de suivre), mais officiel dans Python 3.7 .

Les dictionnaires Python sont des tables de hachage

Pendant longtemps, cela a fonctionné exactement comme ça. Python préallouerait 8 lignes vides et utiliserait le hachage pour déterminer où coller la paire clé-valeur. Par exemple, si le hachage de la clé se terminait en 001, il le collerait dans l'index 1 (c'est-à-dire le 2e) (comme dans l'exemple ci-dessous).

   <hash>       <key>    <value>
     null        null    null
...010001    ffeb678c    633241c4 # addresses of the keys and values
     null        null    null
      ...         ...    ...

Chaque ligne occupe 24 octets sur une architecture 64 bits, 12 sur 32 bits. (Notez que les en-têtes de colonne ne sont que des étiquettes pour nos besoins ici - ils n'existent pas réellement en mémoire.)

Si le hachage se terminait de la même manière que le hachage d'une clé préexistante, il s'agit d'une collision, puis il collerait la paire clé-valeur à un emplacement différent.

Après le stockage de 5 valeurs-clés, lors de l'ajout d'une autre paire de valeurs-clés, la probabilité de collisions de hachage est trop grande, de sorte que la taille du dictionnaire est doublée. Dans un processus 64 bits, avant le redimensionnement, nous avons 72 octets vides, et après, nous perdons 240 octets en raison des 10 lignes vides.

Cela prend beaucoup d'espace, mais le temps de recherche est assez constant. L'algorithme de comparaison de clés consiste à calculer le hachage, à aller à l'emplacement prévu, à comparer l'ID de la clé - s'il s'agit du même objet, ils sont égaux. Sinon, comparez les valeurs de hachage, si elles ne sont pas identiques, elles ne sont pas égales. Sinon, nous comparons enfin les clés pour l'égalité, et si elles sont égales, renvoyons la valeur. La comparaison finale pour l'égalité peut être assez lente, mais les vérifications antérieures raccourcissent généralement la comparaison finale, ce qui rend les recherches très rapides.

Les collisions ralentissent les choses, et un attaquant pourrait théoriquement utiliser des collisions de hachage pour effectuer une attaque par déni de service, nous avons donc randomisé l'initialisation de la fonction de hachage de telle sorte qu'il calcule différents hachages pour chaque nouveau processus Python.

L'espace gaspillé décrit ci-dessus nous a amenés à modifier l'implémentation des dictionnaires, avec une nouvelle fonctionnalité passionnante que les dictionnaires sont désormais classés par insertion.

Les nouvelles tables de hachage compactes

Nous commençons à la place en préallouant un tableau pour l'index de l'insertion.

Puisque notre première paire clé-valeur va dans le deuxième emplacement, nous indexons comme ceci:

[null, 0, null, null, null, null, null, null]

Et notre table est simplement remplie par ordre d'insertion:

   <hash>       <key>    <value>
...010001    ffeb678c    633241c4 
      ...         ...    ...

Donc, lorsque nous recherchons une clé, nous utilisons le hachage pour vérifier la position que nous attendons (dans ce cas, nous allons directement à l'index 1 du tableau), puis nous allons à cet index dans la table de hachage (par exemple, l'index 0 ), vérifiez que les clés sont égales (en utilisant le même algorithme décrit précédemment), et si c'est le cas, renvoyez la valeur.

Nous conservons un temps de recherche constant, avec des pertes de vitesse mineures dans certains cas et des gains dans d'autres, avec l'avantage que nous économisons beaucoup d'espace sur l'implémentation préexistante et nous conservons l'ordre d'insertion. Le seul espace perdu est les octets nuls dans le tableau d'index.

Raymond Hettinger l'a introduit sur python-dev en décembre 2012. Il est finalement entré dans CPython dans Python 3.6 . L'ordre par insertion a été considéré comme un détail d'implémentation de la version 3.6 pour permettre aux autres implémentations de Python de rattraper leur retard.

Clés partagées

Une autre optimisation pour économiser de l'espace est une implémentation qui partage les clés. Ainsi, au lieu d'avoir des dictionnaires redondants qui occupent tout cet espace, nous avons des dictionnaires qui réutilisent les clés partagées et les hachages de clés. Vous pouvez y penser comme ceci:

     hash         key    dict_0    dict_1    dict_2...
...010001    ffeb678c    633241c4  fffad420  ...
      ...         ...    ...       ...       ...

Pour une machine 64 bits, cela pourrait économiser jusqu'à 16 octets par clé par dictionnaire supplémentaire.

Clés partagées pour les objets personnalisés et les alternatives

Ces dictés à clé partagée sont destinés à être utilisés pour des objets personnalisés __dict__. Pour obtenir ce comportement, je pense que vous devez terminer de remplir votre __dict__avant d'instancier votre prochain objet ( voir PEP 412 ). Cela signifie que vous devez attribuer tous vos attributs dans le __init__ou __new__sinon vous pourriez ne pas obtenir vos économies d'espace.

Cependant, si vous connaissez tous vos attributs au moment de votre __init__exécution, vous pouvez également prévoir __slots__votre objet et garantir qu'il __dict__n'est pas créé du tout (s'il n'est pas disponible chez les parents), ou même autoriser __dict__mais garantir que vos attributs prévus sont stockés dans des emplacements de toute façon. Pour en savoir plus __slots__, voir ma réponse ici .

Voir également:

• PEP 509 - Ajouter une version privée à dicter
• PEP 468 - Préserver l'ordre des **kwargsdans une fonction.
• PEP 520 - Ordre de définition des attributs de classe de conservation
• PyCon 2010: The Might Dictionary - Brandon Rhodes
• PyCon 2017: le dictionnaire encore plus puissant - Brandon Rhodes
• PyCon 2017: Dictionnaires Python modernes Une confluence d'une douzaine de grandes idées - Raymond Hettinger
• dictobject.c - Implémentation de dict réelle de CPython en C.

Les dictionnaires Python utilisent l' adressage ouvert ( référence dans Beautiful code )

NB! L'adressage ouvert , ou hachage fermé , ne doit pas, comme indiqué sur Wikipedia, être confondu avec son hachage ouvert opposé !

L'adressage ouvert signifie que le dict utilise des emplacements de tableau, et lorsque la position principale d'un objet est prise dans le dict, le point de l'objet est recherché à un index différent dans le même tableau, en utilisant un schéma de "perturbation", où la valeur de hachage de l'objet joue un rôle. .