función Hash para los flotadores

Question

Actualmente estoy poniendo en práctica una tabla hash en C++ y yo estoy tratando de hacer una función hash para los flotadores ...

que iba a tratar a los flotadores como enteros rellenando los números decimales, pero luego me di cuenta de que probablemente alcanzaría el desbordamiento con grandes números ...

¿Hay una buena manera de llevar las carrozas?

Usted no tiene que darme directamente a la función, pero me gustaría ver/entender diferentes conceptos ...

Notas:

1. no lo necesita para ser realmente rápido, distribuido de manera uniforme si es posible.

2. He leído que los flotadores no deben ser hash debido a la velocidad de los cálculos, ¿alguien puede confirmar/explicar esto y darme otras razones por las que los flotadores no deben ser hash? Realmente no entiendo por qué (además de la velocidad)

Answer 1

Depende de la aplicación, pero la mayoría de las veces no debe ser hasheada porque el hash se usa para búsqueda rápida de coincidencias exactas y la mayoría de los flotantes son el resultado de cálculos que producen un flotador que es solo una aproximación a la respuesta correcta. La forma habitual de comprobar la igualdad flotante es verificar si está dentro de algún delta (en valor absoluto) de la respuesta correcta. Este tipo de comprobación no se presta para las tablas de búsqueda hash.

EDITAR:

Normalmente, debido a errores de redondeo y las limitaciones inherentes de la aritmética de punto flotante, si espera que los números de punto flotante a y b debe ser igual a la otra, porque las matemáticas lo dice, es necesario para elegir relativamente pequeño delta > 0, y luego declara a y b para que sea igual si abs(a-b) < delta, donde abs es la función de valor absoluto. Para más detalles, vea this article.

Aquí hay un pequeño ejemplo que muestra el problema:

float x = 1.0f; 
x = x/41; 
x = x * 41; 
if (x != 1.0f) 
{ 
    std::cout << "ooops...\n"; 
} 

Dependiendo de la plataforma, compilador y optimización de los niveles, esto puede imprimir ooops... a la pantalla, lo que significa que la ecuación matemática x/y * y = x no es necesariamente válida en tu computadora.

Existen casos en los que la aritmética de punto flotante produce resultados exactos, p. números enteros y racionales de tamaño razonable con denominadores de potencia de 2.

Answer 2

unsigned hash(float x) 
{ 
    union 
    { 
     float f; 
     unsigned u; 
    }; 
    f = x; 
    return u; 
} 

comportamiento Técnicamente no definido, pero la mayoría de los compiladores apoyar esto. solución alternativa:

unsigned hash(float x) 
{ 
    return (unsigned&)x; 
} 

Ambas soluciones dependen del orden de bits de su máquina, así que por ejemplo en x86 y SPARC, producirán resultados distintos. Si eso no te molesta, solo usa una de estas soluciones.

Answer 3

Si su función hash hizo lo siguiente se obtendría algún grado de falta de claridad en la búsqueda de hash

unsigned int Hash(float f) 
{ 
    unsigned int ui; 
    memcpy(&ui, &f, sizeof(float)); 
    return ui & 0xfffff000; 
} 

esta manera usted enmascarar los 12 bits menos significativos que permitan un grado de incertidumbre .. Sin embargo, realmente depende de tu aplicación.

Answer 4

Puede, por supuesto, representan un float como un tipo del mismo tamaño int para discutir a ella, sin embargo, este enfoque ingenuo tiene algunas trampas que hay que tener cuidado de ...

Simplemente conversión a una representación binaria es propenso a errores ya que los valores que son iguales no necesariamente tienen la misma representación binaria.

Un caso obvio: -0.0 no coincidirá con 0.0 por ejemplo. *

Además, simplemente convertir a un int del mismo tamaño costumbre dan muy incluso distribución, que a menudo es importante (la aplicación de un hash/set que utiliza cubos por ejemplo).

pasos sugeridos para la implementación:

• filtrar los casos que no son finitos (nan, inf) y (0.0, -0.0si usted necesita para hacer esto de manera explícita o no depende del método utilizado).
• convertir en un int del mismo tamaño
  (es decir - utilizar una unión por ejemplo para representar el float como un int, no simplemente echados a un int).
• redistribuye los bits, (¡intencionalmente vago aquí!), esto es básicamente una compensación de velocidad vs. calidad. Pero si tiene muchos valores en un rango pequeño, probablemente tampoco los quiera en un rango similar.

*: Es posible que wa no para comprobar si hay (nan y -nan) también. Cómo manejarlos depende exactamente de su caso de uso (es posible que desee ignorar el signo de todos los nan como lo hace CPython).

de Python _Py_HashDouble es una buena referencia para saber cómo es posible que un hash de float, en el código de producción (ignorar el cheque -1 al final, ya que es un valor especial para Python).

Answer 5

Puede usar el hash std, no es mala:

std::size_t myHash = std::cout << std::hash<float>{}(myFloat); 

Answer 6

Si está interesado, acabo de hacer una función hash que utiliza coma flotante, y se puede dispersar flotadores. También pasa SMHasher (que es la principal prueba de polarización para las funciones hash no criptográficas). Es mucho más lento que las funciones hash no criptográficas normales debido a los cálculos de flotación.

No estoy seguro de si tifuhash será útil para todas las aplicaciones, pero es interesante ver una función de coma flotante simple pasar tanto PractRand como SMHasher.

La principal función de actualización de estado es muy simple, y se parece a:

function q(state, val, numerator, denominator) { 
    // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction" 
    // with denominator = val + pos/state[1] 
    state[0] += numerator/denominator; 
    state[0] = 1.0/state[0]; 

    // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1 
    state[1] += val; 
    state[1] = numerator/state[1]; 
} 

De todos modos, se puede get it on npm O puede check out the github

El uso es simple:

const tifu = require('tifuhash'); 

const message = 'The medium is the message.'; 
const number = 333333333; 
const float = Math.PI; 

console.log(tifu.hash(message), 
    tifu.hash(number), 
    tifu.hash(float), 
tifu.hash()); 

Hay una demostración de algunos hashes en runkit aquí https://runkit.com/593a239c56ebfd0012d15fc9/593e4d7014d66100120ecdb9

Nota al margen: creo que en el futuro, usar coma flotante, posiblemente grandes matrices de cálculos en coma flotante, podría ser una forma útil de hacer más funciones hash computacionalmente exigentes en el futuro. Un extraño efecto secundario que descubrí al utilizar el punto flotante es que los hashes dependen del objetivo, y supongo que tal vez podrían usarse para tomar las huellas digitales de las plataformas en las que se calcularon.