Pourquoi et comment sont-fonctions Python hashable?

Question

Récemment, j'ai essayé les commandes suivantes en Python:

>>> {lambda x: 1: 'a'}
{<function __main__.<lambda>>: 'a'}

>>> def p(x): return 1
>>> {p: 'a'}
{<function __main__.p>: 'a'}

Le succès de ces deux dict créations indique que les deux lambda et des fonctions classiques sont hashable. (Quelque chose comme {[]: 'a'} d'échec avec TypeError: unhashable type: 'list').

Le hachage est apparemment pas nécessairement l'ID de la fonction:

>>> m = lambda x: 1
>>> id(m)
140643045241584
>>> hash(m)
8790190327599
>>> m.__hash__()
8790190327599

La dernière commande montre que l' __hash__ méthode est explicitement définie pour lambdas, c'est à dire, ce n'est pas quelque automagical chose Python calcule en fonction du type.

Quelle est la motivation derrière fonctions de prise de hashable? Pour un bonus, qu'est-ce que la valeur de hachage d'une fonction?

Answer 1

C'est rien de spécial. Comme vous pouvez le voir si vous examinez la unbound __hash__ méthode de la fonction de type:

>>> def f(): pass
...
>>> type(f).__hash__
<slot wrapper '__hash__' of 'object' objects>

l' of 'object' objects partie signifie qu'il seulement hérite de l'identité par défaut basé __hash__ de object. La fonction == et hash de travail par l'identité. La différence entre id et hash est normal pour n'importe quel type qui hérite object.__hash__:

>>> x = object()
>>> id(x)
40145072L
>>> hash(x)
2509067

---

Vous pourriez penser, __hash__ est supposé être définies pour des objets immuables, et vous auriez presque raison, mais qui manque un détail important. __hash__ ne doit être définie pour les objets où tout impliqués dans == comparaisons est immuable. Pour les objets dont == est basé sur l'identité, c'est complètement standard à base hash sur l'identité, car même si les objets sont mutables, elle ne peut pas être mutable de façon à modifier leur identité. Fichiers, les modules, et d'autres objets mutables avec identity-based == tous se comportent de cette façon.

Answer 2

Il peut être utile, par exemple, à créer des ensembles d'objets de fonction, ou d'index d'un dict par des fonctions. Des objets immuables normalement appuyer __hash__. En tout cas, il n'y a pas de différence entre une fonction définie par un def ou par un lambda - c'est purement syntaxique.

L'algorithme utilisé dépend de la version de Python. Il semblerait que vous utilisez une version récente de Python sur une version 64 bits de zone. Dans ce cas, la valeur de hachage d'une fonction d'un objet est la rotation à droite de son id() par 4 bits, le résultat considéré comme un entier signé de 64 bits. Le décalage à droite est en fait parce que l'objet d'adresses (id() des résultats) sont généralement alignés de façon à ce que leur dernier 3 ou 4 bits sont toujours à 0, et c'est une simple gêne à la propriété pour une fonction de hachage.

Dans votre exemple,

>>> i = 140643045241584 # your id() result
>>> (i >> 4) | ((i << 60) & 0xffffffffffffffff) # rotate right 4 bits
8790190327599  # == your hash() result

Answer 3

Une fonction est hashable parce que c'est un normal, builtin, non mutable objet.

À partir du Python Manuel:

Un objet est hashable si elle a une valeur de hachage qui ne change jamais au cours de sa vie (il a besoin d'un __hash__() méthode), et peut être comparé à d'autres objets (il a besoin d'un __eq__() ou __cmp__() méthode). Hashable des objets qui permettent de comparer l'égalité doit avoir la même valeur de hachage.

Hashability fait un objet utilisable comme clé de dictionnaire et d'un membre du jeu, parce que ces structures de données utiliser la valeur de hachage interne.

Tous de Python est immuable les objets intégrés sont hashable, alors qu'aucun mutable conteneurs (comme les listes ou les dictionnaires) sont. Les objets qui sont des instances de classes définies par l'utilisateur sont hashable par défaut; ils ont tous comparer inégale (à l'exception d'eux-mêmes), et leur valeur de hachage est dérivé de leur id().