Algoritmo de Flacolet-Martin: Pregunta sobre el uso de ciertas funciones de hash

Question

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

Answer 1

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 $ ?