djb2 función hash

Question

estoy usando el algoritmo djb2 para generar la clave hash para una cadena que es el siguiente

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

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

    return hash; 
} 

Ahora con cada bucle existe una multiplicación de dos números grandes, después de algún tiempo con el cuarto del quinto carácter de la cadena hay un desbordamiento como el valor hash se pone muy grande

¿Cuál es la forma correcta de refactorizar para que el valor hash no se desborde y el hash también pasa correctamente

Answer 1

cálculos Hash menudo desbordamiento. Eso generalmente no es un problema en absoluto, siempre y cuando tengas garantías sobre lo que sucederá cuando haga desbordamiento. No olvide que el objetivo de un hash es no tener un número que signifique algo en términos de magniture, etc., es solo una forma de detectar la igualdad. ¿Por qué el desbordamiento interferiría con eso?

Answer 2

No deberías hacer eso. Como no hay módulo, el desbordamiento de enteros es el comportamiento esperado de la función (y se diseñó teniendo esto en cuenta). por que lo quieres cambiar?

Answer 3

Estoy pensando en utilizar un analizador estático/de tiempo de ejecución para advertir sobre desbordamientos de enteros? Bueno, este es uno de esos casos en los que puedes ignorar la advertencia. Las funciones hash están diseñadas para tipos específicos de propiedades, por lo que no debe preocuparse por las advertencias de su analizador. ¡No intente crear una función hash usted mismo!

Answer 4

return (hash & 0xFFFFFFFF); // o la máscara que quieras, no importa mientras la mantengas constante.