另一种冲突解决策略是定义一个序列F(i)=ri,其中r0=0,且r1,r2, ... , rN是前N个整数的随机排列(每个整数恰好出现一次)
a.证明,在这种策略下,如果表不满,那么冲突总能够被解决。
b.能够期望这种策略会消除聚集吗?
c.如果表的装填因子是
,执行一个插入的期望时间是多少?
d.如果表的装填因子是
,执行一个成功查找的期望时间是多少?
e.给出一个有效算法(理论上以及实际上)生成随机序列。解释为什么选择P的那些法则是重要的?