Ich habe eine Subschnittstelle von java.util.Collection definiert, die effektiv eine Multiset (aka bag) ist. Es darf keine null -Elemente enthalten, obwohl das für meine Frage nicht entscheidend ist. Der Gleichheitsvertrag, der von der Schnittstelle definiert wird, ist wie erwartet:
obj instanceof MyInterface obj enthält dieselben Elemente wie this (by equals ) obj enthält die gleiche Anzahl von Duplikaten für jedes Element Nun möchte ich meine hashCode Methode schreiben. Meine ursprüngliche Idee war:
Allerdings habe ich festgestellt, dass com.google.common.collect.Multiset (aus Guava) den Hash-Code wie folgt definiert:
Es kommt mir seltsam vor, dass ein leeres Multiset den Hash-Code 0 hat, aber noch wichtiger ist, dass ich den Vorteil von ^ count(o) gegenüber dem einfachen Addieren der Hash-Codes jedes Duplikats nicht verstehe. Vielleicht geht es darum, den gleichen Hash-Code nicht mehr als einmal zu berechnen, aber warum nicht * count(o) ?
Meine Frage: Was wäre eine effiziente Hash-Code-Berechnung? In meinem Fall ist die Zählung für ein Element nicht garantiert, um billig zu sein.
Nehmen wir beispielsweise an, dass wir ein Array haben, das wir als Multiset behandeln wollen.
Sie müssen also alle Einträge so verarbeiten, wie sie kommen, Sie können count nicht verwenden und können nicht davon ausgehen, dass die Einträge in einer bekannten Reihenfolge sind.
Die allgemeine Funktion, die ich in Betracht ziehen würde, ist
%Vor%Einige Beobachtungen:
NULL_HASH=0 gehen, da dies Nullwerte ignorieren würde. g kann verwendet werden, wenn Sie erwarten, dass die Hashes der Mitglieder in einem kleinen Bereich liegen (was passieren kann, wenn sie z. B. einzelne Zeichen sind). h kann verwendet werden, um das Ergebnis zu verbessern, was nicht sehr wichtig ist, da dies z.B. in HashMap.hash(int) . f ist die wichtigste, leider ist sie ziemlich begrenzt, da sie offensichtlich sowohl assoziativ als auch kommutativ sein muss. f sollte in beiden Argumenten bijektiv sein, sonst würden Sie unnötige Kollisionen erzeugen. In keinem Fall würde ich f(x, y) = x^y empfehlen, da zwei Vorkommen eines Elements aufgehoben werden. Die Verwendung von Zusatz ist besser. Etwas wie
wobei A eine Konstante ist, die alle obigen Bedingungen erfüllt. Es kann sich lohnen.
Für A=0 degeneriert es zur Addition, wobei ein gerades A nicht gut ist, da Bits von x*y out verschoben werden.
Die Verwendung von A=1 ist in Ordnung, und der Ausdruck 2*x+1 kann mit einer einzigen Anweisung in der x86 -Architektur berechnet werden.
Die Verwendung eines größeren ungeraden A könnte besser funktionieren, falls die Hashes der Mitglieder schlecht verteilt sind.
Falls Sie sich für ein nicht-triviales hashCode() entscheiden, sollten Sie testen, ob es richtig funktioniert. Sie sollten die Leistung Ihres Programms messen, vielleicht finden Sie eine einfache Ergänzung ausreichend. Ansonsten würde ich für NULL_HASH=1 , g=h=identity und A=1 .
Es kann aus Effizienzgründen sein. Der Aufruf von count kann für einige Implementierungen teuer sein, stattdessen kann jedoch auch entrySet verwendet werden. Trotzdem könnte es teurer sein, ich kann es nicht sagen.
Ich habe einen einfachen Kollisions-Benchmark für Guava's hashCode und Rinkes und meine eigenen Vorschläge gemacht:
%Vor%Der Code für die Kollisionszählung lautet wie folgt:
%Vor%und gedruckt
%Vor%In diesem einfachen Beispiel hat der Guava-Hashcode wirklich schlecht abgeschnitten (45 von 63 möglichen Kollisionen). Ich behaupte jedoch nicht, dass mein Beispiel für das wirkliche Leben von großer Relevanz ist.
Wenn die Zählung teuer ist, tun Sie es nicht. Weißt du, dass es zu teuer ist? Sie können immer mehrere Implementierungen codieren und ihre Performance mit Daten modellieren, von denen Sie erwarten, dass sie für Ihre Anwendung repräsentativ sind. Dann werden Sie wissen die Antwort statt zu erraten.
Warum Sie XOR verwenden, finden Sie unter 'Berechnung von aggregierten Hashcodes mit XOR' .
Es kommt mir seltsam vor, dass eine leere Multiset den Hash-Code 0 haben würde
Warum? Alle leeren Sammlungen haben wahrscheinlich Hash-Code 0. Auch wenn nicht, müsste es ein fester Wert sein (da alle leeren Sammlungen gleich sind), was ist also falsch mit 0?
Was wäre eine effiziente Hash-Code-Berechnung?
Ihr ist effizienter (was nur schneller berechnet werden kann), nicht so schlecht in Bezug auf die Effektivität (was bedeutet, dass Ergebnisse erzielt werden, die gut funktionieren). Wenn ich es richtig verstehe, addiert es die Hash-Codes aller Elemente (wobei doppelte Elemente zweimal hinzugefügt werden). Dies ist genau das, was ein reguläres Set tut. Wenn Sie also keine Duplikate haben, erhalten Sie den gleichen Hash-Code wie bei einem Set, was ein Vorteil sein könnte (wenn Sie den leeren Satz auf hashCode 0 und nicht auf 1 setzen) >
Googles Version ist ein wenig komplizierter, ich nehme an, um einige sonst häufige Kollisionen zu vermeiden. Natürlich verursacht es wahrscheinlich einige andere Kollisionen, die als selten angesehen werden.
Insbesondere bei der Verwendung von XOR werden die hashCodes über den gesamten verfügbaren Bereich verteilt, auch wenn die einzelnen EingabehashCodes dies nicht tun (was sie beispielsweise nicht für Ganzzahlen aus einem begrenzten Bereich tun, was ein häufiger Anwendungsfall ist). p>
Betrachten Sie den Hash-Code für das Set [1, 2, 3]. Es ist 6. Wahrscheinlich kollidieren mit ähnlichen Sets, zum Beispiel [6], [4, 2], [5, 1]. Einige XORs dorthin zu werfen hilft. Wenn es notwendig ist und die zusätzlichen Kosten wert sind, müssen Sie einen Kompromiss machen.
Ich beobachte, dass java.util.Map mehr oder weniger die gleiche Logik verwendet: java.util.Map.hashCode () wird angegeben, um map.entrySet () zurückzugeben. hashCode () und Map.Entry gibt an, dass es sich um hashCode handelt () ist entry.getKey (). hashCode () ^ entry.getValue (). hashCode (). Wenn Sie die Analogie von Multiset zu Map akzeptieren, ist dies genau die Hash-Code-Implementierung, die Sie erwarten würden.