http://imgur.com/a/rsJdm
想问(31)~(33)
不太懂这题的Under the uniform hashing assumption是什么意思
是指用Linear Probing的方式解决conflict吗？
(31)我的想法是：
因为第3个key需要探测3次，表示前两个key必须连续排，然后第3个key在命中连续key的
最上方的key
所以
1 key:随意摆在m个格子的其中一格
2 key:两种可能(1)命中跟1key一样的格子1/m(2)命中1key的上一个or下一个2/m-1
3 key:命中前述的头一个key格子1/m
这样的话是(1/m+2/m-1)*1/m 但没有这个答案
所以我在想是hashing assumption有特别的什么假设吗？
交大给的答案 C B B

32题背后的推导应该是蛮复杂的，洪逸资料结构上面也只给了公式没有证明，我节录一下他的叙述搜寻一个不在表中之识别字的平均比较次数，对于Rehashing、Random probing、Quadratic Probing为1/(1-a)，a为Loading density，在这题里面就是n/m也许背后的想法就如T大所说的也有可能，只是书上没给证明，有背到这题就会，没背到也许就要用T大的想法了

不一定是linear probing , 也可能是quadratic probing32题，在Uniform hashing假设下，Expected hashing ofprobs 的cost等于是找到空位的cost, 因为有n/m被占满了所以空位比例是1/(1-n/m) // 我是这样想啦33题，因为chaing遇到collision 还是会放到同一格，只是会用link list连接，所以k1乱放还是可以放到任一bucket里，这是k2也来了刚好跟k1放在一起的机率就是1/m

题目没有说要用linear probing，所以也许是想复杂了前面两个摆好之后，第三个key要进来，只要第一次probin中了其中一个(机率为2/m)，就要下一次probing再中了剩下m-1个中的1个就要再一次，机率为1/(m-1)两个乘起来应该就是答案