链式哈希命中查找运行时间数学证明

    《算法导论》中关于链式哈希命中查找运行时间数学证明，一上来就给出公式没看明白，在网上搜了一圈没找到解答心中疑问的文字，于是写下这篇。

    题目是计算在链式哈希表中，在均匀散列的情况下，命中查找的运行时间。

    分析：命中查找的运行时间，就是一个键数目n的函数，按照成本模型便是求命中查找的比较次数随n增长的增长率，即比较次数为n的函数T(n)。

    设要查找键a，a被散列到b链表中。命中查找的比较次数为b链表中排在a前面的元素个数+1.于是题目被转化为键a被插入到b链表后，后续插入的所有键被散列到b链表的个数+1。

设随机变量X表示键a被插入到b链表后，后续插入的所有键被散列到b链表的个数。

设随机变量Yi表示第i次插入键时，键被散列到b链表中的指示器随机变量。（指示器随机变量即当事件发生时为1，不发生时为0.这里表示第i次插入键时，键被散列到b链表中为1，散列到其他链表中为0）

设随机变量Zi表示第i次插入键时，选中a作为插入的键的指示器随机变量。

有

X = ∑<i从1到n>(Zi ∑<k从i+1到n>Yk)        ①

E[Zi] = 1/n                                             ②

E[Yi] = 1/m                                            ③

由上3式得

E[X] = ………… 此处省略20行 ………… = (n-1)/(2m)

题目所求期望即为1 + (n-1)/(2m) = 1 + α/2 – α/(2n)

T(n) = θ(1 + α)    

                                                                                                ■