Was ist eine gute 64-Bit-Hash-function in Java für Textzeichenfolgen?

Ich suche nach einer Hash-function, die:

  1. Harte Textzeichenfolgen (zB wenige Kollisionen)
  2. Ist in Java geschrieben und weit verbreitet
  3. Bonus: funktioniert auf mehreren Feldern (anstatt sie zu verketten und den Hash auf die verkettete Zeichenfolge anzuwenden)
  4. Bonus: Hat eine 128-Bit-Variante.
  5. Bonus: Nicht CPU-intensiv.

Warum verwenden Sie nicht eine long Variante der Standard- String.hashCode() (wo einige wirklich schlaue Jungs sich wirklich Mühe geben, es effizient zu machen – nicht die Tausenden von Entwickleraugen zu erwähnen, die sich diesen Code bereits angesehen haben)?

 // adapted from String.hashCode() public static long hash(String string) { long h = 1125899906842597L; // prime int len = string.length(); for (int i = 0; i < len; i++) { h = 31*h + string.charAt(i); } return h; } 

Wenn Sie noch mehr Bits suchen, könnten Sie wahrscheinlich einen BigInteger Edit verwenden:

Wie ich in einem Kommentar zu der Antwort von @brienegge erwähnt habe, gibt es nicht viele Anwendungsfälle für Hashes mit mehr als 32 Bits und höchstwahrscheinlich keine einzige für Hashes mit mehr als 64 Bits:

Ich könnte mir eine riesige Hashtable vorstellen, die auf Dutzende von Servern verteilt ist und vielleicht Dutzende von Milliarden von Mappings speichert. Für solch ein Szenario hat @brienegge noch einen gültigen Punkt: 32 Bit erlauben 2 ^ 32 (ca. 4,3 Milliarden) verschiedene Hash-Schlüssel. Unter der Annahme eines starken Algorithmus sollten Sie immer noch ziemlich wenige Kollisionen haben. Mit 64 Bit (18.446.744.073 Milliarden verschiedene Schlüssel) sparen Sie sicher, egal in welchem ​​verrückten Szenario Sie es brauchen. Denken Sie an Usecases für 128-Bit-Schlüssel (340.282.366.920.938.463,463,374,607,431 Milliarden mögliche Schlüssel) ist jedoch ziemlich unmöglich.

Um den Hash für mehrere Felder zu kombinieren, führe einfach ein XOR aus, multipliziere eins mit einem Primzahlzeichen und füge sie hinzu:

 long hash = MyHash.hash(string1) * 31 + MyHash.hash(string2); 

Die kleine Primzahl ist da, um den gleichen Hash-Code für vermittelte Werte zu vermeiden, dh {'foo', 'bar'} und {'bar', 'foo'} sind nicht gleich und sollten einen anderen Hash-Code haben. XOR ist schlecht, da es 0 zurückgibt, wenn beide Werte gleich sind. Daher hätten {'foo', 'foo'} und {'bar', 'bar'} denselben Hash-Code.

Erstellen Sie einen SHA-1-Hash und maskieren Sie dann die niedrigsten 64 Bit aus.

 long hash = string.hashCode(); 

Ja, die oberen 32 Bits sind 0, aber Sie werden wahrscheinlich keine Hardware-Ressourcen mehr haben, bevor Sie Probleme mit Hash-Kollisionen haben. Der hashCode in String ist ziemlich effizient und gut getestet.

Update Ich denke, das obige erfüllt die einfachste Sache, die möglicherweise funktionieren könnte , jedoch stimme ich mit @sfussenegger Idee der Erweiterung der bestehenden String-Hash-Code.

Zusätzlich zu einem guten hashCode für Ihren String sollten Sie den Hash-Code in Ihrer Implementierung erneut verwenden. Wenn Ihr Speicher von anderen Entwicklern verwendet oder mit anderen Typen verwendet wird, kann dies helfen, Ihre Schlüssel zu verteilen. Zum Beispiel basiert die HashMap von Java auf Hashtabellen mit Zweierpotenz, so dass diese function hinzugefügt wird, um sicherzustellen, dass die unteren Bits ausreichend verteilt sind.

  h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); 

Warum nicht ein CRC64-Polynom verwenden? Diese sind einigermaßen effizient und optimiert, um sicherzustellen, dass alle Bits gezählt und über den Ergebnisbereich verteilt werden.

Es gibt viele Implementierungen im Internet verfügbar, wenn Sie “CRC64 Java” googlen

Tun Sie etwas wie folgt:

 import java.io.ByteArrayOutputStream; import java.io.DataOutputStream; import java.io.IOException; import java.math.BigInteger; import java.security.MessageDigest; import java.security.NoSuchAlgorithmException; public class Test { public static void main(String[] args) throws NoSuchAlgorithmException, IOException { ByteArrayOutputStream baos = new ByteArrayOutputStream(); DataOutputStream dos = new DataOutputStream(baos); try { MessageDigest md = MessageDigest.getInstance("MD5"); SomeObject testObject = new SomeObject(); dos.writeInt(testObject.count); dos.writeLong(testObject.product); dos.writeDouble(testObject.stdDev); dos.writeUTF(testObject.name); dos.writeChar(testObject.delimiter); dos.flush(); byte[] hashBytes = md.digest(baos.toByteArray()); BigInteger testObjectHash = new BigInteger(hashBytes); System.out.println("Hash " + testObjectHash); } finally { dos.close(); } } private static class SomeObject { private int count = 200; private long product = 1235134123l; private double stdDev = 12343521.456d; private String name = "Test Name"; private char delimiter = '\n'; } } 

Mit DataOutputStream können Sie Primitive und Strings schreiben und sie als Bytes ausgeben lassen. Wenn Sie einen ByteArrayOutputStream darin einschließen , können Sie in ein Byte-Array schreiben, das sich gut in MessageDigest integriert . Sie können aus jedem der hier aufgeführten Algorithmen auswählen.

Schließlich können Sie mit BigInteger die Ausgangsbytes in eine einfachere Nummer umwandeln . Die MD5- und SHA1-Algorithmen erzeugen beide 128-Bit-Hashes. Wenn Sie also 64 benötigen, können Sie sie einfach abschneiden.

SHA1 sollte fast alles gut hacken und mit seltenen Kollisionen (es ist 128-Bit). Dies funktioniert von Java, aber ich bin mir nicht sicher, wie es implementiert ist. Es kann tatsächlich ziemlich schnell sein. Es funktioniert auf mehreren Feldern in meiner Implementierung: schieb sie einfach auf den DataOutputStream und du kannst DataOutputStream . Sie könnten es sogar mit Reflektion und Annotationen machen (vielleicht @HashComponent(order=1) zu zeigen, welche Felder in welcher Reihenfolge in einen Hash gehen). Es hat eine 128-Bit-Variante und ich denke, Sie werden feststellen, dass es nicht so viel CPU verbraucht, wie Sie denken.

Ich habe Code wie diesen verwendet, um Hashes für riesige Datenmengen (inzwischen vermutlich Milliarden von Objekten) zu erhalten, um sie in vielen Backend-Stores zu sharden. Es sollte für alles funktionieren, wofür Sie es brauchen. Beachten Sie, dass Sie MessageDigest.getInstance() einmal aufrufen und dann von da an clone() möchten: IIRC das Klonen ist viel schneller.

Kehren Sie die Zeichenfolge um, um einen weiteren 32-Bit-Hashcode zu erhalten, und kombinieren Sie die beiden dann:

 String s = "astring"; long upper = ( (long) s.hashCode() ) < < 32; long lower = ( (long) s.reverse().hashCode() ) - ( (long) Integer.MIN_VALUE ); long hash64 = upper + lower; 

Dies ist Pseudocode; Die String.reverse() -Methode existiert nicht und muss auf andere Weise implementiert werden.

Eine Antwort für heute (2018). SipHash.

Es wird viel schneller sein als die meisten Antworten hier und eine deutlich höhere Qualität als alle anderen.

Die Guava-Bibliothek hat eine: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24–

Schaust du dir Apache commons lang an ?

Aber für 64 Bit (und 128) brauchen Sie ein paar Tricks: Die Regeln, die in dem Buch Effective Java von Joshua Bloch beschrieben sind, helfen Ihnen bei der Erstellung von 64 Bit Hash easy (verwenden Sie long statt int). Für 128 Bit brauchst du zusätzliche Hacks …

HAFTUNGSAUSSCHLUSS: Diese Lösung ist anwendbar, wenn Sie einzelne Wörter natürlicher Sprache effizient hashen möchten. Es ist ineffizient für das Hashing von längerem Text oder Text, der nicht alphabetische Zeichen enthält.

Ich bin mir einer function nicht bewusst, aber hier ist eine Idee, die helfen könnte:

  • Widmen Sie 52 der 64 Bits, um darzustellen, welche Buchstaben in der Zeichenfolge vorhanden sind. Wenn zum Beispiel ‘a’ vorhanden wäre, würden Sie das Bit [0] setzen, für ‘b’ setzen Sie Bit 1 , für ‘A’ setzen Sie Bit [26]. Auf diese Weise würde nur Text, der genau den gleichen Satz von Buchstaben enthält, die gleiche “Signatur” haben.

Sie könnten dann die verbleibenden 12 Bits verwenden, um die String-Länge (oder einen Modulo-Wert davon) zu codieren, um Kollisionen weiter zu reduzieren, oder um einen 12-Bit-Hash-Code unter Verwendung einer herkömmlichen Hash-function zu erzeugen.

Unter der Annahme, dass Ihre Eingabe nur Text ist, kann ich mir vorstellen, dass dies zu sehr wenigen Kollisionen führen würde und kostengünstig zu berechnen wäre (O (n)). Im Gegensatz zu anderen Lösungen berücksichtigt dieser Ansatz die Problemdomäne, um Kollisionen zu reduzieren. Er basiert auf dem in Programming Pearls beschriebenen Anagram Detector (siehe hier ).