首页 > 试题广场 >

考虑一个特殊的hash函数h，能将任一字符串hash成一个整

[单选题]

考虑一个特殊的hash函数h，能将任一字符串hash成一个整数k，其中概率P(k)=2^(-k)，k=1,2,…∞。对一个未知大小的字符串集合S中的每一个元素取hash值所组成的集合为h(S)。若h(S)中最大的元素max h (S) = 10，那么S的大小的期望是_______。

```
1024
```
```
512
```
```
5
```
```
10
```

查看答案及解析

BlingBing

个人感觉下面这个解释比较容易理解一点==

http://blog.sina.com.cn/s/blog_ab4216e20101j8dg.html

发表于 2017-06-15 23:01:30 回复(0)

曹少平

设字符集合S的大小为x，

x=1时，概率为2^-10;
x=2时，概率为(2^-1+2^-2+...+2^-10)2^-10;
当x=n时，概率为(2^-1+2^-2+...+2^-10)^(n-1)*2^-10;

E(x) = sum (2^-1+2^-2+...+2^-10)^(n-1)2^-10n，其中n从1取到无穷，编写python代码计算：

a = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
num = 0
for i in a:
    num += 2**(-i)
res = 0
for i in range(1000000):
    res += num**(i - 1) * 2**(-10) * i;
print(res)

最终计算结果为1024，也可以算出解析解。

编辑于 2017-04-21 11:36:26 回复(2)

ThyBoox

近似理解：

既然s中的任意一个字符串都能以概率2^(-k)映射成k,那么每个字符映射成10的概率相等为2^（-10），现在既然10出现了，就用最大似然估计的思想，设10出现的概率为1，假设s有n个字符串，则n*2^(-10)=1,求出n=1024。

发表于 2015-09-08 14:56:40 回复(0)

fr_daily

x表示字符串的长度，则

P(x=1) = 2^(-10)

P(x=2) = (2^(-1) + 2^(-2) +...+2^(-10))*2^(-10) //1~10中的每个整数都有可能是字符的映射值

P(x=3) = (2^(-1) + 2^(-2) +...+2^(-10))^(2)*2^(-10)

P(x=n) = (2^(-1) + 2^(-2) +...+2^(-10))^(n-1)*2^(-10) //一共n-1个字符

可以看作n次伯努利实验中，在第k次第一次成功的概率，即为几何分布。

其中p=2^(-10)

q=2^(-1)+2^(-2)+...+2^(-10) = 1-2^(-10)

p+q = 1

几何分布的期望值为1/p = 1024;

发表于 2017-08-30 16:14:12 回复(1)

lhbug1

答案为A：由于s的最大长度为10，可以看成是当前s包含10与不包含10，p=1/2^10。此时类似与伯努利分布。当s长度为1时候概率为：p，s=2时(1-p)p，s=3概率为(1-p)^2p……。最后的E(s)=p+2p(1-p)+……+np(1-p)^(n-2)，答案就是伯努利的期望公式E(s)=1/p;

发表于 2015-09-05 12:59:39 回复(3)