Algorithme de Flajolet-Martin: Question sur l'utilisation de certaines fonctions de hachage

Question

Ceci est une question donnée dans un PDF sur les algorithmes de streaming (ce n'est pas une mission mais j'essaie de comprendre)

EXERCICE 4.4.1 : Supposons que notre flux se compose des entiers 3, 1, 4, 1, 5, 9, 2, 6, 5. Nos fonctions de hachage seront toutes de la forme H (x)= AX + B MOD 32 pour certains A et B. Vous devriez traiter le résultat comme un 5 bits Entier binaire. Déterminer la longueur de la queue pour chaque élément de flux et l'estimation résultante du nombre d'éléments distincts si le hachage La fonction est:

(a) h (x)= 2x + 1 mod 32.

(b) h (x)= 3x + 7 mod 32.

(c) h (x)= 4x mod 32.

! Exercice 4.4.2 : Voyez-vous des problèmes avec le choix de hachage Fonctions dans l'exercice 4.4.1? Quel conseil pourriez-vous donner à quelqu'un qui allait utiliser une fonction de hachage de la forme H (x)= AX + B MOD 2K?

J'ai déjà résolu le premier exercice, trouver une longueur de queue maximale de 0 pour (a) et 4 pour (b) et (c), l'estimation résultante des éléments distincts est donc respectivement 1,16,16. (Il n'est pas demandé de faire des moyennes / des médianes des fonctions de hachage pour trouver une meilleure valeur)

Cependant, je ne peux pas sembler comprendre la réponse au deuxième exercice? Est-ce simplement pour choisir 'A' et 'B' d'une certaine manière? ou ces fonctions ne sont-elles pas bonnes pour générer des numéros de manière égale au hasard avec la traction 0 et sans traction 0?

Merci d'avance

Vous pouvez observer les résultats de chaque fonction de hachage en exécutant ce code: https://onlinegdb.com/rjxc4f4vl

Answer 1

Cependant, je ne peux pas sembler comprendre la réponse au deuxième exercice?Est-ce simplement pour choisir 'A' et 'B' d'une certaine manière?ou ces fonctions ne sont-elles pas bonnes pour générer des numéros de manière égale au hasard avec la traction 0 et sans traction 0?

Vous avez la bonne idée.Je crois que la question tente de suggérer, c'est que cette fonction hachage a un problème de certaines valeurs de $ A $ A $ et $B $ .Considérez, en particulier, A= 16 $ .Que va-t-il arriver à la fonction de hachage dans ce cas?Combien y a-t-il de valeurs possibles?

Alors, pour choisir une bonne valeur de $ A $ , nous devrions probablement vous assurer que $ a= 16 $ n'est pas autorisé. $ a= 8 $ n'est pas bon non plus.Que suggérez-vous est un bon choix pour $ a $ ?