Función hash perfecta mínima

Question

Tengo muchos enteros en el rango [0; 2^63-1]. Sin embargo, solo hay enteros de 10^8. Hay sin duplicados. La lista completa se conoce en tiempo de compilación, pero es , solo números aleatorios únicos. Estos números nunca cambian.
Para almacenar un número entero explícitamente, se requieren 8 bytes, y hay valores asociados de 1 byte, por lo que el almacenamiento explícito requiere aproximadamente 860 MB.
Así que quiero encontrar la función hash perfecta mínima para mapear cada uno de 10^8 enteros de [0; 2^63-1] a [0; 10^8-1]. Debería encontrar esta función solo una vez, los datos nunca cambian y la función puede ser complicada. Pero debe ser mínimo, perfecto y el cálculo debe ser rápido. ¿Cómo puedo hacer esto mejor? Tal vez es posible encontrar y utilizar algunas subsecuencias si ocurren?
Gracias.

Answer 1

Deje que su ordenador haga el trabajo por usted:

http://www.gnu.org/software/gperf/

Cita: ". Gperf GNU es un generador de funciones hash perfecta Para una lista dada de cuerdas, que produce una función hash y tabla hash, en forma de código C o C++, para buscar un valor dependiendo de la cadena de entrada. La función hash es perfecta, lo que significa que la tabla hash no tiene colisiones, y la búsqueda de tabla hash solo necesita una comparación de cadena. "

Answer 2

Estoy trabajando en an algorithm and Java implementation that needs less than 1.6 bits per key.

Anteriormente, he implementado a minimal perfect hash function tool in Java que necesita menos de 2,0 bits por clave.

Otros algoritmos se implementan en CMPH. Por ejemplo, CHD necesita aproximadamente 2,06 bits por tecla de manera predeterminada. Se puede configurar para usar menos espacio, pero la generación es más lenta.