calcola un numero di hash, cosa fa esattamente e perché?

Question

So che questa funzione sta facendo qualcosa con i numeri di hash, ma non ha capito esattamente lo scopo di questa funzione? perché "res * 31 + * chiave"? perché 31?

unsigned int HashAlg(char* key) 
{ 
    unsigned int res = 0; 

    while (*key != 0) 
    { 
     res = res * 31 + *key; 
     ++key; 
    } 

    return res; 
} 

Answer 1

perché "res * 31 + * tasto"

Supponiamo che cosa succede se si trattasse solo res = res + *key; allora l'hash dovrebbe solo sommare tutti i valori nella chiave. Ciò produrrebbe lo stesso hash per stringhe permute come ciao, elloh, olleh, loleh, ecc. Moltiplicare con un valore> 1 lo rende molto meno probabile.

why 31?

Probabilmente per evitare una potenza di 2 che semplicemente sposterebbe a sinistra un valore e lo perderà dopo alcuni turni. Una non potenza di 2 evita questo problema.

Answer 2

L'implementazione è una variante di una funzione di hash della stringa moltiplicativa di D.J. Bernstein:

unsigned djb_hash (void *key, int len) 
{ 
    unsigned char *p = key; 
    unsigned h = 0; 
    int i; 

    for (i = 0; i < len; i++) 
    h = 33 * h + p[i]; 

    return h; 
} 

Lo scopo di funzioni hash come questi è quello di mappare una chiave di ricerca, come la corda "item1", ad un indice che può essere utilizzato in una tabella hash, una cache, ecc .; semplicisticamente, il valore hash ci dà il posto nella tabella in cui deve essere memorizzato il record corrispondente per "item1". Le tabelle hash, a loro volta, vengono utilizzate per implementare array associativi e insiemi dinamici. Per maggiori dettagli, consiglio di iniziare dal Wikipedia page.

È possibile notare che nella propria implementazione, la costante 33 è stata modificata per 31. Non c'è molto lavoro matematico reale che possa provare definitivamente la relazione tra numeri primi e funzioni di hashing. Il concetto base dell'uso dei numeri primi nelle funzioni hash ruota attorno al concetto di trasformazione dello stato corrente della funzione hash (applicando una qualche forma di operazione matematica come la moltiplicazione o l'aggiunta al valore hash). Il risultato è vincolato ad essere un nuovo valore di hash che dovrebbe avere statisticamente un valore entropico più alto o in altre parole un bit-bias molto basso per uno qualsiasi dei bit nel nuovo valore di hash. In termini semplici, quando si moltiplica un insieme di numeri casuali per un numero primo, i numeri risultanti (se analizzati a livello di bit) non dovrebbero mostrare alcun pregiudizio verso l'essere uno o l'altro, ovvero P(Bi = 1) ~= 0.5. Non c'è alcuna prova concreta che questo sia il caso o che avvenga solo con numeri primi, sembra solo un'intuizione auto-proclamata che sembra essere obbligata a seguire. Queste proprietà sono giudicate a posteriori, nel senso che cerchiamo di analizzare le proprietà della funzione hash (o PRNG) con costanti scelte e sviluppare un'intuizione che le costanti "funzionano bene", cioè producendo specifiche distribuzioni o dimostrando un effetto valanga, producono una distribuzione uniforme per un insieme specifico di input, ecc.