Hash求不成功查找<转>

哈希表查找不成功怎么计算？

解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！
例如：散列函数为hash(x)=x MOD 13，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？

     地址： 0   1   2   3   4   5   6   7   8   9   10   11   12

     数据： 39  12  28  15  42  44   6  25  －  －   36   －   38

  成功次数： 1   3   1   2   2   1   1   9           1        1

不成功次数： 9   8   7   6   5   4   3   2   1   1    2   1    10

查找成功时的平均查找长度:ASL=(1+3+1+2+2+1+1+9+1+1)/10 =2.2

查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54

说明：

第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。

至少要查询多少次才能确认没有这个值。

（1） 查询hash(x)=0,至少要查询9次遇到表值为空的时候，才能确认查询失败。

（2） 查询hash(x)=1,至少要查询8次遇到表值为空的时候，才能确认查询失败。

（3） 查询hash(x)=2,至少要查询7次遇到表值为空的时候，才能确认查询失败。

（4） 查询hash(x)=3,至少要查询6次遇到表值为空的时候，才能确认查询失败。

（5） 查询hash(x)=4,至少要查询5次遇到表值为空的时候，才能确认查询失败。

（6） 查询hash(x)=5,至少要查询4次遇到表值为空的时候，才能确认查询失败。

（7） 查询hash(x)=6,至少要查询3次遇到表值为空的时候，才能确认查询失败。

（8） 查询hash(x)=7,至少要查询2次遇到表值为空的时候，才能确认查询失败。

（9） 查询hash(x)=8,至少要查询1次遇到表值为空的时候，才能确认查询失败。

（10）查询hash(x)=9,至少要查询1次遇到表值为空的时候，才能确认查询失败。

（11）查询hash(x)=10,至少要查询2次遇到表值为空的时候，才能确认查询失败。

（12）查询hash(x)=11,至少要查询1次遇到表值为空的时候，才能确认查询失败。

（13）查询hash(x)=12,至少要查询10次遇到表值为空(循环查询顺序表)的时候，才能确认查询失败。

http://hi.baidu.com/liumingkong/blog/item/c6a9fc8c97352d04b21bba60.html

 

哈希表查找不成功的平均查找长度怎么计算？
解答：先建好表，然后可以算出每个位置不成功时的比较次数之和，再除以表空间个数！

例如：散列函数为hash(x)=x MOD 11，用线性探测，建立了哈希表之后，如何求查找不成功时的平均查找长度！？

地址：0 1 2 3 4 5 6 7 8 9 10
数据：33 1 13 12 34 38 27 22 － － －
成功次数：1 1 1 3 4 1 2 8
不成功次数：9 8 7 6 5 4 3 2 1 1 1

查找成功时的平均查找长度:ASL=(1+1+1+3+4+1+2+8)/8 =47/8
查找不成功时的平均查找长度:ASL=(9+8+7+6+5+4+3+2+1+1+1)/11

（注：求查找不成功时的平均查找长度，一般情况下分母为表长，但精确地讲是表长的有效位个数。

例如对于字符串来说，散列函数为hash(x)=x/2，x为字符的第一个字母在字母表的序号，表长即使为16，该分母也应取14，因为最大的hash(Z)=26/2=13,即只有0~13的14个有效位置有效。）

说明：

第n个位置不成功时的比较次数为，第n个位置到第1个没有数据位置的距离。

如：第0个位置到第1个没有数据位置（8）的距离为9.

 

看严蔚敏的课本第261面中间：“分析长度为M的哈西表中添装有N个纪录时查找不成功的平均查找长度这个问题，相当于在这个表中再添加第N+1个纪录时所需比较的次数的期望值。”
比如：当你MOD11时，第N+1个数MOD后的值可能是0~10。当它是0时就要放在第一个位置，如果第一个位置有纪录，就要处理冲突，向后移到一个空位置，记住移动的位置数，就是在0位置上查找不成功的值，然后分别分析在1~10位置上的值，最后相加除以11。（注意：不是除表长M）

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