Question

数据结构哈希表

Suppose that the size of a hash table is 11, and the hash function is H(key)=key%11. The following 4 elements have been inserted into the table as Addr(14)=3, Addr(38)=5, Addr(61)=6, Addr(86)=9. When open addressing with quadratic probing is used to solve collisions, the address of the element
with key=49 will be . (2 points) a. 4 b. 7 c. 8 d. 10

为什么答案是D 我算出来时A

Answer 1

10%11=10，10放在10号位置上24%11=2，24放在2号位置上32%11=10，32放在10号位置上，但是10位置上已经有数了，那么就出现哈希冲突了，题目说用线性探测再散列的方法处理冲突（32+1）%11=0，所以32放在0号位置上……最后排完就是32-X-24-44-X-X-17-X-30-31-10X表示该位置没有值现在计算查找长度10的查找长度为1，因为根据查找函数H(10)=10，我在位置10上正好找到了10，所以查找长度为1，32的查找长度为2，因为H(32)=10，但是10位置上并不是32，所以需要向后探测查找，探测一次发现了32，所以查找长度为2。……可得平局查找长度为（1+1+2+1+1+1+2）/7=1.29现在跟你解释一下“10的查找长度为1，因为根据查找函数H(10)=10，我在位置10上正好找到了10，所以查找长度为1”为什么我已经知道10了还要到哈希表中查找10因为哈希表通常存的是一对值，我们通过找到10去找跟他是一对的另一个值。

Answer 2

二次探测是每次key加i(i从1到size)的平方再去探测。
首先：
H(49) = 5，与之前的Addr(38)=5冲突，然后
H(49 +1×1)　＝　H（50）　＝　6，与Addr(61)=6冲突，然后
H(49 +2×2) = H（53）　＝　9，与Addr(86)=9冲突，然后
H(49 +3×3) = H（58）　＝　3，与Addr(14)=3冲突，然后
H(49 +4×4) = H（65）　＝　10，没有冲突。

追问

为什么都是正的不是还有负的么-1^2 -2^2

追答

这个只是函数选取的不同而已吧，主流默认还是加i的平方.
https://en.wikipedia.org/wiki/Quadratic_probing
人家给的公式还有H(k,i) = H(k) + i + i^2呢