Hashable, unveränderlich

Aus einer aktuellen Frage ALSO (siehe Erstellen Sie ein Wörterbuch in python, die indiziert ist, die mit Listen) ich merkte, ich hatte wohl eine falsche Vorstellung von der Bedeutung von hashable und unveränderliche Objekte, die in python.

Was bedeutet hashable in der Praxis bedeuten?
Was ist die Beziehung zwischen hashable und immmutable?
Gibt es veränderliche Objekte, die hashable oder unveränderliche Objekte, die nicht hashable?

InformationsquelleAutor joaquin | 2010-04-19

83

Hashing ist der Prozess der Umwandlung einige große Menge von Daten in einen viel kleineren Betrag (in der Regel eine einzelne Ganzzahl) in reproduzierbarer Weise, so dass es sein kann, schaute in einer Tabelle in konstanter Zeit (O(1)), die wichtig ist für die high-performance-algorithmen und Datenstrukturen.

Unveränderlichkeit ist die Idee, dass ein Objekt nicht verändern wird in einigen wichtigen Weg, nachdem es erstellt wurde, vor allem in einer Weise, die möglicherweise ändern Sie den hash-Wert des Objekts.

Beide Ideen beziehen, da Objekte, die als hash-Schlüssel müssen in der Regel unveränderlich sind, so dass deren hash-Wert ändert sich nicht. Wenn es erlaubt war, das zu ändern, dann ist die Lage des Objekts in eine Datenstruktur wie ein Hash ändern würde und dann der ganze Zweck des hashing für die Effizienz ist besiegt.

Wirklich zu begreifen die Idee, die Sie sollten versuchen, zu implementieren Ihre eigenen hashtable in einer Sprache wie C/C++, oder Lesen Sie die Java-Implementierung des HashMap Klasse.

Darüber hinaus ist es nicht möglich für hash-Tabellen zu erkennen, wenn der hash-Schlüssel ändern (in einer effizienten Art und Weise zumindest). Es ist ein häufiges Problem z.B. in Java, wo ein HashMap wird gebrochen, wenn Sie ändern ein Objekt als Schlüssel verwendet: weder der alte noch der neue Schlüssel kann gefunden werden, obwohl, wenn Sie drucken Sie die Karte, es kann es gesehen werden.
Hashable und Unveränderlich sind etwas verwandt, aber nicht identisch. E. g. Erzeugten Instanzen von benutzerdefinierten Klassen Erben object sind hashable aber nicht unveränderlich. Diese Instanzen können verwendet werden, hat die Schlüssel des dict, aber Sie können noch geändert werden, wenn Sie herum.

InformationsquelleAutor maerics
10
- Gibt es veränderliche Objekte, die hashable oder unveränderliche Objekte, die nicht hashable?
In Python Tupel unveränderlich ist, aber es ist hashable nur, wenn alle seine Elemente sind hashable.
```
>>> tt = (1, 2, (30, 40))
>>> hash(tt)
8027212646858338501
>>> tl = (1, 2, [30, 40])
>>> hash(tl)
TypeError: unhashable type: 'list'
```
Hashable Arten
- Die Atomare unveränderliche Typen sind alle hashable, wie str, bytes, numeric-Typen
- Eine frozen-set ist immer hashable(Ihre Elemente werden muss hashable per definition)
- Ein Tupel ist hashable nur, wenn alle seine Elemente sind hashable
- Benutzer-definierten Typen sind hashable standardmäßig, weil Ihre hash-Wert der id()
InformationsquelleAutor liuyihe
8

Technisch, hashable bedeutet, dass die Klasse definiert __hash__(). Laut der docs:

__hash__() sollte eine Ganzzahl zurück. Die einzige erforderliche Eigenschaft ist, dass Objekte, die vergleichen gleich, haben den gleichen hash-Wert; es wird empfohlen, um irgendwie miteinander zu vermischen (z.B. unter Verwendung von exklusiv-oder) die hash-Werte für die Komponenten des Objekts, die auch eine Rolle spielen, im Vergleich von Objekten.

Ich denke, dass für die Python-builtin-Typen, alle hashable-Typen sind auch unveränderlich.

Es schwer werden würde, aber vielleicht nicht unmöglich, haben ein veränderliches Objekt, die dennoch definiert __hash__().

Es ist erwähnenswert, dass __hash__ ist standardmäßig definiert das Objekt zurückzugeben ist id; Sie gehen aus dem Weg, um __hash__ = None zu machen unhashable. Auch als Mark Lösegeld erwähnt, gibt es eine zusätzliche Bedingung, dass es nur hashable, wenn der hash-Wert kann sich niemals ändern!
Ich denke, die Antwort ist ein wenig irreführend, list definiert __hash__ in dem Sinne, dass hasattr([1,2,3], "__hash__") zurück True jedoch Berufung hash([1,2,3]) wirft eine TypeError (Python 3), so ist es nicht gerade hashable. Unter Berufung auf die Existenz __hash__ ist nicht ausreichend, um zu bestimmen, ob etwas eine) hashable b) unveränderlich

InformationsquelleAutor Andrew Jaffe
7

Aus der Python-Glossar:

Objekt ist hashable, wenn es einen hash-Wert ändert sich nie während seiner Lebenszeit (es muss ein __hash__() - Methode), und kann im Vergleich zu anderen Objekten (es muss ein __eq__() oder __cmp__() - Methode). Hashable Objekte, die vergleichen gleich, müssen den gleichen hash-Wert.

Hashability macht ein Objekt nutzbar als dictionary-Schlüssel und ein set-Mitglied, weil diese Datenstrukturen verwenden Sie den hash-Wert intern.

Alle Python unveränderlich built-in-Objekte werden hashable, während kein veränderbarer Container (wie Listen oder dictionaries) sind. Objekte sind Instanzen von benutzerdefinierten Klassen sind hashable standardmäßig, Sie alle zu vergleichen, ungleich, und Ihre hash-Wert der id().

Dicts und Sätze müssen, verwenden Sie einen hash für die effiziente Suche in einer hash-Tabelle; die hash-Werte sind unveränderlich, weil die änderung der hash wird mess up der Daten, Strukturen und bewirken, dass das dict-oder scheitern. Der einfachste Weg, um den hash-Wert, der unveränderlich ist, um das gesamte Objekt unveränderlich ist, weshalb die beiden oft gemeinsam erwähnt.

Während keiner der built-in-mutable-Objekte sind hashable, ist es möglich, ein veränderliches Objekt mit einem hash-Wert, der nicht verändert werden. Es ist üblich, dass nur ein Teil des Objektes zu repräsentieren, seine Identität, während der rest der das Objekt enthält Eigenschaften, die frei sind, sich zu ändern. Solange die hash-Wertes und Vergleich-Funktionen basieren auf der Identität, nicht aber die änderbaren Eigenschaften, und die Identität, die sich nie ändert, Sie habe den Anforderungen entsprochen.

Gutes Zitat. Du meinst frozensets, richtig? 🙂
frozensets sind hashable, setzt nicht; beide können nur enthalten hashable Elemente. In den Orten, die von Mark erwähnten sets, er war richtig, also ich glaube nicht, dass er gemeint frozensets.
Benutzer-definierte Klassen standardmäßig definieren hashable-Typen (der hash ist nur das Objekt id). Dies kann nicht ändern, während das Objekt ist Leben, so ist es hashable, aber das bedeutet nicht, Sie können nicht definieren, veränderliche Arten! Sorry, aber hashability bedeutet nicht Unveränderbarkeit.
Ich weiß nicht, warum es dauerte 6 Jahre, um zu sehen Ihren Kommentar, aber besser spät als nie. Ich weiß nicht, wie ich hätte so weit Weg, da habe ich beklagt die Unfähigkeit zu setzen mutable-Objekte in einem C++ gesetzt. Ich hoffe, dass meine änderung behebt Dinge.

InformationsquelleAutor Mark Ransom
4

Gibt es eine implizite, auch wenn es keine explizite Beziehung gezwungen, zwischen unveränderlichen und hashable durch das zusammenspiel zwischen
1. Hashable Objekte, die vergleichen gleich, müssen den gleichen hash-Wert
2. Ein Objekt ist hashable, wenn es einen hash-Wert ändert sich nie während seiner Lebenszeit.
Hier gibt es kein problem, es sei denn, Sie definieren __eq__ so das die Objekte der Klasse definiert äquivalenz auf Wert.

Sobald Sie dies getan haben, benötigen Sie eine stabile hash-Funktion gibt immer den gleichen Wert für Objekte, die den gleichen Wert (zB, wo __eq__) gibt True zurück, und ändert sich nie während der Lebensdauer eines Objekts.

Es schwer zu sehen, eine Anwendung, wo dies möglich ist, ziehen Sie einen möglichen Klasse Eine, der diese Anforderungen erfüllt. Obwohl es die offensichtlich degenerierten Fall, wo __hash__ gibt eine Konstante.

Nun:-
```
>>> 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.
```
In der Tat bedeutet dies die Schaffung hash(b) == hash(c), trotz der Tatsache, dass es nie im Vergleich gleich. Ich Kämpfe, um zu sehen, sowieso sinnvoll definieren __hash__() für ein veränderliches Objekt, das definiert, vergleichen von Wert.

Hinweis: __lt__, __le__ , __gt__ und __ge__ comparsions sind nicht betroffen, so können Sie noch definieren eine Reihenfolge von hashable Objekte veränderlich oder sonst auf Ihren Wert.

InformationsquelleAutor rgammans

nur weil das ist die top-Google-Treffer, hier ist ein einfacher Weg, um ein veränderliches Objekt hashable:

>>> 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 fand sogar eine Verwendung für so etwas wie diese bei der Erstellung einer Klasse zu casten Datensätze in SQLAlchemy etwas wandelbar ist, und mehr nützlich für mich, während die Aufrechterhaltung der hashability für den Einsatz als dict-Schlüssel.

InformationsquelleAutor jcomeau_ictx

3

Immutable bedeutet, dass das Objekt nicht ändern, in irgendeiner signifikanten Art und Weise während seiner Lebensdauer. Es ist eine vage, aber gemeinsame Idee in Programmiersprachen.

Hashability ist etwas anders, und bezieht sich auf den Vergleich.

hashable Ein Objekt ist hashable, wenn es einen hash-Wert nie
änderungen während der Laufzeit kann (es braucht einen __hash__() - Methode), und kann
im Vergleich zu anderen Objekten (es muss ein __eq__() oder __cmp__() - Methode).
Hashable Objekte, die vergleichen gleich, müssen den gleichen hash-Wert.

Alle benutzerdefinierten Klassen haben __hash__ - Methode, die standardmäßig nur die Renditen der Objekt-ID. Also ein Objekt, das den Kriterien entspricht, die für hashability ist nicht unbedingt unveränderlich.

Objekte von jeder neuen Klasse, die Sie deklarieren können verwendet werden als dictionary-Schlüssel, es sei denn, Sie verhindern, dass es zum Beispiel durch das werfen von __hash__

Könnten wir sagen, dass alle unveränderliche Objekte sind hashable, denn wenn sich der hash ändert, während das Objekt Leben, dann bedeutet es, dass das Objekt mutiert.

Aber nicht ganz. Betrachten wir ein Tupel, welches eine Liste (änderbar). Einige sagen, Tupel unveränderlich ist, aber zur gleichen Zeit es ist etwas nicht hashable (wirft).
```
d = dict()
d[ (0,0) ] = 1    #perfectly fine
d[ (0,[0]) ] = 1  #throws
```
Hashability und Unveränderlichkeit siehe Objekt instancess, nicht geben. Zum Beispiel, ein Objekt vom Typ tuple werden kann hashable oder nicht.

"Hashable Objekte, die vergleichen gleich, müssen den gleichen hash-Wert." Warum? Ich kann Objekte erstellen, Vergleich gleich, haben aber nicht den gleichen hash-Wert.
Es ist möglich, solche Objekte, aber es wäre ein Verstoß gegen ein Konzept definiert, in der Python-Dokumentation. Die Idee ist, dass, in der Tat, wir können diese Forderung abzuleiten, eine solche (logisch äquivalent) Implikation: Wenn die Hashwerte nicht gleich sind, dann werden die Objekte nicht gleich sind. Sehr nützlich sind. Viele Implementierungen, die Container und algorithmen verlassen sich auf diese Implikation die Dinge etwas beschleunigen.
In häufigen Fällen, wo comparison != identity ist beim Vergleich von "ungültigen" Werte zusammen wie float("nan") == float("nan") oder interniert strings von Scheiben: "apple" is "apple" vs. "apple" is "crabapple"[4:]

InformationsquelleAutor user2622016
1

In der Python-Sie sind meistens austauschbar, da der hash darstellen soll, der Inhalt, also es ist genauso wandelbar ist wie das Objekt, und ein Objekt ändern Sie den hash-Wert machen es unbrauchbar, weil ein dict-key.

In anderen Sprachen, wird der hash-Wert bezieht sich auf die Objekte 'Identität', und nicht (unbedingt) auf den Wert. Also, für ein veränderliches Objekt, das Zeiger verwendet werden könnten, um starten Sie den hashing. Vorausgesetzt natürlich, dass ein Objekt nicht verschieben, die in Speicher (wie einige GC). Dies ist der Ansatz, die in der Lua, zum Beispiel. Dies macht ein veränderliches Objekt nutzbar als Tisch-Schlüssel; aber es erzeugt einige (unangenehme) überraschungen für Neulinge.

Am Ende, mit einer unveränderlichen Sequenz-Typ (Tupel) macht es schöner für 'multi-value-Tasten'.

Python-Sie sind meist austauschbar " Meine Zweifel beziehen sich auf das kleine Teil nicht enthalten in 'meist'

InformationsquelleAutor Javier
0

Hashable bedeutet, dass eine variable, die den Wert der dargestellt werden kann (oder, eher, Sat), die durch eine ständige-string, Anzahl, etc. Nun, etwas, das verändert werden (veränderlich) kann nicht dargestellt werden durch etwas, das nicht ist. Also, alle Variablen, die verändert werden kann hashable und, durch die gleichen token, die nur unveränderliche Variablen können hashable.

Hoffe, das hilft ...

InformationsquelleAutor ktdrv

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.