Flajolet-Martin Algoritmo: Domanda sull'uso di alcune funzioni hash

Question

Questa è una domanda fornita in un PDF sugli algoritmi in streaming (questo non è un incarico ma sto cercando di capire)

.

Esercizio 4.4.1 : Supponiamo che il nostro flusso sia costituito da numeri interi 3, 1, 4, 1, 5, 9, 2, 6, 5. Le nostre funzioni hash saranno tutte del modulo h (x)= AX + B MOD 32 per alcuni A e B. Dovresti trattare il risultato come un 5 bit Integer binario. Determina la lunghezza della coda per ciascun elemento del flusso e la stima risultante del numero di elementi distinti se l'hash La funzione è:

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

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

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

! Esercizio 4.4.2 : vedi problemi con la scelta di hash Funzioni in esercizio 4.4.1? Che consiglio potresti dare a qualcuno che stava per usare una funzione hash del modulo h (x)= ax + b mod 2k?

Ho già risolto il primo esercizio, trovando una lunghezza massima della coda r da 0 per (a) e 4 per (b) e (c), quindi la massima stima degli elementi distinti è rispettivamente di 1.16,16. (Non è stato chiesto di fare medie / mediane delle funzioni di hash per trovare un valore migliore)

Tuttavia, non riesco a capire la risposta al secondo esercizio? È semplicemente scegliere "A" e "B" in un certo modo? O queste funzioni non sono buone per generare numeri ugualmente casuali con finali 0s e senza trascinamento 0s?

Grazie in anticipo

È possibile osservare i risultati di ciascuna funzioni hash eseguendo questo codice: https://onlinegdb.com/rjxc4f4vl

Answer 1

.

Tuttavia, non riesco a capire la risposta al secondo esercizio?È semplicemente scegliere "A" e "B" in un certo modo?O queste funzioni non sono buone per generare numeri ugualmente casuali con finali 0s e senza trascinamento 0s?

Hai l'idea giusta.Credo che la domanda stia cercando di suggerire è che questa funzione hash ha un problema con alcuni valori di $ a $ e $B $ .Considera, in particolare, $ a= 16 $ .Cosa succederà alla funzione hash in tal caso?Quanti valori possibili ci sono?

Quindi, scegliere un buon valore di $ A $ , dovremmo probabilmente assicurarci che $ a= 16 $ non è permesso. $ A= 8 $ non è neanche buone.Cosa suggerisci è una buona scelta per $ a $ ?