Hashing de valores de puntero

Question

Algunas veces necesita tomar una función hash de un puntero; no el objeto al que apunta el puntero, sino el puntero en sí mismo. Muchas veces, la gente simplemente selecciona y usa el valor del puntero como un entero, cortan algunos bits altos para que quepa, quizás cambien de bits conocidos a cero en la parte inferior. La cosa es que los valores del puntero no están necesariamente bien distribuidos en el espacio del código; de hecho, si su asignador está haciendo su trabajo, existe una gran posibilidad de que estén todos agrupados.

Entonces, mi pregunta es, ¿alguien ha desarrollado funciones hash que sean buenas para esto? Tome un valor de 32 o 64 bits que tal vez tenga 12 bits de entropía en él en algún lugar y extiéndalo uniformemente en un espacio de números de 32 bits.

Answer 1

This page enumera varios métodos que pueden ser de utilidad. Uno de ellos, debido a Knuth, es un simple como multiplicar (en 32 bits) por 2654435761, pero "se producen malos resultados hash si las claves varían en los bits superiores". En el caso de los punteros, esa es una situación bastante rara.

Here son algunos algoritmos más, que incluyen pruebas de rendimiento.

Parece que las palabras mágicas son "hashing entero".

Answer 2

¿Por qué no usar simplemente un hash function existente?

Answer 3

Es probable que muestren localidad, sí, pero en los bits inferiores, lo que significa que los objetos se distribuirán a través de la tabla hash. Solo verá colisiones si la dirección de un puntero es un múltiplo de la longitud del hashtable desde otro puntero.

Answer 4

Si conoce la dirección del puntero más baja posible (que a menudo es el caso si está trabajando dentro de un gran buffer), simplemente convierta el puntero a un entero restando el valor del puntero más bajo posible; p.ej. esa podría ser la dirección base del buffer. -Recuerda: el puntero restado del puntero es igual a un desplazamiento (entero). Entonces: No "corte" bits; es mucho mejor convertir a un desplazamiento. Esto dará como resultado que el valor de compensación sea mucho menor que el valor de un puntero. Puede ayudar aún más cambiar el valor del puntero a la derecha dos veces (por ejemplo, dividir entre 4) en algunos casos también, antes de hash. El problema con los punteros es que a menudo se asignan pequeños bloques de memoria en la misma dirección (por ejemplo, se libera un bloque y otro bloquea el lugar del bloque liberado).