Question

数据结构问题，求高手。

设H(x)是一哈希函数，有K个不同的关键字（x1,x2,x3,.....xk）满足H(x1)=H(x2)=...H(xk),若用线性探测法将这K个关键字存入哈希表中，至少要探测多少次？求答案和详细过程。

Answer 1

x1探测1次找到自己的位置
x2探测1次，与x1冲突，再探测1次
x3探测1次，与x2冲突，再探测1次，与x1冲突，再探测1次

依次类推
所以总的次数是1+2+。。。+k=(k+1)*k/2

追问

我查了正确答案应该是k(k-1)/2啊。。。。

追答

额。。那应当是每个元素第一次求hash值不算探测。。。那样就得总数减k。。。就是你的答案了。。。

追问

总是减k是指什么？求详细运算过程。。。

追答

嗯，重新写一次哈~
x1计算hash值，找到自己的位置
x2计算hash值，与x1冲突，向后再探测1次，共1次
x3计算hash值，与x2冲突，向后再探测1次，向后与x1冲突，再探测1次，共2次
。。。
xk计算hash值，与xk-1冲突，向后再探测1次。。。向后与x1冲突，再探测1次，共k-1次
一共1+...+k-1=(1+k-1)*(k-1)/2=(k-1)k/2