Hash für Lambda-Funktion in Python

Question

Ich versuche, den Hash einer Lambda-Funktion zu bekommen. Warum bekomme ich zwei Werte (8746164008739 und -9223363290690767077)? Warum ist der Hash der Lambda-Funktion nicht immer ein Wert?

>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 
>>> fn = lambda: 1 
>>> hash(fn) 
8746164008739 
>>> fn = lambda: 1 
>>> hash(fn) 
-9223363290690767077 

Answer 1

Bei zwei Objekten wird nicht garantiert, dass sie auf den gleichen Wert synchronisiert werden, es sei denn, sie vergleichen [1].

Python-Funktionen (einschließlich lambdas) vergleichen nicht gleich, auch wenn sie den gleichen Code haben [2]. Zum Beispiel:

>>> (lambda: 1) == (lambda: 1) 
False 

Implementierungsweise ist dieses Verhalten auf die Tatsache zurückzuführen, dass Funktionsobjekte ihren eigenen Gleichheitsoperator nicht bereitstellen. Stattdessen erben sie den Standardnamen, der die Identität des Objekts verwendet, d. H. Seine Adresse. Von den documentation:

Wenn kein __cmp__(), __eq__() oder __ne__() Betrieb definiert ist, Klasse Instanzen von Objektidentität verglichen („Adresse“).

Hier ist, was in Ihrem speziellen Beispiel passiert:

fn = lambda: 1 # New function is allocated at address A and stored in fn. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
fn = lambda: 1 # New function is allocated at address A and stored in fn. 
       # The function at address B is garbage collected. 
fn = lambda: 1 # New function is allocated at address B and stored in fn. 
       # The function at address A is garbage collected. 
... 

Da Adresse A immer auf einen Wert gehasht wird, und die Adresse B zum anderen, Sie hash(fn) wechseln zwischen den beiden Werten sehen. Dieses alternierende Verhalten ist jedoch ein Implementierungsartefakt und könnte sich eines Tages ändern, wenn beispielsweise der Garbage Collector etwas anders verhalten würde.

Die folgende interessante Notiz wird von @ruakh beigetragen worden:

Es ist erwähnenswert, dass es nicht möglich ist äquivalent ein allgemeines Verfahren zu bestimmen, ob zwei Funktionen zu schreiben. (Dies ist eine Folge der undecidability der halting problem.) Darüber hinaus kann zwei Python-Funktionen anders verhalten können, selbst wenn ihr Code identisch ist (da sie Verschlüsse sein können mit Bezug distinct-but-gleichnamigen Variablen). Es macht also Sinn, dass Python-Funktionen den Gleichheitsoperator nicht überlasten: Es gibt keine Möglichkeit, etwas besser als die Standard-Objektidentität Vergleich zu implementieren.

[1] Die Umkehrung ist im Allgemeinen nicht wahr: Zwei Objekte, die ungleich vergleichen, können denselben Hash-Wert haben. Dies wird hash collision genannt. würde natürlich immer geben den gleichen Wert, da hash(1) ist immer gleich innerhalb eines Programms

[2] Aufruf Ihre lambdas und dann das Ergebnis Hashing:

>>> (lambda: 1)() == (lambda: 1)() 
True 

Answer 2

Der Hash einer lambda Funktionsobjekt ist basierend auf seiner Speicheradresse (in CPython ist dies, was die id Funktion zurückgibt). Das bedeutet, dass zwei beliebige Funktionsobjekte unterschiedliche Hashes haben (vorausgesetzt, es gibt keine Hash-Kollisionen), selbst wenn die Funktionen denselben Code enthalten.

Um zu erklären, was in der Frage passiert, beachten Sie zuerst, dass das Schreiben fn = lambda: 1 ein neues Funktionsobjekt im Speicher erstellt und den Namen fn daran bindet. Diese neue Funktion wird daher einen anderen Hash-Wert als alle bestehenden Funktionen haben.

Wiederholung fn = lambda: 1, erhalten Sie abwechselnd Werte für die Hash-Werte, weil, wenn fn zum neu geschaffenen Funktion Objekt gebunden ist, die Funktion, dass fnzuvor zeigte Müll wird von Python gesammelt. Dies liegt daran, dass es keine Referenzen mehr gibt (da der Name fn jetzt auf ein anderes Objekt zeigt).

Der Python-Interpreter verwendet dann diese alte Speicheradresse für das nächste neue Funktionsobjekt, das durch Schreiben von fn = lambda: 1 erstellt wurde.

Dieses Verhalten kann zwischen verschiedenen Systemen und Python-Implementierungen variieren.

Answer 3

Jedes Mal, wenn Sie fn = lambda: 1 tun, wird ein neues Funktionsobjekt erstellt, und das alte Objekt, das an den Namen fn gebunden ist, wird zum Löschen markiert. Python entpackt das Objekt jedoch nicht einfach und gibt seinen Speicher an das Betriebssystem zurück. Um die Systemaufrufe für die Speicherzuweisung zu minimieren und die Speicherfragmentierung zu minimieren, versucht Python, Speicher nach Möglichkeit zu recyceln. Und wenn Sie also ein drittes Mal fn = lambda: 1 erstellen, merkt der Interpreter, dass er einen Block RAM hat, der groß genug für das neue Funktionsobjekt ist und diesen Block verwendet. Und so landet Ihre 3. fn in diesem Block von RAM und hat daher die gleiche ID wie die erste fn, da die ID der CPython-Objekte ihre Speicheradresse ist.

(Wie andere haben den Hash von jedem Objekttyp erwähnt, die nicht eine spezifische Implementierung von __hash__ bereitstellt in CPython auf seiner ID basiert. Und wenn eine Klasse eine __cmp__ oder __eq__ Methode nicht definiert ist es nicht definieren sollte __hash__ Operation entweder).

Answer 4

Die Entscheidung, ob zwei Funktionen gleich sind, ist unmöglich, da es eine Übermenge des Halteproblems ist.

In einer idealen Welt würde das Vergleichen (und damit das Hashing) zu einem Typfehler führen. Python scheint das nicht zu mögen und wählt stattdessen die Identität der Funktionen, um sie zu vergleichen (und damit zu hashen).