Kurzfassung: Was ist der beste Hashalgorithmus für ein Multiset, das als Wörterbuch mit ungeordneten Elementen implementiert ist?

Ich versuche, ein unveränderliches Multiset (das in anderen Sprachen ein Bag oder Multiset ist: wie ein mathematisches Set, außer dass es mehr als eines von jedem Element enthalten kann) zu hashen, das als Wörterbuch implementiert ist. Ich habe eine Unterklasse der Standardbibliotheksklasse erstelltcollections.Counter, ähnlich dem Rat hier:Python hashable diktiert, der eine Hash-Funktion wie folgt empfiehlt:

<code>class FrozenCounter(collections.Counter):
    # ...
    def __hash__(self):
        return hash(tuple(sorted(self.items())))
</code>

Das Erstellen des vollständigen Tupels von Elementen beansprucht viel Speicher (z. B. mithilfe eines Generators), und in einem äußerst speicherintensiven Teil meiner Anwendung tritt Hashing auf. Noch wichtiger ist, dass meine Wörterbuchschlüssel (Multiset-Elemente) wahrscheinlich nicht bestellbar sind.

Ich denke an diesen Algorithmus:

<code>def __hash__(self):
    return functools.reduce(lambda a, b: a ^ b, self.items(), 0)
</code>

Ich rechne mit bitweisen XOR-MittelnDie Reihenfolge spielt für den Hash-Wert keine Rolle, anders als beim Hashing eines Tupels? Ich nehme an, ich könnte den Python-Tupel-Hashing-Alogrithmus auf dem ungeordneten Tupelstrom meiner Daten semi-implementieren. Sehenhttps://github.com/jonashaag/cpython/blob/master/Include/tupleobject.h (Suche auf der Seite nach dem Wort "Hash") - aber ich kenne kaum genug C, um es zu lesen.

Gedanken? Vorschläge? Vielen Dank.

(Wenn Sie sich fragen, warum ich versuche, ein Multiset zu hashen: Die Eingabedaten für mein Problem sind Sätze von Multisets, und innerhalb jedes Satzes von Multisets muss jedes Multiset eindeutig sein. Ich arbeite an einer Frist und bin kein erfahrener Programmierer. Deshalb wollte ich möglichst keine neuen Algorithmen erfinden. Es scheint, als wäre es die pythonischste Methode, um sicherzustellen, dass ich ein einzigartiges Bündel von Dingen habe, sie in ein einzutragenset(), aber die Dinge müssen hashbar sein.)

Was ich aus den Kommentaren zusammengetragen habe

Sowohl @marcin als auch @senderle gaben so ziemlich die gleiche Antwort: usehash(frozenset(self.items())). Das macht Sinn, weilitems() "Ansichten" sind satzartig. @marcin war der erste, aber ich habe @senderle das Häkchen gegeben, weil ich gute Nachforschungen über die Big-O-Laufzeiten für verschiedene Lösungen angestellt habe. @ Marcin erinnert mich auch aneinschließen__eq__ Methode - aber der von geerbtdict wird gut funktionieren. So setze ich alles um - weitere Kommentare und Vorschläge zu diesem Code sind willkommen:

<code>class FrozenCounter(collections.Counter):
    # Edit: A previous version of this code included a __slots__ definition.
    # But, from the Python documentation: "When inheriting from a class without
    # __slots__, the __dict__ attribute of that class will always be accessible,
    # so a __slots__ definition in the subclass is meaningless."
    # http://docs.python.org/py3k/reference/datamodel.html#notes-on-using-slots
    # ...
    def __hash__(self):
        "Implements hash(self) -> int"
        if not hasattr(self, '_hash'):
            self._hash = hash(frozenset(self.items()))
        return self._hash
</code>