Perché 5381 e 33 sono così importanti nell'algoritmo djb2?

Question

Il djb2 algorithm ha una funzione di hash per le stringhe.

unsigned long hash = 5381; 
int c; 

while (c = *str++) 
    hash = ((hash << 5) + hash) + c; /* hash * 33 + c */ 

Perché 5381 e 33 sono così importanti?

Answer 1

Forse perché 33 == 2^5 + 1 e molti algoritmi di hashing utilizzano 2^n + 1 come moltiplicatore?

credito al Jerome Berger

Aggiornamento:

Ciò sembra essere confermato dalla versione corrente del djb2 pacchetto software originariamente provenivano da: cdb

Le note sono collegate per descrivere il cuore di l'algoritmo di hashing che utilizza h = ((h << 5) + h)^c per eseguire l'hashing ... x << 5 è un modo hardware veloce per utilizzare 2^5 come moltiplicatore.

Answer 2

In 5381, Dan Bernstein (djb2) dice in this article:

[...] praticamente ogni buon moltiplicatore funziona. Penso che ti preoccupi del fatto che 31c + d non copre un intervallo ragionevole di valori di hash se c e d sono compresi tra 0 e 255. Ecco perché, quando ho scoperto la funzione di hash 33 e ho iniziato ad usarlo nei miei compressori, ho avviato con un valore hash di 5381. Penso che troverete esattamente questo come e un moltiplicatore 261.

L'intero thread è here se sei interessato.

Ozan Yigit ha a page on hash functions che dice:

[...] la magia del numero 33 (perché funziona meglio di molti altri costanti, primo o no) non è mai stato adeguatamente spiegato.

Answer 3

Questa funzione hash è simile ad un Linear Congruential Generator (LCG - una semplice classe di funzioni che generano una serie di numeri pseudo-casuali) che ha generalmente la forma:

X = (a * X) + c; // "mod M", where M = 2^32 or 2^64 typically 

nota la somiglianza con il Funzione hash djb2 ... a = 33, M = 2^32. Affinché un LCG di avere un "periodo di pieno" (cioè come casuale come può essere), un deve avere determinate proprietà:

• a-1 è divisibile per tutti i fattori primi di M (a- 1 è 32, che è divisibile per 2, l'unico fattore primo di 2^32)
• a-1 è un multiplo di 4 se M è un multiplo di 4 (sì e sì)

Inoltre , c e M si suppone che siano relativamente primi (che sarà vero per valori dispari di c).

Come si può vedere, questa funzione di hash assomiglia un po 'a un buon LCG.E quando si tratta di funzioni di hash, ne vuoi una che produca una distribuzione "casuale" di valori hash dato un insieme realistico di stringhe di input.

Per quanto riguarda il motivo per cui questa funzione di hash è buona per le stringhe, penso che abbia un buon bilanciamento di essere estremamente veloce, fornendo al tempo stesso una distribuzione ragionevole dei valori hash. Ma ho visto molte altre funzioni di hash che affermano di avere caratteristiche di output molto migliori, ma coinvolte molte più linee di codice. Per esempio vedere this page about hash functions

MODIFICA: This good answer spiega perché 33 e 5381 sono stati scelti per motivi pratici.

Answer 4

33 è stato scelto perché:

1) Come detto prima, la moltiplicazione è facile da calcolare utilizzando shift e aggiungere.

2) Come si può vedere dallo spostamento e aggiungere l'implementazione, l'utilizzo di 33 crea due copie della maggior parte dei bit di input nell'accumulatore di hash, quindi distribuisce quei bit relativamente distanti tra loro. Questo aiuta a produrre una buona valanga. L'uso di uno spostamento più ampio duplicherebbe meno bit, utilizzando uno spostamento più piccolo si manterrebbero le interazioni tra i bit più locali e ci sarebbe voluto più tempo prima che le interazioni si diffondessero.

3) Lo spostamento di 5 è relativamente primo a 32 (il numero di bit nel registro), che aiuta con la valanga. Mentre nella stringa ci sono abbastanza caratteri, ogni bit di un byte di input alla fine interagirà con ogni bit precedente di input.

4) Lo spostamento di 5 è una buona quantità di spostamento quando si considerano i dati dei caratteri ASCII. Un carattere ASCII può essere pensato come un selettore di tipo di carattere a 4 bit e un selettore di tipo di carattere a 4 bit. Per esempio. le cifre hanno tutte 0x3 nei primi 4 bit. Quindi uno spostamento a 8 bit causerebbe bit con un determinato significato per interagire principalmente con altri bit che hanno lo stesso significato. Uno spostamento a 4 o 2 bit produrrebbe allo stesso modo forti interazioni tra bit simili. Lo spostamento a 5 bit fa sì che molti dei quattro bit di ordine basso di un personaggio interagiscano fortemente con molti dei 4 bit superiori nello stesso carattere.

Come affermato altrove, la scelta di 5381 non è troppo importante e molte altre scelte dovrebbero funzionare anche qui.

Questa non è una funzione di hash veloce poiché elabora l'immissione di un carattere alla volta e non tenta di utilizzare il parallelismo a livello di istruzione. È, tuttavia, facile da scrivere. La qualità dell'output diviso per la facilità di scrittura del codice è probabile che colpisca un punto debole.

Sui processori moderni, la moltiplicazione è molto più veloce di quando è stato sviluppato questo algoritmo e altri fattori di moltiplicazione (ad esempio 2^13 + 2^5 + 1) possono avere prestazioni simili, risultati leggermente migliori ed essere leggermente più facili da Scrivi.

Contrariamente a una risposta sopra, una buona funzione di hash non crittografica non vuole produrre un output casuale. Invece, dati due input che sono quasi identici, vuole produrre output molto diversi. Se i valori di input sono distribuiti casualmente, non hai bisogno di una buona funzione di hash, puoi semplicemente utilizzare un insieme arbitrario di bit dal tuo input. Alcune delle funzioni di hash moderne (Jenkins 3, Murmur, probabilmente CityHash) producono una migliore distribuzione degli output rispetto agli input casuali che sono molto simili.