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

https://stackoverflow.com/questions/1660501

11-09-2019
|

Frage

Ich suche nach einer Hash-Funktion, die:

Hashes Textzeichenfolgen gut (zum Beispiel wenige Kollisionen)
ist in Java geschrieben und weit verbreitet
Bonus: Arbeiten auf mehreren Feldern (statt mich ihnen und Anwenden des Hash auf der verketteten Zeichenfolge verketten)
Bonus:. Hat eine 128-Bit-Variante
Bonus. Nicht viel CPU-Kapazität

Lösung

Warum Sie keine long Variante des Standard String.hashCode() verwenden (wo einige wirklich smarten Jungs sicherlich Mühe in sie effizienter zu machen - nicht die Tausende von Entwicklern Augen zu erwähnen, die bereits an diesem Code angesehen)?

// 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 eine BigInteger~~ verwenden Edit:

Wie ich in einem Kommentar zu der Antwort von @brianegge erwähnt, gibt es nicht viel usecases für Hashes mit mehr als 32 Bits und höchstwahrscheinlich nicht ein einzigen für Hashes mit mehr als 64 Bit:

Ich konnte eine große hashtable über Dutzende von Servern verteilt sich vorstellen, vielleicht zig Milliarden Zuordnungen zu speichern. Für ein solches Szenario hat @brianegge noch einen wichtigen Punkt hier: 32-Bit erlauben 2 ^ 32 (ca. 4,3 Milliarden) verschiedene Hash-Schlüssel. Unter der Annahme eines starken Algorithmus, sollten Sie immer noch recht wenige Kollisionen haben. Mit 64 Bit (18446744073 Milliarden verschiedene Schlüssel) Sie sicher speichern, unabhängig davon, was auch immer verrückt Szenario, das Sie es brauchen. Denken an usecases für 128-Bit-Schlüssel (340,282,366,920,938,463,463,374,607,431 Milliarden mögliche Schlüssel) ist allerdings ziemlich unmöglich.

Um den Hash für mehrere Felder zu kombinieren, einfach ~~tun, um eine XOR~~ multiplizieren man mit einem Strich und fügen Sie:

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

Die kleine Primzahl ist dort in für geschaltete Werte gleich Hash-Code zu vermeiden, das heißt { ‚foo‘, ‚bar‘} und { ‚bar‘, ‚foo‘} nicht gleich sind und sollte einen anderen Hash-Code haben. XOR ist schlecht, wie es 0 zurückgibt, wenn beide Werte gleich sind. Daher { 'foo', 'foo'} und { 'bar', 'bar'} würde den gleichen Hash-Code haben.

Andere Tipps

Erstellen eines SHA-1-Hash und dann die niedrigsten 64 Bit maskieren .

long hash = string.hashCode();

Ja, die oberen 32 Bits 0 sein, aber Sie werden wahrscheinlich aus der Hardware-Ressourcen ausführen, bevor Sie Probleme mit Hash-Kollisionen führen. Die hashCode in String ist sehr effizient und gut getestet.

Aktualisieren Ich denke, die oben erfüllt die einfachste Sache, die möglicherweise funktionieren könnte , aber ich mit @sfussenegger Idee der Erweiterung des bestehenden String hashCode zustimmen.

Neben eine gute hashCode für Ihren String zu haben, können Sie wieder aufzuwärmen den Hash-Code in Ihrer Implementierung zu betrachten. Wenn Ihr Speicher von anderen Entwicklern verwendet wird, oder mit anderen Arten verwendet wird, kann dies Ihre Schlüssel verteilt helfen. Zum Beispiel ist Java HashMap basierend auf Power-of-two Länge Hash-Tabellen, so fügt sie diese Funktion der unteren Bits, um sicherzustellen, ausreichend verteilt.

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

Warum nicht ein CRC64 Polynom verwenden. Dies sind einigermaßen effizient und optimiert, um sicherzustellen, dass alle Bits werden gezählt und das Ergebnis Raum verteilt.

Es gibt viele Implementierungen im Internet verfügbar sind, wenn Sie Google „CRC64 Java“

Sie etwas wie folgt aus:

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';
    }
}

Dataoutputstream können Sie Primitiven schreiben und Streicher und haben sie ausgegeben als Bytes. Wickeln eines ByteArrayOutputStream es wird Sie lassen schreiben Sie an einen Byte-Array, das gut mit Message . Sie können von jedem Algorithmus wählen aufgelistet hier .

Schließlich BigInteger lassen Sie die Ausgangs-Bytes in eine leichter zu bedienende Zahl drehen. Die MD5 und SHA1-Algorithmen erzeugen beide 128-Bit-Hash-Werte, also wenn Sie 64 benötigen, können Sie nur gestutzt.

SHA1 sollte fast alles gut Hash und mit seltenen Kollisionen (es ist 128 Bit). Dies funktioniert aus Java, aber ich bin nicht sicher, wie es umgesetzt werden. Es kann eigentlich ziemlich schnell sein. Es funktioniert auf mehreren Feldern in meiner Implementierung: gerade sie schieben alle auf die DataOutputStream und du bist gut zu gehen. Sie tun können, es auch mit Reflexion und Anmerkungen (vielleicht zeigen @HashComponent(order=1), die in eine Hash gehen Felder und in welcher Reihenfolge). Es hat eine 128-Bit-Variante und ich denke, Sie finden es nicht so viel CPU nicht verwendet, wie Sie denken, es wird.

Ich habe so benutzten Code Hashes für große Datensätze zu bekommen (mittlerweile wahrscheinlich Milliarden von Objekten), um sie Scherbe über viele Back-End-Läden zu können. Es sollte für Arbeit, was auch immer Sie es brauchen. Beachten Sie, dass ich glaube, Sie nur Anruf MessageDigest.getInstance() einmal möchten und dann clone() von da an. IIRC das Klonen viel schneller ist

die Zeichenfolge umkehren einen weiteren 32-Bit-Hash-Code zu bekommen und dann kombinieren die beiden:

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 Pseudo-Code; die String.reverse() Methode existiert nicht und muss eine andere Art und Weise umgesetzt werden.

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

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

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

Haben Sie sehen Apache commons lang ?

Aber für 64-Bit (und 128) müssen Sie einige Tricks: die Regeln in dem Buch Effective Java von Joshua Bloch Ihnen dabei helfen, 64 Hash leicht Bit gelegt (nur so lange statt int verwenden). Für 128-Bit benötigen Sie zusätzliche Hacks ...

HAFTUNGSAUSSCHLUSS: Diese Lösung ist anwendbar, wenn Sie möchten effizient einzelne natürliche Sprache Worte Hash. Es ist ineffizient, für längeren Text Hashing oder Text enthält nicht-alphabetische Zeichen.

Ich bin mir nicht bewusst, eine Funktion, aber hier ist eine Idee, die helfen kann:

weihe 52 der 64 Bits, die darstellen, welche Buchstaben im String vorhanden sind. Wenn zum Beispiel 'a' vorhanden sind Sie hat gesetzt Bit [0], für 'b' gesetzt Bit 1 , für 'A' gesetzt Bit [26]. Auf diese Weise nur Text genau den gleichen Satz von Buchstaben enthält, würde die gleiche „Signatur“.

Sie könnten dann die restlichen 12 Bit verwenden, um die String-Länge (oder einen Modulo-Wert davon) zu kodieren, um weitere Kollisionen zu verringern, oder einen 12-Bit-hashCode erzeugen eine traditionelle Hash-Funktion verwendet wird.

Ihre Eingabe Unter der Annahme, nur Text kann ich mich vorstellen, dies in sehr wenige Kollisionen führen würde und wäre billig zu berechnen (O (n)). Im Gegensatz zu anderen Lösungen so weit dieser Ansatz das Problem Domain berücksichtigt Kollisionen zu verringern - Es basiert weg ist der Anagram Detector in Programming Pearls beschrieben (siehe hier ).

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow