Warum und wie sind Python-Funktionen hashbar?

Question

ich die folgenden Befehle in Python vor kurzem versucht:

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

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

Der Erfolg beider dict Kreationen, die Funktionen hashable beide Lambda und regelmäßig an. (Etwas wie {[]: 'a'} schlägt mit TypeError: unhashable type: 'list' fehl).

Der Hash ist offenbar nicht unbedingt die ID der Funktion:

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

Der letzte Befehl zeigt, dass die __hash__ Methode explizit für lambda s definiert ist, das heißt, dies ist nicht irgendein automagischen Sache berechnet auf Python basiert der Typ.

Was ist die Motivation, Funktionen funktionsfähig zu machen? Für einen Bonus, was ist der Hash einer Funktion?

Answer 1

Es ist nichts besonderes. Wie Sie sehen können, wenn Sie die ungebundene __hash__ Methode des Typs Funktion prüfen:

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

der of 'object' objects Teil bedeutet, es erbt nur die Standardidentitätsbasierte __hash__ von object. Funktion == und hash arbeiten nach Identität. Der Unterschied zwischen id und hash ist für jede Art normal, dass object.__hash__ erbt:

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

---

Man könnte denken, __hash__ ist nur für unveränderliche Objekte definiert werden soll, und Sie würden fast richtig, aber das fehlt ein Schlüsseldetail. __hash__ sollte nur für Objekte definiert werden, wo alles beteiligt == Vergleiche ist unveränderlich. Für Objekte, deren == auf Identität basiert, ist es völlig normal, hash auch auf Identität zu basieren, da selbst wenn die Objekte veränderbar sind, sie unmöglich so veränderbar sein können, dass sich ihre Identität ändert. Dateien, Module und andere veränderbare Objekte mit identitätsbasiertem == verhalten sich alle so.

Answer 2

Eine Funktion ist hashbar, weil es ein normales, eingebautes, nicht veränderbares Objekt ist.

Vom Python Manual:

An object is hashable if it has a hash value which never changes during its lifetime (it needs a __hash__() method), and can be compared to other objects (it needs an __eq__() or __cmp__() method). Hashable objects which compare equal must have the same hash value.

Hashability makes an object usable as a dictionary key and a set member, because these data structures use the hash value internally.

All of Python’s immutable built-in objects are hashable, while no mutable containers (such as lists or dictionaries) are. Objects which are instances of user-defined classes are hashable by default; they all compare unequal (except with themselves), and their hash value is derived from their id() .

Answer 3

Es kann nützlich sein, zum Beispiel zu erstellen Sätze von Funktionsobjekten oder ein dict von Funktionen zu indizieren. Unveränderliche Objekte normalerweise Unterstützung __hash__. In jedem Fall gibt es keinen internen Unterschied zwischen einer Funktion, die durch def definiert wird, oder einer lambda - das ist rein syntaktisch.

Der verwendete Algorithmus hängt von der Version von Python ab. Anscheinend verwenden Sie eine aktuelle Version von Python auf einer 64-Bit-Box. In diesem Fall ist der Hash eines Funktionsobjekts die richtige Drehung seiner um 4 Bits, wobei das Ergebnis als 64-Bit-Ganzzahl mit Vorzeichen angezeigt wird. Die Verschiebung nach rechts erfolgt, weil Objektadressen (Ergebnisse) typischerweise so ausgerichtet sind, dass ihre letzten 3 oder 4 Bits immer 0 sind, und das ist eine leicht störende Eigenschaft für eine Hash-Funktion.

In Ihrem speziellen Beispiel

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