散列＆期望

hash

2011-12-12 88 views 0 likes

散列函数H：{0,1}^30000→{0,1}^20散列＆期望

如果h的前4位（M）都是零消息m进行采样。假设N是检测器散列的消息的数量，并且令Y是检测器采样的消息的数量。 N应该多大以确保E [Y] = 20000？

任何帮助？谢谢

来源

2011-12-12 NuNu

作业，有什么机会？ –

它取决于哈希函数。 –

回答

这完全取决于您使用的散列函数。举例来说，这里是一个（非常糟糕）哈希函数

h(m) = 11111111111111111111

因为一切都被映射到那些串，E[Y]为零，无论有多少信息是如何处理的。是。所以为了保证20000的期望值，你需要一些散列函数的标准。

来源

2011-12-12 23:18:42

说h（m）= 00001111111111111111 然后会发生什么？ – NuNu

然后'E [Y]'='N'无论如何（因为所有的消息都将被采样）。但是，假设在'h（m）'的前4位中，字符串'0000'与'0001'和'0002'以及所有其他字符（总共16种可能性）一样可能出现。然后我们得到E [Y] = N/16'。这里要讲的是每个哈希函数服从一个特定的统计分布，每个分布都有自己的一组统计特性，包括期望值。 –

散列＆期望

回答

相关问题