Pregunta sobre c++, hash – Cadena a la función de hash entero con precisión

4

Quiero un hash de una matriz de caracteres en un int o un largo. El valor resultante tiene que adherirse a un valor de precisión dado. La función que he estado usando se da a continuación:

<code>int GetHash(const char* zKey, int iPrecision /*= 6*/)
{
        /////FROM : http://courses.cs.vt.edu/~cs2604/spring02/Projects/4/elfhash.cpp

        unsigned long h = 0;
        long M = pow(10, iPrecision);

        while(*zKey)
        {
                h = (h << 4) + *zKey++;
                unsigned long g = h & 0xF0000000L;
                if (g) h ^= g >> 24;
                h &= ~g;
        }            

        return (int) (h % M);
}
</code>

La cadena que se va a hash es similar a "SAEUI1210.00000010_1".

Sin embargo, esto produce valores duplicados en algunos casos. ¿Hay alguna buena alternativa que no duplique el mismo hash para diferentes valores de cadena?

Intente usar CRC 32:en.wikipedia.org/wiki/Crc32 Akira Yamamoto

Tu respuesta

4   la respuesta
13

algunos valores, debido a que el rango del valor de hash es más pequeño que el espacio de los datos hash.

En teoría, un hash de 32 bits tiene un rango suficiente para agrupar todas las cadenas de ~ 6 caracteres (A-Z, a-z, 0-9 solamente), sin causar una colisión. En la práctica, los hashes no son una permutación perfecta de la entrada. Dado un hash de 32 bits, puede esperar obtener colisiones de hash después del hashing ~ 16 bit de entradas aleatorias, debido aparadoja de cumpleaños.

Dado un conjunto estático de valores de datos, siempre es posible construir una función hash diseñada específicamente para ellos, que nunca colisionará consigo misma (por supuesto, el tamaño de su salida será al menoslog(|data set|). Sin embargo, requiere que conozca todos los valores de datos posibles con anticipación. Se llamahashing perfecto.

Habiendo dicho eso,aquí Hay algunas alternativas que deberían ayudarle a comenzar (están diseñadas para minimizar las colisiones)

La única forma de probar qué función hash es la "mejor" para sus propósitos, es realizar un punto de referencia en una muestra de datos que se ajuste a sus datos reales esperados. La función que está utilizando no intenta mezclar los bits de entrada con demasiada fuerza para crear un hash: en cada paso, como máximo, se mezclan los 4 bits más altos; y en cadenas de longitud <8, incluso eso no sucede, su hash simplemente acumula todos los caracteres, con un poco de superposición. ASk
¿Cuál es la mejor función de hash para usar fuera de las que figuran en el enlace que proporcionó y la que estoy usando en este momento? La función que estoy usando parece ser más compleja que djb2 y sdbm. ¿Eso significa que es mejor para evitar las colisiones? Gayan
2

Problema de cumpleaños.

Es posible que desee comprobar que el criptográfico tiene funciones como MD5 (relativamente rápido y no le importa que sea inseguro) pero también tendrá colisiones.

Los hashes perfectos por definición no lo hacen. MSalters
1

MD5 oSHA. Hay muchas implementaciones abiertas y es muy poco probable que el resultado produzca un resultado duplicado.

Sí. Pero mi requisito también incluye el hecho de que el resultado debe ser un número entero. Los hashes MD5 contienen ints y caracteres. Creo que es lo mismo para los algoritmos SHA. Gayan
Es cierto, pero la conversión es trivial: de 128 a 32 bits de entero. Obtendrá un código de 2 líneas (hash, conversión int) que produce un hash de colisión sin facto. Adam Matan
2

eso es lo que hacen. Todo lo que puede hacer es crear una función hash con suficiente distribución o profundidad de bits (o ambas cosas) para minimizar esas colisiones. Ya que tienes esta restricción adicional de precisión (0-5?), Entonces vas a golpear colisiones con mucha más frecuencia.

Preguntas relacionadas