FLAJOLET-MARTIN算法：关于某些散列函数的问题

Question

这是一个关于流算法的PDF中给出的问题（这不是一个分配，但我试图理解）

练习4.4.1 ：假设我们的流由整数3,1，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的表格h（x）= b mod 2k的哈希函数？

我已经解决了第一练习，找到了（a）和4（b）和（c）4的最大值r尾长长度，因此产生的不同元素的估计分别为1,16,16。 （没有被要求做哈希函数的平均值/中位数来找到更好的价值）

但是，我似乎无法想到第二次锻炼的答案？它只是以某种方式选择“A”和'B'吗？或者这些功能不好地生成具有尾随0的同样随机的数字，没有尾随0s？

提前谢谢

您可以通过运行此代码来观察每个哈希函数的结果： https://onlinegdb.com/rjxc4f4vl

Answer 1

但是，我似乎无法想到第二次锻炼的答案？它只是以某种方式选择“A”和'B'吗？或者这些功能不好地生成具有尾随0的同样随机的数字，没有尾随0s？

你有正确的想法。我相信问题所努力的推荐是，这个哈希函数具有某些值 $ a $ 和 $B $ 。特别考虑 $ a= 16 $ 。在这种情况下哈希函数会发生什么？有多少可能的值？

所以，要选择一个良好的 $ a $ ，我们应该确保 $ a= 16 $不允许。 $ a= 8 $ 也不好。您建议的是 $ a $ ？