Question

数据结构填空题：有n个关键字,它们具有相同的Hash函数值,用线性探测的方法解决冲突

Answer 1

n(n - 1) / 2

线性探测解决冲突的办法指一旦目标空间被占有,则探测相邻的下一个空间,如果空闲则插入,否则继续向下一个探测,如果到了队列末尾则返回队列头探测,一旦全部空间都被占据则无法插入.

设那么第i个元素探测和插入的次数是T(i),则可知：

T(i) = T(i - 1) + 1,而且T(1) = 1则T(n) = n

所以总次数为n(n - 1) / 2