djb2 funzione hash

Question

Sto usando l'algoritmo djb2 per generare la chiave hash per una stringa che è la seguente

hash(unsigned char *str) 
{ 
    unsigned long hash = 5381; 
    int c; 

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

    return hash; 
} 

Ora con ogni ciclo c'è una moltiplicazione con due grandi numeri, Dopo un po 'di tempo con il 4 ° del 5 ° carattere della stringa c'è un overflow di come il valore hash diventa enorme

Qual è il modo corretto di refactoring in modo che il valore hash non trabocchi e l'hashing avviene anche in modo corretto

Answer 1

calcoli hash spesso overflow. In genere non è affatto un problema, a patto che tu abbia delle garanzie su ciò che accadrà quando lo compie l'overflow. Non dimenticare che il punto di un hash non è quello di avere un numero che significa qualcosa in termini di magnificenza, ecc. - è solo un modo per scoprire l'uguaglianza. Perché l'overflow interferirebbe con quello?

Answer 2

Non dovresti farlo. Poiché non esiste alcun modulo, l'overflow dei numeri interi è il comportamento previsto per la funzione (ed è stato progettato tenendo presente questo fatto). Perché vuoi cambiarlo?

Answer 3

Sto pensando di utilizzare un analizzatore statico/di runtime per avvertire di overflow integer? Bene, questo è uno di quei casi in cui è possibile ignorare l'avviso. Le funzioni di hash sono progettate per tipi specifici di proprietà, quindi non preoccuparti degli avvisi del tuo analizzatore. Non provare a creare autonomamente una funzione hash!

Answer 4

ritorno (hash & 0xFFFFFFFF); // o qualunque maschera tu voglia, non importa fintanto che la mantieni coerente.