Flajolet-Martin Algoritmo: Pergunta sobre o uso de certas funções de hash

Question

Esta é uma pergunta dada em um PDF sobre algoritmos de streaming (isso não é uma tarefa, mas estou tentando entender)

.

Exercício 4.4.1 : Suponha que nosso fluxo consista aos inteiros 3, 1, 4, 1, 5, 9, 2, 6, 5. Nossas funções hash serão todas a forma H (x)= AX + B Mod 32 para alguns A e b. Você deve tratar o resultado como um 5 bits inteiro binário. Determinar o comprimento da cauda para cada elemento de fluxo e a estimativa resultante do número de elementos distintos se o hash Função é:

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

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

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

! Exercício 4.4.2 : Você vê algum problema com a escolha do hash Funções no Exercício 4.4.1? Que conselho você poderia dar a alguém que ia usar uma função hash do formulário H (x)= AX + B MOD 2K?

Eu já resolvi o primeiro exercício, encontrando um comprimento de cauda máximo de 0 para (a) e 4 para (b) e (c), portanto, a estimativa resultante de elementos distintos é respectivamente 1.16,16. (Não é solicitado a fazer médias / medianas das funções de hash para encontrar um valor melhor)

No entanto, não consigo descobrir a resposta para o segundo exercício? É simplesmente escolher 'A' e 'B' de uma certa maneira? ou são essas funções não são boas para gerar números igualmente aleatórios com 0s e sem arrastar 0s?

Obrigado antecipadamente

Você pode observar os resultados de cada funções de hash executando este código: https://onlinegdb.com/rjxc4f4vl

Answer 1

.

No entanto, não consigo descobrir a resposta para o segundo exercício?É simplesmente escolher 'A' e 'B' de uma certa maneira?ou são essas funções não são boas para gerar números igualmente aleatórios com 0s e sem arrastar 0s?

Você tem a ideia certa.Acredito que a pergunta está tentando sugerir é que essa função de hash tem um problema com certos valores de $ a $ e $B $ .Considere, em particular, $ a= 16 $ .O que acontecerá com a função HASH nesse caso?Quantos valores possíveis existem?

Então, para escolher um bom valor da $ a $ , provavelmente deveríamos certificar-se de que $ a= 16 $ não é permitido. $ a= 8 $ não é bom também.O que você sugere é uma boa escolha para $ a $ ?