programacion - huella hash

Función hash de muy bajo costo

Question

Necesito una función hash para una tabla Look Up, de modo que si mis valores van de 0 a N, necesito una función hash que me dé un valor de 0 a n, siendo n << N. Otra información es que yo ya sé N por adelantado.

He estado investigando sobre diferentes funciones de hash de bajo costo y solo he encontrado esto:

h = z mod n range(z) - 0 to N, range(h) - 0 to n

Mi función hash debe implementarse en HW, por lo que debe tener un costo muy bajo. ¿Alguien puede recomendar otra fórmula o algoritmo aparte de esa simple cosa ?. Cuando digo HW me refiero a una verdadera implementación en HW, y no a instrucciones en un microprocesador.

Gracias.

Actualiza con la solución

Gracias por toda la respuesta, no voy a seleccionar una favorita, porque todas son igualmente válidas según las características de la aplicación de destino.

Answer 1

CRC?

Ya hay mucho soporte de hardware para esto también.

Answer 2

La forma canónica de eso es h(x) = (a*x + b) mod n , donde a y b son constantes yn es el tamaño de tu tabla hash. Desea hacer n un número primo, para obtener una distribución óptima (ish).

Tenga en cuenta que esto es sensible a cierto tipo de distribuciones; por ejemplo, hacer solo x mod n depende principalmente de la aleatoriedad de los bits de bajo orden; si no son aleatorios en tu conjunto, obtendrás un sesgo bastante significativo.

Bob Jenkins ha diseñado varias funciones hashing muy buenas; aquí hay uno específicamente diseñado para ser simple de implementar en hardware: http://burtleburtle.net/bob/hash/nandhash.html

Para muchas funciones de hash diferentes, discusiones de diseño, etc., vea el resto del sitio: http://burtleburtle.net/bob/hash/

Answer 3

Si realmente está hablando de hardware (frente a software o implementación de hardware de software), y su número de cubos hash n puede escribirse como n = 2 ^m - 1, el más fácil es probablemente un registro de desplazamiento de realimentación lineal de longitud máxima ( LFSR) de los cuales CRC es una instancia.

Esta es una forma en que podría usar un registro de desplazamiento de m bits para crear un hash de un paquete de datos (asegúrese de que todos los datos estén representados consistentemente como una cadena de K bits, si tiene cadenas más cortas y rellene un extremo con ceros):

1. Inicialice el estado de la LFSR (CRC-32 usa todos los 1; todos los ceros probablemente sean malos)
2. Cambia los bits de tus datos
3. (Opcional) Shift en j ceros adicionales (j entre m y 2m es probablemente una buena opción); esto agrega un hashing adicional para reducir la correlación directa entre los bits de entrada / salida
4. Use el contenido del registro de desplazamiento m-bit como su valor hash.

Answer 4

Vuelva a conectar los bits en orden aleatorio y tome bits log2(n) más bajos

O simplemente tome bits log2(n) más bajos si sus datos están distribuidos uniformemente.

Answer 5

Creo que este es el mejor hash posible para este problema (más rápido que el módulo, mejor distribución), dado que todos sus números en 0..N tienen la misma probabilidad:

h = z * n / N;

Donde todos los valores son enteros, entonces tienes una división entera. De esta forma, cada valor entre 0..N se correlaciona exactamente con el mismo número de valores en n.

Por ejemplo, cuando n = 3 y N = 7 (los valores 3 y 7 no están incluidos en los rangos), los valores hash son los siguientes:

z * n / N = hash
----------------
0 * 3 / 7 = 0
1 * 3 / 7 = 0
2 * 3 / 7 = 0
3 * 3 / 7 = 1
4 * 3 / 7 = 1
5 * 3 / 7 = 2
6 * 3 / 7 = 2

Por lo tanto, cada valor de hash se usa con la misma frecuencia, justo en 1. Simplemente tenga cuidado de que n*(N-1) no se desborde.

Si N es una potencia de 2, puede reemplazar la división por desplazamiento. por ejemplo, si N = 256:

h = (z * n) >> 8;