Algoritmo de Flacolet-Martin: Pregunta sobre el uso de ciertas funciones de hash
-
29-09-2020 - |
Pregunta
Esta es una pregunta dada en un PDF sobre los algoritmos de transmisión (esto no es una asignación pero estoy tratando de entender)
Ejercicio 4.4.1 : Supongamos que nuestro flujo consiste en los enteros 3, 1, 4, 1, 5, 9, 2, 6, 5. Nuestras funciones hash serán todas del formulario H (x)= AX + B MOD 32 para algunos A y B. Debes tratar el resultado como un 5 bits. entero binario. Determine la longitud de la cola para cada elemento de la corriente y la estimación resultante de la cantidad de elementos distintos si el hash La función es:
(a) h (x)= 2x + 1 mod 32.
(b) h (x)= 3x + 7 mod 32.
(c) h (x)= 4x mod 32.
! Ejercicio 4.4.2 : ¿Ve algún problema con la elección de hash? Funciones en el ejercicio 4.4.1? ¿Qué consejo podrías dar a alguien que iba a usar una función hash de la forma H (x)= AX + B MOD 2K?
Ya he resuelto el primer ejercicio, encontrando una longitud máxima de la cola R de 0 para (a) y 4 para (B) y (c), por lo tanto, la estimación resultante de elementos distintos es respectivamente 1,16,16. (No se le pide que haga promedios / medianos de las funciones de hash para encontrar un mejor valor)
Sin embargo, ¡parece que no puedo imaginar la respuesta al segundo ejercicio? ¿Es simplemente elegir 'A' y 'B' de una manera determinada? ¿O son estas funciones, no son buenas para generar números igualmente aleatorios con 0s de arrastre y sin 0s de arrastre?
Gracias de antemano
Puede observar los resultados de cada Hosth Funciones ejecutando este código: https://onlinegdb.com/rjxc4f4vl
Solución
Sin embargo, ¡parece que no puedo imaginar la respuesta al segundo ejercicio?¿Es simplemente elegir 'A' y 'B' de una manera determinada?¿O son estas funciones, no son buenas para generar números igualmente aleatorios con 0s de arrastre y sin 0s de arrastre?
Tienes la idea correcta.Creo que lo que la pregunta está tratando de sugerir es que esta función hash tiene un problema con ciertos valores de $ a $ y $B $ .Considere, en particular, $ A= 16 $ .¿Qué pasará con la función hash en ese caso?¿Cuántos valores posibles hay?
Entonces, para elegir un buen valor de $ a $ , probablemente deberíamos asegurarnos de que $ A= 16 $ no está permitido. $ a= 8 $ tampoco es bueno.¿Qué sugieres es una buena opción para $ a $ ?