Che cosa è una buona funzione di hash a 64 bit in Java per le stringhe testuali?

Question

Sto cercando una funzione di hash che:

1. hash stringhe testuali e (per esempio alcuni contatti)
2. è scritto in Java, e ampiamente utilizzato
3. Bonus: opere in diversi campi (invece di me li concatenare e applicando l'hash sulla stringa concatenata)
4. Bonus:. Ha una variante a 128 bit
5. Bonus:. Non per la CPU

Answer 1

Perché non si utilizza una variante long del String.hashCode() default (dove alcuni ragazzi davvero in gamba certamente mettere impegno nel rendere esso efficiente - senza menzionare le migliaia di occhi per gli sviluppatori che già consultato la pagina di questo codice)?

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

Se siete alla ricerca di ancora più bit, probabilmente si potrebbe utilizzare un BigInteger Edit:

Come ho già detto in un commento alla risposta di @brianegge, non ci sono molte casi d'uso per gli hash con più di 32 bit e molto probabilmente non uno solo per gli hash con più di 64 bit:

  

potevo immaginare un enorme tabella hash distribuita in decine di server, forse la memorizzazione di decine di miliardi di mappature. Per un tale scenario, @brianegge ha ancora un valido punto qui: 32 bit permettono di 2 ^ 32 (circa 4,3 miliardi) diverse chiavi di hash. Ipotizzando una procedura forte, si dovrebbe comunque avere non poche collisioni. Con 64 bit (18,446,744,073 miliardi di chiavi diverse) il vostro sicuramente risparmiare, a prescindere di qualsiasi scenario folle ne avete bisogno per. Pensando di casi d'uso per 128 chiavi bit (340,282,366,920,938,463,463,374,607,431 miliardi di possibili chiavi) è praticamente impossibile però.

Per combinare l'hash per diversi campi, semplicemente fare un XOR moltiplicare uno con un primo e aggiungerli:

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

Il piccolo principale è lì per evitare il codice hash per uguali valori commutati, cioè { 'foo', 'bar'} e { 'bar', 'foo'} non sono uguali e dovrebbe avere un codice hash diverso. XOR è male come si restituisce 0 se entrambi i valori sono uguali. Pertanto, { 'foo', 'foo'} e { 'bar', 'bar'} avrebbero lo stesso codice hash.

Answer 2

Crea un hash SHA-1 e quindi mascherare i 64bits più bassi .

Answer 3

long hash = string.hashCode();

Sì, i primi 32 bit saranno 0, ma è probabilmente a corto di risorse hardware prima di eseguire in problemi con collisioni hash. Il hashCode nella stringa è abbastanza efficiente e ben collaudato.

Aggiorna Credo che le soddisfa sopra il cosa più semplice che potrebbe lavorare , però, sono d'accordo con @sfussenegger idea di estendere il hashCode stringa esistente.

Oltre ad avere una buona hashCode per la vostra String, si può prendere in considerazione rimasticare il codice hash nell'implementazione. Se la memoria viene utilizzato da altri sviluppatori, o utilizzati con altri tipi, questo può aiutare a distribuire le chiavi. Ad esempio, HashMap di Java si basa su potenze di due tabelle lunghezza hash, quindi si aggiunge questa funzione per assicurare i bit inferiori sono sufficientemente distribuiti.

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

Answer 4

Perché non usare un polinomio CRC64. Questi sono ragionevolmente efficiente e ottimizzato per assicurarsi che tutti i bit vengono contati e si sviluppa su spazio risultato.

Ci sono un sacco di implementazioni disponibili in rete se google "CRC64 Java"

Answer 5

fare qualcosa di simile:

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 vi permette di scrivere le primitive e archi e li hanno uscita come byte. Avvolgendo un ByteArrayOutputStream in esso vi permetterà di scrivere in un array di byte, che si integra perfettamente con MessageDigest . È possibile scegliere da un qualsiasi algoritmo elencato qui .

BigInteger consentirà di spegnere i byte di uscita in un numero facile da usare. Gli algoritmi MD5 e SHA1 entrambi producono gli hash di 128 bit, quindi se avete bisogno 64 si può solo troncare.

SHA1 dovrebbe hash quasi tutto bene, e con le collisioni frequenti (è a 128-bit). Questo funziona da Java, ma non sono sicuro di come è implementato. Potrebbe in effetti essere abbastanza veloce. Funziona su diversi campi della mia realizzazione: basta spingere tutto sul DataOutputStream e siete a posto. Si potrebbe anche farlo con la riflessione e le annotazioni (forse @HashComponent(order=1) per mostrare quali campi andare in un hash e in quale ordine). Essa ha avuto una variante a 128 bit e penso che lo troverete non usa più CPU come si pensa che lo farà.

Ho usato il codice come questo per ottenere gli hash per insiemi di dati enormi (ormai probabilmente miliardi di oggetti) per essere in grado di coccio loro attraverso molti negozi di back-end. Dovrebbe funzionare per tutto ciò che serve per. Si noti che penso che si può decidere di sola chiamata MessageDigest.getInstance() una volta e poi clone() da allora in poi:. IIRC la clonazione è molto più veloce

Answer 6

Invertire la stringa per ottenere un altro a 32 bit codice hash e poi unire i due:

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

Questa è pseudocodice; il metodo String.reverse() non esiste e dovrà essere attuato in qualche altro modo.

Answer 7

Una risposta per oggi (2018). SipHash.

Sarà molto più veloce rispetto alla maggior parte delle risposte qui, e significativamente più alta qualità di tutti loro.

La biblioteca Guava ha uno: https://google.github.io/guava/releases/23.0/api/docs/com/google/common/hash/Hashing.html#sipHash24--

Answer 8

Non si guarda a Apache Commons Lang ?

Ma per 64 bit (e 128) è necessario qualche trucco: le norme previste nel libro Effective Java da Joshua Bloch aiuterà a creare a 64 bit di hash facile (basta usare a lungo al posto di int). Per 128 bit è necessario hack supplementari ...

Answer 9

NOTA BENE: Questa soluzione è applicabile se si desidera hash in modo efficiente le singole parole in linguaggio naturale. E 'inefficiente per hashing testo più lungo, o il testo che contiene caratteri non alfabetici.

Io non sono a conoscenza di una funzione, ma qui è un'idea che potrebbe aiutare:

• Dedicate 52 dei 64 bit per rappresentare quali lettere sono presenti nella stringa. Ad esempio, se 'a' erano presenti quando si imposta po '[0], per 'b' bit impostato 1 , per 'a' bit impostato [26]. In questo modo, solo il testo che contiene esattamente lo stesso insieme di lettere avrebbe lo stesso "firma".

È quindi possibile utilizzare i rimanenti 12 bit per codificare la lunghezza della stringa (oppure un valore modulo di esso) per ridurre ulteriormente le collisioni, o generare un 12 bit hashCode utilizzando una funzione di hashing tradizionale.

Supponendo che l'input è di solo testo Posso immaginare questo si tradurrebbe in pochissimi collisioni e sarebbe poco costoso per calcolare (O (n)). A differenza di altre soluzioni finora questo approccio prende il dominio del problema in considerazione per ridurre le collisioni - Si basa fuori il rilevatore Anagram descritto in perle di programmazione (vedi qui ).