Flajolet-Martin 알고리즘 : 특정 해시 기능 사용에 대한 질문

Question

이것은 스트리밍 알고리즘에 대한 PDF에 주어진 질문입니다 (이는 할당이지만 이해하려고하는 IM을 이해하려고합니다)

운동 4.4.1 : 우리 스트림이 정수 3, 1, 4, 1, 5, 9, 2, 6, 5. 우리의 해시 함수는 모두 양식 h (x)= AX + B MOD 32 일부 A 및 B 용. 결과를 5 비트로 취급해야합니다. 바이너리 정수. 각 스트림 요소에 대한 꼬리 길이를 결정하십시오 해시가있는 경우 별개의 요소 수의 결과 추정치 함수는 다음과 같습니다.

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

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

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

! 연습 4.4.2 : 해시 선택에 문제가 있습니까? 운동 4.4.1의 기능? 어떤 조언을 누군가에게 줄 수 있습니까? H (x)= ax + b mod 2k?

의 해시 함수를 사용하려고했습니다.

나는 (a) 및 (b) 및 (c)의 경우 (a) 및 4의 경우 (a) 및 4의 최대 r 테일 길이 0을 발견 한 첫 번째 운동을 이미 해결했다. 따라서 별개의 요소의 결과 추정은 각각 1,16,16이다. (Hash 함수의 평균 / 중간자를 더 나은 가치를 찾으려면 묻는 것은 아닙니다)

그러나 두 번째 exercice에 대한 답을 알아볼 수는 없습니다. 그것은 단순히 'a'와 'b'를 특정 방식으로 선택하는 것입니까? 또는이 함수는 트레일 링 0 및 트레일 링 0s없이 똑같이 무작위로 숫자를 생성하는 것이 좋지 않습니다.

미리 감사드립니다

이 코드를 실행하여 각 해시 함수의 결과를 관찰 할 수 있습니다. https://onlinegdb.com/rjxc4f4vlp.com/ a>

Answer 1

그러나 두 번째 exercice에 대한 답을 알아볼 수는 없습니다.그것은 단순히 'a'와 'b'를 특정 방식으로 선택하는 것입니까?또는이 함수는 트레일 링 0 및 트레일 링 0s없이 똑같이 무작위로 숫자를 생성하는 것이 좋지 않습니다.

당신은 올바른 생각을 가지고 있습니다.나는이 해시 함수가 $ a $ 및 $B $ .특히 $ a= 16 $ 을 고려하십시오.해시 기능에 어떤 일이 일어날 것입니까?얼마나 많은 값이 있습니까?

$ a $ 의 좋은 가치를 선택하려면 $ a= 16 $인지 확인해야합니다.은 허용되지 않습니다. $ a= 8 $ 도 좋지 않습니다. $ a $ 에 대한 좋은 선택은 무엇입니까?