Order-unabhängige Hash-Algorithmus

Question

Ich arbeite derzeit an einer Sammlung Bibliothek für meine benutzerdefinierte Programmiersprache. Ich habe bereits mehrere Datentypen (Collection, List, Map, Set) und Implementierungen für sie (veränderbar und unveränderlich), aber was ich bisher vermisst habe, war und equals. Während dies für Listen keine Probleme sind, da sie geordnete Sammlungen sind, spielen sie für Sets und Maps eine besondere Rolle. Zwei Sätze werden als gleich betrachtet, wenn sie die gleiche Größe und die gleichen Elemente haben, und die Reihenfolge, in der die Sätze sie beibehalten, sollte keinen Unterschied in ihrer Gleichheit machen. Aufgrund des equals-hashCode-Vertrags muss die hashCode-Implementierung auch dieses Verhalten widerspiegeln, was bedeutet, dass zwei Sätze mit denselben Elementen, aber unterschiedlicher Reihenfolge denselben Hash-Code haben sollten. (Dies gilt auch für Karten, die technisch eine Reihe von Key-Value-Paaren)

Beispiel (Pseudocode):

let set1: Set<String> = [ "a", "b", "c" ] 
let set2: Set<String> = [ "b", "c", "a" ] 
set1 == set2  // should return true 
set1.hashCode == set2.hashCode // should also return true 

Wie würde ich einen einigermaßen guten Hash-Algorithmus implementieren, für die die hashCode s im obigen Beispiel geben Sie den gleichen Wert zurück?

Answer 1

Das JDK selbst schlägt die folgende Lösung für dieses Problem vor. Der Vertrag der Schnittstelle java.util.Set lautet:

Gibt den Hashcodewert für diesen Satz zurück. Der Hash-Code eines Satzes ist definiert als die Summe der Hash-Codes der Elemente in dem Satz, wobei der Hash-Code eines Null-Elements als Null definiert ist. Dies stellt sicher, dass s1.equals (s2) impliziert, dass s1.hashCode() == s2.hashCode() für alle zwei Mengen s1 und s2, wie vom allgemeinen Vertrag von Object.hashCode() gefordert, ist.

Eine Alternative der Summe der Einträge Hash-Codes auf der Verwendung beispielsweise zu verwenden wäre, den ^ (XOR) Operator.

Die Scala Sprache verwendet eine Bestell-invariant Version des Murmurhash Algorithmus (vgl die privaten scala.util.hashing.MurmurHash3 Klasse), um die hashCode (oder ##) Methode seiner immutable sets und ähnlichen Sammlungen zu implementieren.

Answer 2

Hier ist der Pseudo-Code für eine mögliche Implementierung:

String hashCode = null; 
for(element : elements){ 
    hashCode = xor(hashCode, getHashCode(element)); 
} 
return hashCode; 

Die xor Funktion sollte einen String zurückgeben, solange die längste der beiden Argumente ist. Es wird XOR die Bits in jedem, bis es an das Ende eines der Argumente gelangt. Es nimmt dann die restlichen Bits von der längeren Zeichenfolge und hängt diese an.

Diese Implementierung bedeutet, dass der hashCode eines Satzes so lang ist wie der hashCode seines längsten Elements. Da Sie die Bits XORing sind, wird der Hashcode am Ende immer gleich sein, unabhängig von der Reihenfolge Ihrer Elemente. Wie bei jeder Hashing-Implementierung besteht jedoch die Gefahr von Kollisionen.

Answer 3

Sie können die Hashsumme berechnen, indem Sie Ihre Sammlung in alphabetischer Reihenfolge sortieren.

Es ist die C# Beispiel - ich hoffe, dass Sie es in Java übersetzen :)

static String GetHash(List<String> l) 
{ 
    using (System.Security.Cryptography.MD5 md5 = System.Security.Cryptography.MD5.Create()) 
    { 
     return BitConverter.ToString(md5.ComputeHash(l.OrderBy(p => p).SelectMany(s => System.Text.Encoding.ASCII.GetBytes(s + (char)0)).ToArray())).Replace("-", ""); 
    } 
}