Co to jest dobra 64-bitowa funkcja hashowa w Javie dla ciągów tekstowych?

Utwórz hash SHA-1, a następnie zamaskuj najniższe 64 bity.

long hash = string.hashCode();

Tak, najlepsze 32 bity będą równe 0, ale prawdopodobnie zabraknie Ci zasobów sprzętowych, zanim napotkasz problemy z kolizjami hash. HashCode w String jest dość wydajny i dobrze przetestowany.

Update Myślę, że powyższe spełnia najprostszą rzecz, która mogłaby ewentualnie działać , jednak zgadzam się z @sfussenegger pomysł rozszerzenia istniejącego hashcode łańcucha.

Oprócz dobrego hashCode dla Twojego ciągu, możesz rozważyć odświeżanie kodu hashowego w Twojej implementacji. Jeśli pamięć masowa jest używana przez innych programistów lub używana z innymi typami, może to pomóc w dystrybucji kluczy. Na przykład HashMap Java opiera się na tablicach skrótu o mocy dwóch długości, więc dodaje tę funkcję, aby zapewnić wystarczającą dystrybucję dolnych bitów.

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

Dlaczego nie użyć wielomianu CRC64. Są one w miarę wydajne i zoptymalizowane, aby upewnić się, że wszystkie bity są liczone i rozłożone na przestrzeni wyników.

Istnieje wiele implementacji dostępnych w sieci, jeśli wygooglujesz "CRC64 Java"

Zrób coś takiego:

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 pozwala na zapisywanie pierwiastków i łańcuchów i wysyłanie ich jako bajtów. Owinięcie ByteArrayOutputStream w nim pozwoli Ci zapisać do tablicy bajtów, która ładnie integruje się z MessageDigest. Możesz wybrać dowolny algorytm z listy tutaj .

Wreszcie BigInteger pozwoli Ci zamienić bajty wyjściowe w łatwiejszy w użyciu numer. Algorytmy MD5 i SHA1 produkują 128-bitowe hashów, więc jeśli potrzebujesz 64, możesz po prostu obciąć.

SHA1 powinien dobrze hashować prawie wszystko i przy rzadkich kolizjach (jest 128-bitowy). To działa z Javy, ale nie jestem pewien, jak to jest zaimplementowane. To może być dość szybkie. Działa to na kilku polach w mojej implementacji: po prostu wciśnij je wszystkie na DataOutputStream i gotowe. Możesz to zrobić nawet z refleksją i adnotacjami(może @HashComponent(order=1), aby pokazać, które pola mają hash i w jakiej kolejności). Ma 128-bitową odmianę i Myślę, że przekonasz się, że nie używa tyle CPU, ile myślisz, że będzie.

Użyłem takiego kodu, aby uzyskać hasze dla ogromnych zbiorów danych (do tej pory prawdopodobnie miliardów obiektów), aby móc je odłamywać w wielu sklepach zaplecza. Powinien działać na wszystko, czego potrzebujesz. Zauważ, że myślę, że możesz chcieć wywołać MessageDigest.getInstance() tylko raz, a następnie clone() od tego czasu: IIRC klonowanie jest o wiele szybsze.

Odwróć ciąg znaków, aby uzyskać kolejny 32-bitowy hashcode, a następnie połącz oba:

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

Jest to pseudokod; metoda String.reverse() nie istnieje I musi być zaimplementowana w inny sposób.

Odpowiedź na dziś (2018). Syf.

To będzie znacznie szybsze niż większość odpowiedzi tutaj, i znacznie wyższej jakości niż wszystkie z nich.

Biblioteka Guava ma jeden: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--

Czy patrzysz na Apache commons lang ?

Ale dla 64 bitów (i 128) potrzebne są pewne sztuczki: zasady zawarte w książce Effective Java autorstwa Joshuy Bloch pomogą Ci stworzyć 64 bitowy hash (wystarczy użyć long zamiast int). Dla 128 bitów potrzebujesz dodatkowych hacków...

Zastrzeżenie: to rozwiązanie ma zastosowanie, jeśli chcesz skutecznie hashować poszczególne słowa w języku naturalnym. Nieefektywne jest mieszanie dłuższego tekstu lub tekstu zawierającego znaki niealfabetyczne.

Nie znam funkcji, ale mam pomysł, który może pomóc:

• poświęć 52 Z 64 bitów na określenie, które litery są obecne w łańcuchu. Na przykład, gdyby 'a' było obecne, ustawiłbyś bit [0], dla 'B' ustawił bit 1, dla bitu zestawu " A " [26]. Że sposób, tylko tekst zawierający dokładnie ten sam zestaw liter miałby ten sam "podpis".

Można następnie użyć pozostałych 12 bitów do zakodowania długości łańcucha (lub jego wartości modulo) w celu dalszego zmniejszenia kolizji lub wygenerowania 12-bitowego hashCode za pomocą tradycyjnej funkcji haszującej.

Zakładając, że Twoje dane wejściowe są tekstowe-tylko mogę sobie wyobrazić, że spowodowałoby to bardzo niewiele kolizji i byłoby niedrogie do obliczenia(O (n)). W przeciwieństwie do innych rozwiązań do tej pory to podejście bierze pod uwagę dziedzinę problemu w celu zmniejszenia kolizji - opiera się na detektorze anagramów opisanym w perłach programistycznych (patrz tutaj ).