Hashable, unveränderlich

Aufgrund einer kürzlich durchgeführten SO-Frage (siehe Erstellen eines Wörterbuchs in Python, das durch Listen indiziert ist ) wurde mir klar, dass ich wahrscheinlich eine falsche Vorstellung von der Bedeutung von hashbaren und unveränderlichen Objekten in Python hatte.

• Was bedeutet Hashable in der Praxis?
• Wie ist die Beziehung zwischen hashable und unveränderlich?
• Gibt es veränderbare Objekte, die hashbar sind, oder unveränderliche Objekte, die nicht hashbar sind?

Beim Hashing werden einige große Datenmengen auf wiederholbare Weise in eine viel kleinere Datenmenge (normalerweise eine einzelne Ganzzahl) konvertiert, damit sie in konstanter Zeit ( O(1)) in einer Tabelle nachgeschlagen werden können , was für eine hohe Leistung wichtig ist Algorithmen und Datenstrukturen.

Unveränderlichkeit ist die Idee, dass sich ein Objekt nach seiner Erstellung nicht auf eine wichtige Weise ändert, insbesondere nicht auf eine Weise, die den Hash-Wert dieses Objekts ändern könnte.

Die beiden Ideen hängen zusammen, da Objekte, die als Hash-Schlüssel verwendet werden, normalerweise unveränderlich sein müssen, damit sich ihr Hash-Wert nicht ändert. Wenn es erlaubt wäre, sich zu ändern, würde sich die Position dieses Objekts in einer Datenstruktur wie einer Hashtabelle ändern, und dann wird der gesamte Zweck des Hashing aus Effizienzgründen zunichte gemacht.

Um die Idee wirklich zu verstehen, sollten Sie versuchen, Ihre eigene Hashtabelle in einer Sprache wie C / C ++ zu implementieren, oder die Java-Implementierung der HashMapKlasse lesen .

• Gibt es veränderbare Objekte, die hashbar sind, oder unveränderliche Objekte, die nicht hashbar sind?

In Python ist Tupel unveränderlich, aber nur dann hashbar, wenn alle Elemente hashbar sind.

>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'

Hashbare Typen

• Die atomar unveränderlichen Typen sind alle hashbar, wie z. B. str, bytes und numerische Typen
• Ein eingefrorener Satz ist immer hashbar (seine Elemente müssen per Definition hashbar sein)
• Ein Tupel ist nur hashbar, wenn alle seine Elemente hashbar sind
• Benutzerdefinierte Typen können standardmäßig gehasht werden, da ihr Hashwert ihre id () ist.

Aus dem Python-Glossar :

Ein Objekt ist hashbar, wenn es einen Hashwert hat, der sich während seiner Lebensdauer nie ändert (es benötigt eine __hash__()Methode) und mit anderen Objekten verglichen werden kann (es benötigt eine __eq__()oder __cmp__()Methode). Hashbare Objekte, die gleich sind, müssen denselben Hashwert haben.

Durch die Hashability kann ein Objekt als Wörterbuchschlüssel und als festgelegtes Element verwendet werden, da diese Datenstrukturen den Hashwert intern verwenden.

Alle unveränderlichen integrierten Objekte von Python sind hashbar, während keine veränderlichen Container (wie Listen oder Wörterbücher) vorhanden sind. Objekte, die Instanzen benutzerdefinierter Klassen sind, können standardmäßig gehasht werden. Sie alle vergleichen sich ungleich und ihr Hash-Wert ist ihre ID ().

Dicts und Sets müssen einen Hash für eine effiziente Suche in einer Hash-Tabelle verwenden. Die Hash-Werte müssen unveränderlich sein, da das Ändern des Hash die Datenstrukturen durcheinander bringt und dazu führt, dass das Diktat oder Set fehlschlägt. Der einfachste Weg, den Hash-Wert unveränderlich zu machen, besteht darin, das gesamte Objekt unveränderlich zu machen, weshalb die beiden häufig zusammen erwähnt werden.

Während keines der integrierten veränderbaren Objekte hashbar ist, ist es möglich, ein veränderbares Objekt mit einem Hash-Wert zu erstellen, der nicht veränderbar ist. Es ist üblich, dass nur ein Teil des Objekts seine Identität darstellt, während der Rest des Objekts Eigenschaften enthält, die sich frei ändern können. Solange der Hashwert und die Vergleichsfunktionen auf der Identität, aber nicht auf den veränderlichen Eigenschaften basieren und sich die Identität nie ändert, haben Sie die Anforderungen erfüllt.

Hashable bedeutet technisch gesehen, dass die Klasse definiert __hash__(). Laut den Dokumenten:

__hash__()sollte eine ganze Zahl zurückgeben. Die einzige erforderliche Eigenschaft ist, dass Objekte, die gleich sind, denselben Hashwert haben. Es wird empfohlen, die Hash-Werte für die Komponenten des Objekts, die auch beim Vergleich von Objekten eine Rolle spielen, irgendwie miteinander zu mischen (z. B. mit exklusiven oder).

Ich denke, dass für die in Python eingebauten Typen alle Hash-Typen ebenfalls unveränderlich sind.

Es wäre schwierig, aber vielleicht nicht unmöglich, ein veränderliches Objekt zu haben, das dennoch definiert ist __hash__().

Es gibt eine implizite Beziehung, auch wenn aufgrund des Zusammenspiels zwischen beiden keine explizite Beziehung zwischen unveränderlich und hashbar erzwungen wird

1. Hashbare Objekte, die gleich sind, müssen denselben Hashwert haben
2. Ein Objekt ist hashbar, wenn es einen Hashwert hat, der sich während seiner Lebensdauer nie ändert.

Hier gibt es kein Problem, es sei denn, Sie definieren neu, __eq__sodass die Objektklasse die Äquivalenz für den Wert definiert.

Sobald Sie dies getan haben, müssen Sie eine stabile Hash-Funktion finden, die immer den gleichen Wert für Objekte zurückgibt, die den gleichen Wert darstellen (z. B. wo __eq__) True zurückgibt und sich während der Lebensdauer eines Objekts nie ändert.

Es ist schwer, eine Anwendung zu finden, in der dies möglich ist. Betrachten Sie eine mögliche Klasse A, die diese Anforderungen erfüllt. Obwohl es den offensichtlichen entarteten Fall __hash__gibt, in dem eine Konstante zurückgegeben wird.

Jetzt:-

>>> a = A(1)
>>> b = A(1)
>>> c = A(2)
>>> a == b
True
>>> a == c
False
>>> hash(a) == hash(b)
True
>>> a.set_value(c)
>>> a == c
True
>>> assert(hash(a) == hash(c)) # Because a == c => hash(a) == hash(c)
>>> assert(hash(a) == hash(b)) # Because hash(a) and hash(b) have compared equal 
                                 before and the result must stay static over the objects lifetime.

Tatsächlich bedeutet dies bei der Erstellung Hash (b) == Hash (c), obwohl es nie gleich verglichen wird. Ich habe sowieso Schwierigkeiten zu sehen, um sinnvoll __hash__() für ein veränderliches Objekt zu definieren, das Vergleich nach Wert definiert.

Hinweis : __lt__, __le__, __gt__und __ge__comparsions sind davon nicht betroffen , so dass Sie immer noch eine Bestellung von hashable Objekten, wandelbar oder auf andere Weise , basierend auf ihrem Wert definieren.

Nur weil dies der Top-Hit von Google ist, gibt es eine einfache Möglichkeit, ein veränderbares Objekt hashbar zu machen:

>>> class HashableList(list):
...  instancenumber = 0  # class variable
...  def __init__(self, initial = []):
...   super(HashableList, self).__init__(initial)
...   self.hashvalue = HashableList.instancenumber
...   HashableList.instancenumber += 1
...  def __hash__(self):
...   return self.hashvalue
... 
>>> l = [1,2,3]
>>> m = HashableList(l)
>>> n = HashableList([1,2,3])
>>> m == n
True
>>> a={m:1, n:2}
>>> a[l] = 3
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unhashable type: 'list'
>>> m.hashvalue, n.hashvalue
(0, 1)

Ich habe tatsächlich eine Verwendung für so etwas gefunden, als ich eine Klasse erstellt habe, um SQLAlchemy-Datensätze in etwas für mich veränderliches und nützlicheres umzuwandeln, während ihre Hashfähigkeit für die Verwendung als Diktatschlüssel beibehalten wurde.

Unveränderlich bedeutet, dass sich das Objekt während seiner Lebensdauer nicht wesentlich verändert. Es ist eine vage, aber verbreitete Idee in Programmiersprachen.

Die Hashability unterscheidet sich geringfügig und bezieht sich auf den Vergleich.

Hashable Ein Objekt ist Hashbar, wenn es einen Hashwert hat, der sich während seiner Lebensdauer nie ändert (es benötigt eine__hash__()Methode) und mit anderen Objekten verglichen werden kann (es benötigt eine__eq__()oder__cmp__()Methode). Hashbare Objekte, die gleich sind, müssen denselben Hashwert haben.

Alle benutzerdefinierten Klassen verfügen über eine __hash__Methode, die standardmäßig nur die Objekt-ID zurückgibt. Ein Objekt, das die Kriterien für die Hashfähigkeit erfüllt, ist also nicht unbedingt unveränderlich.

Objekte einer neuen Klasse, die Sie deklarieren, können als Wörterbuchschlüssel verwendet werden, es sei denn, Sie verhindern dies, indem Sie beispielsweise von werfen __hash__

Wir könnten sagen, dass alle unveränderlichen Objekte hashbar sind, denn wenn sich der Hash während der Lebensdauer des Objekts ändert, bedeutet dies, dass das Objekt mutiert ist.

Aber nicht ganz. Stellen Sie sich ein Tupel mit einer Liste vor (veränderbar). Einige sagen, Tupel sei unveränderlich, aber gleichzeitig ist es etwas nicht hashbar (Würfe).

d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws

Hashability und Unveränderlichkeit beziehen sich auf Objektinstanz, nicht auf Typ. Beispielsweise kann ein Objekt vom Typ Tupel hashbar sein oder nicht.

In Python sind sie meistens austauschbar. Da der Hash den Inhalt darstellen soll, ist er genauso veränderlich wie das Objekt, und wenn ein Objekt geändert wird, würde der Hash-Wert ihn als Diktatschlüssel unbrauchbar machen.

In anderen Sprachen bezieht sich der Hash-Wert eher auf die 'Identität' der Objekte und nicht (notwendigerweise) auf den Wert. Somit könnte für ein veränderliches Objekt der Zeiger verwendet werden, um das Hashing zu starten. Vorausgesetzt natürlich, dass sich ein Objekt nicht im Speicher bewegt (wie es einige GC tun). Dies ist beispielsweise der in Lua verwendete Ansatz. Dadurch kann ein veränderbares Objekt als Tabellenschlüssel verwendet werden. schafft aber einige (unangenehme) Überraschungen für Neulinge.

Am Ende macht es ein unveränderlicher Sequenztyp (Tupel) für 'mehrwertige Schlüssel' schöner.

Hashable bedeutet, dass der Wert einer Variablen durch eine Konstante dargestellt (oder vielmehr codiert) werden kann - Zeichenfolge, Zahl usw. Nun kann etwas, das geändert werden kann (veränderlich), nicht durch etwas dargestellt werden, das nicht geändert wird. Daher kann jede Variable, die veränderbar ist, nicht hashbar sein, und aus dem gleichen Grund können nur unveränderliche Variablen hashbar sein.

Hoffe das hilft ...