Comment Python calcule le hash d'un tuple

Question

En python, si j'ai un tuple avec de nombreux éléments, son hash est-il calculé à partir des id de ses éléments ou du contenu de ses éléments ?

Dans cet exemple,

a = (1, [1,2])
hash(a)

Une erreur se produit en disant que la liste est non-hashable. Je suppose donc que ce n'est pas calculé par id, ou qu'il y a probablement une vérification pour déterminer si l'élément est mutable.

Maintenant, voyez cet exemple

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Ici, il s'avère que le hash de ta ne change pas avec la modification de son élément, c'est-à-dire a0. Peut-être que l'id de a0 est utilisé pour le calcul du hash ? a0 est-il d'une certaine manière considéré comme immutable ? Comment python sait-il si un type est mutable ?

Considérons maintenant ce cas

b = (1, 2)
id(b)  # 3980742764
c = (1, 2)
id(c)  # 3980732588
tb = (1, b)
tc = (1, c) 
hash(tb)  # -1383040070
hash(tc)  # -1383040070

Il semble que le contenu de b et c est utilisé pour le calcul du hash.

Comment devrais-je interpréter ces exemples ?

Answer 1

Si j'ai un tuple avec de nombreux éléments, son hachage est-il calculé à partir des IDs de ses éléments ou du contenu de ses éléments?

Aucun des deux. Il est calculé sur la base des hachages de ces éléments, pas sur leur "contenu" (valeurs/attributs), ni sur leurs IDs.

---

Les bases : pourquoi les hachages sont utilisés de cette manière

Jetez un œil à ce paragraphe dans la glossaire de documentation de Python.

Que quelque chose soit hashable ou non, et comment il est hashé, dépend de l'implémentation de sa méthode __hash__(). En soi, Python n'a aucune idée de la mutabilité d'un objet.

Un hachage est utile pour l'identification des objets. Par exemple, il accélère la récupération des données à partir d'un dict, identifiant la valeur arbitraire d'une clé par une seule valeur numérique dans un intervalle fini - le hachage de la clé.

Un hachage devrait rester inchangé tout au long de la durée de vie de l'objet. Sinon, un objet pourrait être associé à deux valeurs différentes dans un dict, ou être inclus dans un set deux fois, dès que son hachage change.

Il ne suffit pas de comparer deux objets par leurs hachages : à la fin de la journée, vous pourriez quand même avoir besoin d'effectuer des vérifications d'égalité, car il peut y avoir une collision entre les hachages de différents objets. C'est pourquoi les objets hashables doivent avoir __eq__() implémenté.

Cela ramène à la mutabilité : si un objet hashable mute de manière à modifier les comparaisons d'égalité avec des objets hashables, en particulier ceux avec le même hachage - il rompt le contrat, et pourrait entraîner les mêmes bizarreries qu'un hachage muté. Les objets hashables ne doivent pas modifier les comparaisons entre eux.

Des objets hashables qui sont égaux les uns aux autres devraient avoir le même hachage. Cet accord général rend tout le reste plus simple - il est naturel de supposer que x == y implique que à la fois x et y se mappent à la même valeur dans un dict.

---

Hachage d'un tuple

Prenons votre premier exemple. Le tuple se hache lui-même sur la base de ses éléments, alors que son deuxième élément, la list, n'a pas de hachage du tout - la méthode __hash__ n'est pas implémentée pour elle. Ainsi, la méthode tuple.__hash__ échoue.

C'est pourquoi un tuple avec un objet list à l'intérieur n'est pas hashable. Comme vous le voyez, il est donc également incorrect de dire qu'un hachage de tuple est basé sur les IDs de ses éléments.

Remarquez que si la list était hashable ici, et que le hachage était basé sur ses éléments, les changer modifierait le hachage du tuple extérieur, rompant le contrat.

---

Pourquoi ma classe personnalisée ne nécessite pas de __hash__() ?

Jetons un œil à la documentation du modèle de données Python, et ce qu'elle a à dire sur le sujet :

Les classes définies par l'utilisateur ont par défaut les méthodes __eq__() et __hash__() ; avec elles, tous les objets se comparent de manière différente (sauf avec eux-mêmes) et x.__hash__() renvoie une valeur appropriée telle que x == y implique à la fois que x est y et que hash(x) == hash(y).

En somme, l'implémentation par défaut compare l'identité des objets, qui n'a rien à voir avec les attributs de l'objet. C'est pourquoi vous pouvez changer les valeurs "à l'intérieur" de l'objet de votre classe personnalisée sans modifier son hachage.

C'est aussi pourquoi vous n'avez pas à définir __hash__() pour vos classes - Python le fait pour vous dans ce cas.

À cet égard, vous avez raison - l'implémentation par défaut (de CPython) de la fonction de hachage pour les classes personnalisées repose sur le id() d'un objet (et non sur les valeurs "à l'intérieur" de celui-ci). Il s'agit d'un détail d'implémentation, et cela diffère selon les versions de Python.

Dans les versions récentes de Python, la relation entre hash() et id() implique de la randomisation. Cela empêche certains types d'attaques par déni de service, où la création de collisions de hachage arbitraires pourrait ralentir considérablement les applications web. Voir PEP-456.

---

Comment se hache-t-il en réalité ?

Alors que les détails sont assez compliqués et impliquent probablement des mathématiques avancées, l'implémentation de la fonction de hachage pour les objets tuple est écrite en C, et peut être consultée ici (voir static Py_hash_t tuplehash(PyTupleObject *v)).

Le calcul implique un XOR d'une constante avec les hachages de chacun des éléments du tuple. La ligne responsable du hachage des éléments est la suivante :

y = PyObject_Hash(*p++);

---

Donc, pour répondre à votre question initiale : il réalise une sorte de tour de magie XOR avec les hachages de chacun de ses éléments. Le fait que les contenus et les attributs de ces éléments soient pris en compte ou non dépend de leurs fonctions de hachage spécifiques.

Answer 2

Le contrat de base du hachage est que les objets égaux ont des hachages égaux. En particulier, le hachage ne se préoccupe pas directement de la mutabilité ou de la mutation; il se soucie uniquement de la mutation qui affecte les comparaisons d'égalité.

---

Votre premier tuple est non hachable car la mutation de la liste imbriquée modifierait le comportement du tuple dans les comparaisons d'égalité.

La mutation de a0 dans votre deuxième exemple n'affecte pas le hachage du tuple car elle n'affecte pas les comparaisons d'égalité. a0 est toujours seulement égal à lui-même, et son hachage reste inchangé.

tb et tc dans votre troisième exemple ont des hachages égaux car ce sont des tuples égaux, peu importe si leurs éléments sont les mêmes objets.

---

Tout cela signifie que les tuples ne peuvent pas utiliser directement id pour les hachages. Si c'était le cas, des tuples égaux avec des éléments distincts mais égaux pourraient avoir des hachages différents, violant le contrat de hachage. Sans prendre en compte les types d'éléments, les seules choses que les tuples peuvent utiliser pour calculer leurs propres hachages sont les hachages de leurs éléments, donc les tuples basent leurs hachages sur les hachages de leurs éléments.

Answer 3

La réponse à la question "Le hachage du tuple est-il calculé en fonction de l'identité ou de la valeur ?" est : Ni l'un ni l'autre.

La bonne réponse est que le hachage du tuple est calculé à partir des hachages des éléments. Comment ces hachages sont calculés est (plus ou moins) sans importance.

Une façon facile de le prouver est de voir ce qui se passe lorsque vous mettez une liste dans un tuple :

>>> hash( (1, 2) )
3713081631934410656
>>> hash( (1, []) )
Traceback (most recent call last):
  File "", line 1, in 
TypeError: type non valide pour hachage: 'list'

Parce que les listes ne sont pas hachables, un tuple contenant une liste n'est pas hachable non plus.

---

Jetons un coup d'œil plus attentif à cet exemple que vous avez apporté :

class A: pass
a0 = A()
ta = (1, a0)
hash(ta)  # -1122968024
a0.x = 20
hash(ta)  # -1122968024

Pourquoi le fait de définir a0.x = 20 n'affecte pas le hachage du tuple ? Eh bien, si nous modifions ce code pour afficher le hachage de a0, vous verrez que le fait de définir a0.x = 20 n'a aucun effet sur la valeur de hachage de a0 :

a0 = A()
print(hash(a0))  # -9223363274645980307
a0.x = 20
print(hash(a0))  # -9223363274645980307

La raison en est que Python implémente une fonction de hachage par défaut pour vous. Selon la documentation :

Les classes définies par l'utilisateur ont par défaut les méthodes __eq__() et __hash__(); avec elles, tous les objets se comparent de manière inégale (sauf avec eux-mêmes) et x.__hash__() renvoie une valeur appropriée telle que x == y implique à la fois que x is y et hash(x) == hash(y).

La fonction de hachage par défaut ignore les attributs de l'objet et calcule le hachage en fonction de l'identifiant de l'objet. Peu importe les modifications apportées à a0, son hachage restera toujours le même. (Bien qu'il soit possible de définir une fonction de hachage personnalisée pour les instances de votre classe A en implémentant une méthode personnalisée __hash__.)

---

Addendum : La raison pour laquelle les listes ne sont pas hachables est parce qu'elles sont mutables. Selon la documentation :

Si une classe définit des objets mutables et implémente une méthode __eq__(), elle ne doit pas implémenter __hash__(), car l'implémentation de collections hachables nécessite qu'une valeur de hachage de clé soit immuable (si la valeur de hachage de l'objet change, elle sera dans le mauvais compartiment de hachage).

Les listes entrent dans cette catégorie.

Answer 4

Le hachage d'un tuple est basé sur le contenu, pas sur les _id_s des tuples. Et les hachages sont calculés de manière récursive : si un élément n'est pas hachable (comme un élément de list), alors le tuple lui-même n'est pas hachable.

Il est parfaitement normal que si a et b sont des tuples et a == b, alors hash(a) == hash(b) (si les hachages peuvent être calculés bien sûr), même si a is not b.

(au contraire, hash(a) == hash(b) ne signifie pas que a == b)

Les informations transmises par is ne sont souvent pas très utiles, en raison de l'internage des objets Python par exemple.