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

Question

Je essaie de comprendre la fonction Python hash sous le capot. J'ai créé une classe personnalisée où toutes les instances retournent la même valeur de hash.

class C:
    def __hash__(self):
        return 42

J'ai juste supposé qu'une seule instance de la classe ci-dessus peut être dans un dict à tout moment, mais en fait un dict peut avoir plusieurs éléments avec le même hash.

c, d = C(), C()
x = {c: 'c', d: 'd'}
print(x)
# {<__main__.C object at 0x7f0824087b80>: 'c', <__main__.C object at 0x7f0823ae2d60>: 'd'}
# notez que le dict a 2 éléments

J'ai expérimenté un peu plus et j'ai trouvé que si je redéfinis la méthode __eq__ de telle sorte que toutes les instances de la classe se comparent égales, alors le dict n'autorise qu'une seule instance.

class D:
    def __hash__(self):
        return 42
    def __eq__(self, other):
        return True

p, q = D(), D()
y = {p: 'p', q: 'q'}
print(y)
# {<__main__.D object at 0x7f0823a9af40>: 'q'}
# notez que le dict a seulement 1 élément

Je suis curieux de savoir comment un dict peut avoir plusieurs éléments avec le même hash.

Answer 1

Voici tout ce que j'ai pu rassembler sur les dictionnaires Python (probablement plus que quiconque voudrait savoir; mais la réponse est exhaustive). Un grand merci à Duncan pour avoir souligné que les dictionnaires Python utilisent des emplacements (slots) et m'avoir conduit dans ce terrier de lapin.

• Les dictionnaires Python sont implémentés comme des tables de hachage.

• Les tables de hachage doivent permettre des collisions de hachage 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 clé-valeur de manière non équivoque.

• Les dict Python utilisent un adressage ouvert pour résoudre les collisions de hachage (expliqué ci-dessous) (voir dictobject.c:296-297).

• La table de hachage Python est juste un bloc de mémoire contigu (un peu comme un tableau, donc vous pouvez faire une recherche O(1) par indice).

• Chaque emplacement dans la table peut stocker une seule et unique entrée. C'est important.

• Chaque entrée dans la table est en fait une combinaison des trois valeurs - . Cela est implémenté sous forme de struct 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 les indices des emplacements dans la table de hachage (ils sont simplement à des fins illustratives et ne sont pas stockés avec la table évidemment!).

  # Modèle logique de la table de hachage Python
  -+-----------------+
  0| |
  -+-----------------+
  1|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  i|      ...        |
  -+-----------------+
  .|      ...        |
  -+-----------------+
  n|      ...        |
  -+-----------------+

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

• Lors de l'ajout d'entrées dans la table, nous commençons avec un emplacement, i, qui est basé sur le hachage de la clé. CPython utilise i = hash(clé) & masque au début. Où masque = PyDictMINSIZE - 1, mais ce n'est pas vraiment important). Remarquez 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, ). Mais que se passe-t-il 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 comparaison, je veux dire comparaison == pas la comparaison is) de l'entrée dans l'emplacement avec la clé de l'entrée actuelle à insérer (dictobject.c:337,344-345). Si les deux correspondent, alors il considère 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.

• Sonder signifie simplement qu'il recherche les emplacements un par un pour trouver un emplacement vide. Techniquement, nous pourrions juste aller un par un, i+1, i+2, ... et utiliser le premier disponible (c'est 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. Dans le sondage aléatoire, le prochain emplacement est choisi 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 le prochain emplacement n'est pas vraiment important (voir dictobject.c:33-126 pour l'algorithme de sondage). Ce qui est important, c'est que les emplacements sont sondés jusqu'à ce qu'un emplacement vide soit trouvé.

• La même chose se produit pour les recherches, simplement en commençant par l'emplacement initial i (où i dépend du hachage de la clé). Si le hachage et la clé ne correspondent pas à ceux de l'entrée dans l'emplacement, il commence à sonder jusqu'à ce qu'il trouve un emplacement correspondant. Si tous les emplacements sont épuisés, il signale un échec.

• Au fait, le dictionnaire sera redimensionné s'il est rempli aux deux tiers. Cela évite de ralentir les recherches. (voir dictobject.h:64-65)

Et voilà ! L'implémentation Python des dictionnaires vérifie à la fois l'égalité de hachage de deux clés et l'égalité normale (==) des clés lors de l'insertion d'éléments. En résumé, s'il existe deux clés, a et b et hash(a)==hash(b), mais a!=b, alors les deux peuvent coexister harmonieusement dans un dictionnaire Python. Mais si hash(a)==hash(b) et a==b, alors ils ne peuvent pas tous deux être dans le même dictionnaire.

En raison du sondage 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 lentes (comme Duncan le souligne dans les commentaires).

Je suppose que la réponse courte à ma question est : "Parce que c'est ainsi que c'est implémenté dans le code source ;)"

Alors que c'est bon à savoir (pour des points de geek?), je ne suis pas sûr de comment cela peut être utilisé dans la vraie vie. Parce que à moins de chercher explicitement à casser quelque chose, pourquoi deux objets qui ne sont pas égaux auraient le même hachage ?

Answer 2

Pour une description détaillée de comment fonctionne le hachage en Python, consultez ma réponse à Pourquoi le retour anticipé est-il plus lent que le else ?

Fondamentalement, il utilise le hachage pour choisir un emplacement dans la table. S'il y a une valeur dans l'emplacement et que le hachage correspond, il compare les éléments pour voir s'ils sont égaux.

Si le hachage correspond mais que les éléments ne sont pas égaux, alors il essaye un autre emplacement. Il y a une formule pour choisir cela (que je décris dans la réponse référencée), et elle tire progressivement les parties inutilisées de la valeur de hachage ; mais une fois qu'elle les a toutes utilisées, elle finira par passer par tous les emplacements de la table de hachage. Cela garantit qu'à un moment donné, nous trouvons soit un élément correspondant, soit un emplacement vide. Lorsque la recherche trouve un emplacement vide, elle insère la valeur ou abandonne (en fonction de si nous ajoutons ou obtenons une valeur).

La chose importante à noter est qu'il n'y a pas de listes ou de seaux : il y a juste une table de hachage avec un nombre spécifique d'emplacements, et chaque hachage est utilisé pour générer une séquence d'emplacements candidats.

Answer 3

Modifier : la réponse ci-dessous est l'une des façons possibles de gérer les collisions de hachage, ce n'est cependant pas la façon dont 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: https://github.com/python/cpython/blob/master/Objects/dictobject.c Je m'excuse pour la confusion.

---

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

Ici, vous voyez John Smith et Sandra Dee qui se hachent tous les deux en 152. Le seau 152 les contient tous les deux. Lors de la recherche de Sandra Dee, il trouve d'abord la liste dans le seau 152, puis parcourt cette liste jusqu'à ce que Sandra Dee soit trouvée et renvoie 521-6955.

La suite est incorrecte, elle est uniquement là pour le contexte: Sur le wiki de Python, vous pouvez trouver un code (pseudo ?) sur comment Python effectue la recherche.

Il existe en réalité 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

Answer 4

Les tables de hachage, en général, doivent permettre les collisions de hachage! Vous aurez de la malchance et deux choses finiront par être hachées à 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. Habituellement, il n'y a qu'une seule chose dans cette liste, mais dans ce cas, ils continueront à s'empiler dans la même. La seule façon de savoir qu'ils sont différents est à travers l'opérateur equals.

Quand cela se produit, vos performances se dégraderont au fil du temps, c'est pourquoi vous voulez que votre fonction de hachage soit aussi "aléatoire que possible".

Answer 5

Dans le fil, je n'ai pas vu ce que python fait exactement avec les instances de classes définies par l'utilisateur lorsque nous les mettons dans un dictionnaire en tant que clés. Lisons un peu de documentation: il déclare que seuls les objets hashables peuvent être utilisés comme clés. Les objets hashables sont toutes les classes intégrées immuables et toutes les classes définies par l'utilisateur.

Les classes définies par l'utilisateur ont par défaut des méthodes __cmp__() et __hash__(); avec elles, tous les objets sont inégaux (sauf avec eux-mêmes) et x.__hash__() renvoie un résultat dérivé de id(x).

Donc, si vous avez constamment __hash__ dans votre classe, mais que vous ne fournissez aucune méthode __cmp__ ou __eq__, alors toutes vos instances sont inégales pour le dictionnaire. D'autre part, si vous fournissez une méthode __cmp__ ou __eq__, mais que vous ne fournissez pas __hash__, vos instances sont toujours 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}