c++ - mapa - Cadena para enterrar la función hash con precisión
set string c++ (4)
Quiero hacer un hash de una matriz char en un int o un long. El valor resultante debe adherirse a un valor de precisión dado. La función que he estado usando se da a continuación:
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);
}
La cadena a ser 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?
Cada hash tendrá colisiones. Período. Eso se llama un problema de cumpleaños .
Es posible que desee comprobar criptográfica tiene funciones como MD5 (relativamente rápido y no le importa que es inseguro), pero también tendrá colisiones.
La definición misma de un hash es que produce valores duplicados para algunos valores, debido a que el rango de valores hash es más pequeño que el espacio de los datos hash.
En teoría, un hash de 32 bits tiene suficiente rango para hash all ~ 6 cadenas de caracteres (AZ, az, 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 hash después de hash ~ 16 bits de entradas aleatorias, debido a la paradoja del 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 menos log(|data set|) . Sin embargo, requiere que conozcas todos los posibles valores de datos antes de tiempo. Esto se llama hashing perfecto .
Dicho esto, aquí hay algunas alternativas que deberían ayudarte a comenzar (están diseñadas para minimizar las colisiones)
Los valores hash generan el mismo valor para diferentes entradas, 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) para minimizar esas colisiones. Ya que tiene esta restricción de precisión adicional (0-5?), Entonces tendrá colisiones mucho más a menudo.