Question

NOIP一题选择题求讲解

2002年初中组19.设有一个含有13个元素的Hash表(0~12)，Hash函数是:H(key)=key%13,其中%是求余数运算。用线性探查法解决冲突，则对于序列(2,8,31,20,19,18,53,27)中,18应该放在第几号格中？
A、5
B、9
C、4
D、0
答案是B，求高手解释一下为什么。。。所谓“线性探查法”是什么意思？

Answer 1

线性探查法基本思想是：将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。

追问

问题就是。。。这个东西看不懂饿

追答

......那我也没办法了。。。