Question

关于数据结构的哈希表平均查找长度的疑问

设散列表的长度是8，散列函数H(k)=k%7,初始关键字序列为(23,31,8,27,13,68),求链地址法解决冲突的平均查找长度。(为什么我算的是6/7,答案是3/4)
我算的是7/6

Answer 1

23 % 7 = 1, 31 % 7 = 3, 8 % 7 = 1, 27 % 7 = 6, 13 % 7 = 6, 68 % 7 = 5
这样1 的链表中有2个结点，6 的链表中也有两个结点，因此查找成功探查次数对于一个链表中的两个结点来说，一定是表头的结点探查1次，后面表尾的结点探查2次

所以查找成功的平均查找长度是(2 * (1 + 2) + 1 + 1) / 6 = 8 / 6 = 4 / 3