FLAJOLET-MARTINアルゴリズム：特定のハッシュ関数の使用に関する質問

Question

これはストリーミングアルゴリズムに関するPDFでの質問です（これは割り当てはありますが、理解しようとしているIM）

演習4.4.1 ：私達の流れが整数3,1,4で構成されているとします。 1,5,9,2,6,5。私達のハッシュ関数はすべてh（x）=の形式であるでしょう。 AX + B MOD 32 AND 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）のための最大Rテール長さ0を見つけたので、その結果として生じる異なる要素の推定はそれぞれ1,16,16です。 （より良い価値を見つけるためにハッシュ関数の平均/中央値をするように頼まれていません）

しかし、私は第二の演習に対する答えを理解するようには思われませんか？特定の方法で「a」と 'b'を選択するだけですか？または、これらの関数は、末尾の0Sと末尾の0Sを持つ同様にランダムな数値を生成するのに良くないですか？

事前にありがとう

このコードを実行することで、各ハッシュ関数の結果を観察することができます。 https://onlinegdb.com/rjxc4f4vl

Answer 1

しかし、私は第二の演習に対する答えを理解するようには思われませんか？特定の方法で「a」と 'b'を選択するだけですか？または、これらの関数は、末尾の0Sと末尾の0Sを持つ同様にランダムな数値を生成するのに良くないですか？

あなたは正しいアイデアを持っています。この質問がしようとしているのは、このハッシュ関数には $ a $ 、 $の特定の値に問題があることです。B $ 。特に $ A= 16 $ を考慮してください。その場合のハッシュ関数は何が起こりますか？可能な値はいくつありますか？

SO、 $ A $ の良い値を選ぶには、おそらく $ a= 16 $であることを確認する必要があります。は許可されていません。 $ a= 8 $ どちらでもありません。 $ a $ のための良い選択は何ですか？