哈希表公共溢出区线性探测再散列查找不成功的ASL怎么求

Question

就这个不成功的ASL怎么算的

Answer 1

ASL查找失败次数是由地址到空位置的比较次数。
5个1的原因:哈希表5个空位置，各比较一次
5个5的原因:哈希表中已经有关联字的位置比较1次，公共溢出区比较3＋1次。

最后除以总的地址数

Answer 2

查找不成功的ASL :定义为查找不成功时对关键字需要执行的平均比较次数。 故对拉链法来说，第一次探测到空的位置，该次查找失败长度是0。 如ASLunsucc =(1+0+2+1+0+1+1+0+0+0+1+0+3)/13≈10/13≈0.77追问

哥们这是公共溢出区啊，怎么就拉链了

Answer 3

要从表头重新查起，因为在构建表的时候就已经预留了空间，一般是表的75%可以用来存放数据，所以数据时可以完全存进去的，如果不要求二次散列那么就要从头查起！本回答被提问者采纳

Answer 4

北邮的嘛哈哈哈
重点应该是那个"5"没理解吧，"1"就不说了。
5=1（原表中对应位置的一次比较）+3（溢出区的已有3个数比较）+1（溢出区的第四个位置为空的比较，发现查找失败）