很简单的构造哈希表,计算查找长度的问题(数据结构版没人会,我很着急只好发在这里试试)
设有一组关键字{9,01,23,14,55,20,84,27},采用哈希函数:H(key)=key mod 7 ,表长为10,用开放地址法的二次探测再散列方法Hi=(H(key)+di)mod10(di=1*1,2*2,3*3….)解决冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度
我算出来的答案是
地址 0 1 2 3 4 5 6 7 8 9
值 14 01 9 23 84 27 55 20
比较次数 1 1 1 2 3 4 1 2
平均查找长度: (1+1+1+2+3+4+1+2)/8=15/8=1.875
具体过程如下:
9mod7=2
1mod7=1
23mod7=2 与9位置冲突, (23mod7+1)mod10=3
14mod7=0
55mod7=6
20mod7=6 与55位置冲突, (20mod7+1)mod10=7
84mod7=0 与14位置冲突,(84mod7+1)mod10=1 与1位置冲突,
(84mod7+2*2)mod10=4
27mod7=6 与55位置冲突,(27mod7+1)mod10=7 与20位置冲突,
(27mod7+2*2)mod10=0 与14位置冲突,
(27mod7+3*3)mod10=5
我的答案跟标准答案对不上,我又实在没发现我计算过程哪里错了,大家能帮着看看吗,发现我哪里错了请给我指一下,不胜感激!
标准答案给的是:
地址 0 1 2 3 4 5 6 7 8 9
值 55 1 9 20 84 23 14 27
次数 4 1 1 2 2 1 2 4
我怎么也得不出来,是不是答案有问题啊
[解决办法]
要怀疑答案
[解决办法]
我编了个小程序试了下,发现你真的比较靠谱。
原来以为不同排列次序,结果不同。
再仔细一看标准答案:
9==1
23==1
最起码这两个很不靠谱嘛。