Comment python calculer la valeur de hachage d'un tuple
en python, Si j'ai un tuple avec beaucoup d'éléments, est son hachage calculé à partir de ses éléments' id s ou le contenu de ses éléments?
Dans cet exemple,
a = (1, [1,2])
hash(a)
C'est une erreur de dire la liste est unhashable. Donc je suppose que ce n'est pas calculé par id, ou probablement il y a une vérification sur si l'élément est mutable.
voir maintenant 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 hachage de l' ta ne change pas avec la modification de son élément, c'est à dire, a0. Alors peut-être a0'id est utilisé pour le calcul de hachage? a0 d'une façon ou d'une autre considérée comme immuable? Comment python savoir si un type est muable?
maintenant, considérez 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 sont utilisés pour le calcul du hachage.
Comment dois-je comprendre ces exemples?
4 réponses
ni l'un ni l'autre. Il est calculé sur la base des hachures de ces éléments, et non du contenu (valeurs).
jetez un coup d'oeil à ce paragraphe dans python documentation glossaire.
Si quelque chose hashable ou pas, et comment il est hashé, dépend de la mise en oeuvre de son .__hash__() méthode. Python lui-même n'a aucune idée sur la mutabilité d'un objet.
dans votre premier exemple,tuple se produit pour se Hasher sur la base de ses éléments, alors qu'un list ne pas avoir un hachage à tous - l' .__hash__() méthode n'est pas implémentée pour elle (et pour une bonne raison). C'est pourquoi un tuple avec un list objet à l'intérieur de celui-ci n'est pas hashable.
Maintenant, ayant cela à l'esprit, nous allons jeter un coup d'oeil à python, modèle de données de la documentation, et ce qu'il a à dire sur le sujet:
les classes définies par L'Utilisateur ont
__eq__()et__hash__()méthodes par défaut; eux, tous les objets comparent inégal (sauf avec eux - mêmes) etx.__hash__()renvoie une valeur appropriée telle quex == yimplique à la fois quex is yethash(x) == hash(y).
C'est pourquoi vous n'avez pas à définir .__hash__() pour vos cours-python le fait pour vous dans ce cas. L'implémentation par défaut ne prend pas des champs d'instance dans le compte. C'est pourquoi vous pouvez modifier les valeurs à l'intérieur de votre objet sans modifier son hachage.
À cet égard, vous êtes droit - la valeur par défaut (Disponible) la mise en œuvre de la fonction de hachage pour les classes personnalisées repose sur le id() d'un objet, et non pas sur les valeurs à l'intérieur de celui-ci. C'est un détail d'implémentation, et il diffère entre les versions de Python. Dans les versions plus récentes de Python la relation entre hash() et id() implique une certaine randomisation.
mais comment est-ce que cela se hash réellement?
alors que les détails sont assez compliquées et impliquent probablement quelques mathématiques avancées, l'implémentation de la fonction de hachage pour les objets tuple est écrite en C, et peut être vue ici (voir static Py_hash_t tuplehash(PyTupleObject *v).
le calcul consiste à Xorner une constante avec les hachures de chacun des éléments du tuple. La ligne responsable du hachage des éléments est celle-ci:
y = PyObject_Hash(*p++);
donc, pour répondre à votre question originale: il fait un tas de XOR Hokus-pocus avec le hachages de chacun de ses éléments. Que le contenu de ces éléments soit ou non utilisé dépend de leurs fonctions de hachage spécifiques.
le contrat de base du hachage est que les objets égaux ont des hachures égales. En particulier, hashing ne se soucie pas directement de la mutabilité ou de la mutation; il se soucie seulement de mutation qui affecte les comparaisons d'égalité.
votre premier tuple est indéchiffrable parce que la mutation de la liste imbriquée changerait le comportement du tuple dans les comparaisons d'égalité.
la Mutation a0 dans votre deuxième exemple n'affecte pas le hachage de le tuple parce qu'il n'affecte pas les comparaisons d'égalité. a0 est encore seulement égal à lui-même, et son hachage est inchangé.
tb et tc dans votre troisième exemple ont des hachures égales parce qu'ils sont des tuples égaux, indépendamment du fait que leurs éléments soient les mêmes objets.
cela signifie que tuples ne peut pas (directement) utiliser id pour les tables de hachage. S'ils l'ont fait, les tuples égaux avec des éléments distincts mais égaux pourraient hachés différemment, violant le contrat de hachage. Sans les types d'éléments de boîtier Spéciaux, les seules choses que les tuples peuvent utiliser pour calculer leurs propres hashes sont les hashes de leurs éléments, donc les tuples basent leurs hashes sur les hashes de leurs éléments.
la réponse à la question "le hachage du tuple est-il calculé sur la base de l'identité ou de la valeur?"est: Ni.
la bonne réponse est que le hachage du tuple est calculé à partir des hachages des éléments. Comment ceux les hachages sont calculés est (plus ou moins) sans importance.
un moyen facile de prouver ceci est de voir ce qui se passe quand vous mettez une liste dans un tuple:
>>> hash( (1, 2) )
3713081631934410656
>>> hash( (1, []) )
Traceback (most recent call last):
File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
parce que les listes ne sont pas hachables, un tuple contenant une liste n'est pas hashable.
regardons de plus près cet exemple que vous avez apporté:
class A: pass
a0 = A()
ta = (1, a0)
hash(ta) # -1122968024
a0.x = 20
hash(ta) # -1122968024
Pourquoi ne pas la configuration de a0.x = 20 affecter le hash du tuple? Eh bien, si nous modifions ce code pour afficher le hachage de a0, vous verrez que la configuration de a0.x = 20 n'a aucun effet sur a0'la valeur de hachage:
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. À partir de la documentation:
les classes définies par L'Utilisateur ont
__eq__()et__hash__()méthodes par défaut; avec eux, tous les objets comparent inégal (sauf avec eux-mêmes) etx.__hash__()renvoie une valeur appropriée telle quex == yimplique tant quex is yethash(x) == hash(y).
la fonction de hachage par défaut ignore les attributs de l'objet et calcule le hachage basé sur l'id de l'objet. Peu importe les changements que vous faites à a0, son hachage restera toujours la même. (Si c'est possible de définissez une fonction de hachage personnalisée pour les instances de votre A classe par la mise en œuvre d'un custom __hash__ méthode.)
Addendum: la raison pour laquelle les listes ne sont pas hachables est qu'elles sont mutables. À partir de la documentation:
si une classe définit des objets mutables et implémente un
__eq__()méthode, il ne devrait pas mettre en œuvre__hash__(), depuis la mise en œuvre de hashable collections exige que la valeur de hachage d'une clé soit immuable (si la valeur de hachage de l'objet change, il sera dans le mauvais seau de hachage).
les listes entrent dans cette catégorie.
le hachage d'un tuple est basé sur le table des matières, pas sur les id_s des tuples. Et les hachages sont calculés récursivement: si un élément n'est pas hachable (comme un list element), alors le tuple lui-même n'est pas hachable.
c'est parfaitement normal que si a et b sont des n-uplets et a == b, puis hash(a) == hash(b) (si les hash peuvent être calculés bien sûr), même si a is not b.
(au contraire hash(a) == hash(b) ne veut pas dire que a == b)
L'information véhiculée par is n'est souvent pas très utile, à cause de Python object interning par exemple.