Creazione di un hash da diversi stringa oggetti Java

Question

quello che sarebbe il più veloce e più robusta (in termini di unicità) modo per implementare un metodo come

public abstract String hash(String[] values); 

Il values[] array ha da 100 a 1.000 membri, ciascuno di un che con poche decine di caratteri e il metodo deve essere eseguito circa 10.000 volte/sec su un diverso array values[] ogni volta.

Se una stringa lunga viene creata utilizzando un buffer StringBuilder e quindi un metodo hash richiamato sul contenuto del buffer, o è meglio continuare a richiamare il metodo hash per ogni stringa da values[]?

Ovviamente è necessario un hash di almeno 64 bit (ad es. MD5) per evitare collisioni, ma c'è qualcosa di più semplice e veloce che potrebbe essere fatto, con la stessa qualità?

Per esempio, per quanto riguarda

public String hash(String[] values) 
{ 
    long result = 0; 

    for (String v:values) 
    { 
     result += v.hashCode(); 
    } 

    return String.valueOf(result); 
} 

Answer 1

Sicuramente non utilizzare oltre pianura grazie alle sue proprietà di linearità, ma è possibile modificare il codice solo un po 'di raggiungere molto buona dispersione.

public String hash(String[] values) { 
    long result = 17; 
    for (String v:values) result = 37*result + v.hashCode(); 
    return String.valueOf(result); 
} 

Answer 2

Primo, il codice hash è in genere numerico, ad es. int. Inoltre la tua versione della funzione di hash crea int e quindi rende la sua rappresentazione di stringa che IMHO non ha alcun senso.

Mi piacerebbe migliorare il tuo metodo di hash come segue:

public int hash(String[] values) { 
    long result = 0; 
    for (String v:values) { 
     result = result * 31 + v.hashCode(); 
    } 
    return result; 
} 

dare uno sguardo su hashCode() implementato in classe java.lang.String

Answer 3

Si dovrebbe guardare fuori per la creazione di punti deboli quando si combinano metodi. (La funzione di hash java e la tua). Ho fatto una piccola ricerca sui codici a cascata, e questo è un esempio di ciò. (L'aggiunta potrebbe interferire con i meccanismi interni di hashCode()

Gli interni di hashCode() simile a questa:.

 for (int i = 0; i < len; i++) { 
      h = 31*h + val[off++]; 
     } 

numeri in modo sommando causeranno gli ultimi caratteri di tutte le stringhe nella matrice di Basta aggiungere, che non riduce la casualità (questo è già abbastanza grave per una funzione hash)

Se si desidera la pseudocasualità reale, dare un'occhiata all'algoritmo di hash FNV.È l'algoritmo hash più veloce là fuori appositamente progettato per l'utilizzo in HashMaps.

va in questo modo:

long hash = 0xCBF29CE484222325L; 
    for(String s : strings) 
    { 
     hash ^= s.hashCode(); 
     hash *= 0x100000001B3L; 
    } 

^Questo non è l'effettiva attuazione di FNV quanto prende interi come input invece di byte, ma penso che funziona altrettanto bene.

Answer 4

Non fornisce un hash a 64 bit, ma dato il titolo della domanda è probabilmente da menzionare che dal momento che Java 1.7 è java.util.Objects#hash(Object...).