Comment Python dict peut-il avoir plusieurs clés avec le même hachage?

voici tout sur les dicts de Python que j'ai pu assembler (probablement plus que n'importe qui voudrait savoir; mais la réponse est complète). Un cri à Duncan pour avoir souligné que les dicts Python utilisent des fentes et me mener dans ce terrier de lapin.

• les dictionnaires Python sont implémentés en tant que tables de hachage .
• les tables de hachage doivent tenir compte de hachage collisions c'est-à-dire que même si deux clés 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 de clés et de valeurs sans ambiguïté.
• Python dict utilise en abordant pour résoudre les collisions de hachage (expliqué ci-dessous) (voir dictobject.c: 296-297 ).
• table de hachage Python est juste un bloc contingueux de la mémoire (sorte de comme un tableau, donc vous pouvez faire O(1) recherche par index).
• chaque fente de la table peut contenir une seule entrée. C'est important
• chaque entrée dans le tableau en fait une combinaison des trois valeurs - . Il s'agit d'une structure c (voir dictobject.h:51 à 56 )

• La figure ci-dessous est une représentation logique d'un table de hachage python. Dans la figure ci-dessous, 0, 1, ..., je. ,.. sur la gauche sont les indices du slots dans la table de hachage (ils sont juste à titre indicatif 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 slots . (voir dictobject.h:49 )

• lors de l'ajout entrées à la table, nous commençons par un certain slot, i qui est basé sur le hachage de la clé. CPython utilise initiale i = hash(key) & mask . Où mask = PyDictMINSIZE - 1 , mais ce n'est pas vraiment important). Il suffit de noter que la fente initiale, i, qui est cochée dépend de la hachage de la clé.
• Si l'emplacement 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é!? Très probablement parce qu'une autre entrée a le même hachage (hash collision!)
• si la fente est occupée, CPython (et même PyPy) compare la le hachage et la clé (par comparaison je veux dire == comparaison pas la is comparaison) de l'entrée dans la fente contre la clé de l'entrée actuelle à insérer ( dictobject.c: 337,344-345 ). Si les deux correspondent, alors il pense que l'entrée existe déjà, abandonne Et Passe à la suivante entrée à insérer. Si le hachage ou la clé ne correspondent pas, il commence sonder .
• Sonder signifie simplement qu'il Recherche Les fentes par fente pour trouver une fente vide. Techniquement, nous pourrions aller un par un, i+1, i+2, ... et utilisez la première disponible (qui est sonde linéaire). Mais pour des raisons expliquées magnifiquement dans les commentaires (Voir dictobject.c: 33-126 ), CPython utilise sondage aléatoire . En aléatoire la prochaine fente est choisie dans un ordre pseudo-aléatoire. L'entrée est ajoutée à la première logement vide. Pour cette discussion, l'algorithme réel utilisé pour choisir le prochain slot n'est pas vraiment important (voir dictobject.c:33-126 pour l'algorithme pour sonder). Ce qui est important, c'est que les fentes soient sondées jusqu'à ce que la première fente vide soit trouvée.
• la même chose se produit pour les recherches, commence juste avec la fente initiale i (où je dépend du 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é s'il est deux tiers plein. Cela évite de ralentir les recherches. (voir dictobject.h: 64-65 )

voilà! L'implémentation Python de dict vérifie à la fois l'égalité de hachage de deux clés et l'égalité normale ( == ) des touches lors de l'insertion des éléments. Donc, en résumé, s'il y a deux clés, a et b et hash(a)==hash(b) , mais a!=b , alors les deux peuvent exister harmonieusement dans un dict Python. Mais si hash(a)==hash(b) et a==b , alors ils ne peuvent pas tous les deux ÊTRE dans le même dict.

parce que nous devons sonder après chaque collision de hachage, un effet secondaire de trop de collisions de hachage est que les recherches et les insertions deviendront très lent (comme le souligne Duncan dans le commente ).

je suppose que la réponse courte à ma question est, "parce que c'est comment il est mis en œuvre dans le code source;) "

alors que c'est bon à savoir (pour geek points?), Je ne suis pas sûr de savoir comment il peut être utilisé dans la vie réelle. Parce qu'à moins d'essayer de casser explicitement quelque chose, pourquoi deux objets qui ne sont pas égaux, auraient le même hachage?

Edit : la réponse ci-dessous est une des façons possibles de traiter les collisions de hachage, il est cependant pas comment Python le fait. Le wiki de Python référencé ci-dessous est également incorrect. La meilleure source donnée par @Duncan ci-dessous est l'implémentation elle-même: http://svn.python.org/projects/python/trunk/Objects/dictobject.c Je m'excuse pour la confusion.

Il stocke une liste (ou seau) des éléments au hachage puis itère à travers cette liste jusqu'à ce qu'il trouve la clé réelle dans cette liste. Une image dit plus de mille mots:

ici vous voyez John Smith et Sandra Dee les deux hachures à 152 . Le seau 152 contient les deux. En regardant vers le haut Sandra Dee il trouve d'abord la liste dans le seau 152 , puis boucle à travers cette liste jusqu'à Sandra Dee est trouvé et renvoie 521-6955 .

ce qui suit est erroné c'est seulement ici pour le contexte: On wiki de Python vous pouvez trouver (pseudo?) code comment Python exécute la recherche.

il y a en fait plusieurs solutions possibles à ce problème, consultez l'article de wikipedia pour un bel aperçu: http://en.wikipedia.org/wiki/Hash_table#Collision_resolution

tables de hachage, en général doivent tenir compte des collisions de hachage! Tu vas avoir de la malchance et deux choses vont finir par arriver à la même chose. En dessous, il y a un ensemble d'objets dans une liste d'éléments qui ont la même clé de hachage. D'habitude, il n'y a qu'une chose dans cette liste, mais dans ce cas, elle les empilera dans la même. La seule façon de savoir qu'ils sont différents est par l'intermédiaire de l'opérateur égal.

quand cela se produit, votre performance se dégradera le temps, c'est pourquoi vous voulez que votre fonction de hachage soit aussi "aléatoire que possible".

dans le thread Je n'ai pas vu ce que fait exactement python avec les instances d'une classe définie par l'utilisateur quand nous l'avons mis dans un dictionnaire comme des clés. Lisons un peu la documentation: elle déclare que seuls les objets hashables peuvent être utilisés comme des clés. Les hashables sont toutes les classes immuables intégrées et toutes les classes définies par l'utilisateur.

les classes définies par L'Utilisateur ont _ _ _ cmp_ _ () et __hash__() méthodes par défaut; avec eux, tous les objets comparer inégal (sauf avec eux-mêmes) et x.__hash__() renvoie un résultat dérivés de id(x).

Donc si vous avez constamment __hash__ dans votre classe, mais ne fournissant aucune __cmp__ ou __eq__ méthode, puis toutes les instances sont inégales pour le dictionnaire. En revanche, si vous fournissez une méthode__ cmp __ou__ _ eq__, mais pas __hash__, vos instances sont encore inégales en termes de dictionnaire.

class A(object):
    def __hash__(self):
        return 42


class B(object):
    def __eq__(self, other):
        return True


class C(A, B):
    pass


dict_a = {A(): 1, A(): 2, A(): 3}
dict_b = {B(): 1, B(): 2, B(): 3}
dict_c = {C(): 1, C(): 2, C(): 3}

print(dict_a)
print(dict_b)
print(dict_c)

sortie

{<__main__.A object at 0x7f9672f04850>: 1, <__main__.A object at 0x7f9672f04910>: 3, <__main__.A object at 0x7f9672f048d0>: 2}
{<__main__.B object at 0x7f9672f04990>: 2, <__main__.B object at 0x7f9672f04950>: 1, <__main__.B object at 0x7f9672f049d0>: 3}
{<__main__.C object at 0x7f9672f04a10>: 3}