Objekte als dict keys mit __hash__?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Gerenuk
User
Beiträge: 69
Registriert: Donnerstag 21. Januar 2010, 22:27

Ich habe gesehen man kann beliebige Objekte als dict key verwenden, wenn man __hash__ implementiert (in meinem Beispiel "return self.data["id"]" - irgendwie hatte ich noch ne Zahl draus gemacht :) ). Nun bin ich mir gar nicht sicher was da genau passiert.

Was muss ich beachten?
Kommt das ganze Objekt als key rein? Was ist wenn es sich verändert? Was ist wenn ein gleiches Objekt mit einem gleich berechneten key kommt? Kann ich das komplette Objekt aus dem key herauslesen?

Irgendwie erscheint mit das schleierhaft.. :-|
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Code: Alles auswählen

>>> d = {'a': 42, 'b': 23}
>>> d
{'a': 42, 'b': 23}
>>> d['a'] = 1337
>>> d
{'a': 1337, 'b': 23}
>>> 'a' == 'a'
True
>>> hash('a') == hash('a')
True
Und genauso sollte es sich auch bei deinen eigenen Objekten verhalten (die dann z.B. vom Typ Foo statt str sind). Das heißt: gleicher hashwert ist äquivalent zu gleiches objekt. Weiter Informationen auf http://docs.python.org/reference/datamo ... t.__hash__. Da steht auch, wann es überhaupt sinnvoll ist, __hash__ zu implementieren und in welchen Fällen davon abgeraten wird.
syntor
User
Beiträge: 88
Registriert: Donnerstag 2. Dezember 2010, 03:56

Jedes benutzerdefinierte Objekt hat eine __hash__ Methode, sie gibt standardmässig id(self) zurück. Das sich daraus ergebende Verhalten ist vollkommen intuitiv, finde ich.

Du kannst sie also ohne Aufwand als Keys in dictionaries verwenden.
BlackJack

@Gerenuk: Es reicht nicht `__hash__()` zu implementieren, man muss auch `__eq__()` oder `__cmp__()` entsprechend überschreiben. Der Vertrag ist, das genau dann wenn zwei Objekte beim Vergleichen mit ``==`` gleich sind, auch der Hash-Wert gleich sein muss. Und der Wert über den das beides passiert darf nicht verändert werden. Darum gehen Listen zum Beispiel nicht als Schlüssel, weil man deren Wert verändern kann und deshalb `__hash__()` so implementiert wurde, dass es eine Ausnahme auslöst.

Am einfachsten bekommt man einen Hash-Wert mit der `hash()`-Funktion die man auf ein Tupel mit den Werten anwendet, die auch zum Vergleich heran gezogen werden. Beispiel:

Code: Alles auswählen

class Point(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __cmp__(self, other):
        return cmp((self.x, self.y), (other.x, other.y))

    def __hash__(self):
        return hash((self.x, self.y))
derdon
User
Beiträge: 1316
Registriert: Freitag 24. Oktober 2008, 14:32

Hab gerade ein etwas ausführlicheres Beispiel geschrieben. Auch wenn die Antworten die Fragen mittlerweile beantwortet haben, will ich nicht, das die Zeit umsonst war :P

Code: Alles auswählen

>>> class Foo(object):
...     def __init__(self, bar, baz):
...         self.bar = bar
...         self.baz = baz
...     def __repr__(self):
...         return '{}(bar={!r}, baz={!r})'.format(
...             self.__class__.__name__,
...             self.bar,
...             self.baz)
...     def __eq__(self, other):
...         return self.bar == other.bar and self.baz == other.baz
...     def __ne__(self, other):
...         return not (self == other)
...     def __hash__(self):
...         return hash(self.bar) ^ hash(self.baz)
... 
>>> foo1 = Foo(23, 42)
>>> foo2 = Foo(23, 42)
>>> map(hash, [foo1, foo2])
[61, 61]
>>> foo1 == foo2
True
>>> d = {foo1: 'this is foo1'}
>>> d
{Foo(bar=23, baz=42): 'this is foo1'}
>>> d[foo2] = 'this is foo2'
>>> d
{Foo(bar=23, baz=42): 'this is foo2'}
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

syntor hat geschrieben:Jedes benutzerdefinierte Objekt hat eine __hash__ Methode, sie gibt standardmässig id(self) zurück. Das sich daraus ergebende Verhalten ist vollkommen intuitiv, finde ich.
Nein, ist es nicht und deswegen wurde dies in Python 3.x geändert, so dass __hash__ nicht mehr vererbt wird wenn Vergleichsoperationen implementiert werden (oder zumindest __eq__).

Das Problem ist einfach dass man nicht erwartet dass veränderbare Objekte hashable sind, sollten sie es doch sein muss in logischer Konsequenz sich der Hash verändern wenn ich das Objekt selbst verändert. Ein solches Verhalten haben die built-in Sachen allerdings nicht.

Immer wenn man Vergleichsoperatoren implementiert sollte man dementsprechend __hash__ auf None setzen es sei den das Objekt ist unveränderbar, dann sollte man __hash__ implementieren, dass geht am einfachsten über den hash eines tuples der Attribute(siehe BlackJacks Beispiel) oder wie in der Dokumentation beschrieben.
syntor
User
Beiträge: 88
Registriert: Donnerstag 2. Dezember 2010, 03:56

Ich beziehe mich darauf:
object.__hash__(self)¶

Called by built-in function hash() and for operations on members of hashed collections including set, frozenset, and dict. __hash__() should return an integer. The only required property is that objects which compare equal have the same hash value; it is advised to somehow mix together (e.g. using exclusive or) the hash values for the components of the object that also play a part in comparison of objects.

If a class does not define a __cmp__() or __eq__() method it should not define a __hash__() operation either; if it defines __cmp__() or __eq__() but not __hash__(), its instances will not be usable in hashed collections. If a class defines mutable objects and implements a __cmp__() or __eq__() method, it should not implement __hash__(), since hashable collection implementations require that a object’s hash value is immutable (if the object’s hash value changes, it will be in the wrong hash bucket).

User-defined classes have __cmp__() and __hash__() methods by default; with them, all objects compare unequal (except with themselves) and x.__hash__() returns id(x).

Classes which inherit a __hash__() method from a parent class but change the meaning of __cmp__() or __eq__() such that the hash value returned is no longer appropriate (e.g. by switching to a value-based concept of equality instead of the default identity based equality) can explicitly flag themselves as being unhashable by setting __hash__ = None in the class definition. Doing so means that not only will instances of the class raise an appropriate TypeError when a program attempts to retrieve their hash value, but they will also be correctly identified as unhashable when checking isinstance(obj, collections.Hashable) (unlike classes which define their own __hash__() to explicitly raise TypeError).

Changed in version 2.5: __hash__() may now also return a long integer object; the 32-bit integer is then derived from the hash of that object.

Changed in version 2.6: __hash__ may now be set to None to explicitly flag instances of a class as unhashable.
Ich verstehe nicht, weshalb meine Aussage nicht stimmen soll.

# edit: nvm, ich nehme an du hast dich auf das "intuitiv" bezogen.
lunar

@DasIch: Die Quelle für Deine Behauptung hinsichtlich der Änderung im Verhalten von "__hash__()" und Python 3?

Ich verstehe auch nicht ganz, was nicht intuitiv daran sein soll, Hashing und Gleichheit standardmäßig über Objektidentität zu implementieren. Ich finde das ziemlich naheliegend, zumal andere Sprache sich genauso verhalten, und es eigentlich keine sinnvolle Alternative gibt.
DasIch
User
Beiträge: 2718
Registriert: Montag 19. Mai 2008, 04:21
Wohnort: Berlin

lunar hat geschrieben:@DasIch: Die Quelle für Deine Behauptung hinsichtlich der Änderung im Verhalten von "__hash__()" und Python 3?
http://docs.python.org/py3k/reference/datamodel.html#object.__hash__ hat geschrieben: If a class that overrides __eq__() needs to retain the implementation of __hash__() from a parent class, the interpreter must be told this explicitly by setting __hash__ = <ParentClass>.__hash__. Otherwise the inheritance of __hash__() will be blocked, just as if __hash__ had been explicitly set to None.
Ich verstehe auch nicht ganz, was nicht intuitiv daran sein soll, Hashing und Gleichheit standardmäßig über Objektidentität zu implementieren. Ich finde das ziemlich naheliegend, zumal andere Sprache sich genauso verhalten, und es eigentlich keine sinnvolle Alternative gibt.
Es kommt recht häufig vor das __eq__ implementiert wird __hash__ aber weder auf None gesetzt wird oder implementiert wird.

Das führt dann dazu das Objekte die veränderbar sind hashable sind. Intuitiv wäre allerdings dass ein veränderbares Objekt nicht hashable ist und dass desweiteren bei einem Objekt das hashable ist der Hash für gleiche Objekte identisch ist. Diese Situation provoziert Bugs geradezu.
lunar

Danke, in den "What's New"-Dokumenten ist diese Änderung gar nicht aufgeführt. Ansonsten reden wir aneinander vorbei. Ich sprach von der Standardimplementierung von "__hash__()", und die hat per se ja erst einmal nichts damit zu tun, dass man "__hash__()" und "__eq__()" zusammen überladen sollte, und der Interpreter das nach Möglichkeit erzwingen sollte (worin ich vollkommen Deiner Meinung bin).

Andererseits ist der Zusammenhang zwischen "__hash__()" und "__eq__()" ja eigentlich ziemlich klar dokumentiert :)
Antworten