数据结构问题选取哈希函数H(k)=(3k)MOD11,用开放定址法的伪随机处理冲突,di＝i（（7k）MOD10+1）(i=1,2,3,…).试在0～10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）构造哈希表,并求等概

Question

数据结构问题
选取哈希函数H(k)=(3k) MOD 11,用开放定址法的伪随机处理冲突,di＝i（（7k）MOD 10+1）(i=1,2,3,…).试在0～10的散列地址空间中对关键字序列（22,41,53,46,30,13,01,67）构造哈希表,并求等概率情况下查找成功时的平均查找长度?

Answer 1

构建哈希表0 1 2 3 4 5 6 7 8 9 1022 30 41 13 67 46 1 H(22)=0 填入 H(41)=2 填入 H(53)=5 填入 H(46)=6 填入--------------H(30)=2 此时发生冲突,用伪随机处理冲突. d1=1 填入--------------H(13)=6 发生冲突 d1 = 3 填入 --------------H(01)=3 冲突 d1 = 7 填入--------------H(67)=3 冲突d1 = 3 冲突 d2= 7 冲突 d3=d4=1 冲突 d5= 7冲突 d6=4 填入--------------22,41,53,46均找1次30,13,01均找2次67 找6次ssl = (1*4+2*3+6)/8