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

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

公司主营业务：网站制作、网站设计、移动网站开发等业务。帮助企业客户真正实现互联网宣传，提高企业的竞争能力。创新互联是一支青春激扬、勤奋敬业、活力青春激扬、勤奋敬业、活力澎湃、和谐高效的团队。公司秉承以“开放、自由、严谨、自律”为核心的企业文化，感谢他们对我们的高要求，感谢他们从不同领域给我们带来的挑战，让我们激情的团队有机会用头脑与智慧不断的给客户带来惊喜。创新互联推出八步免费做网站回馈大家。

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

    分析：命中查找的运行时间，就是一个键数目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 = ∑(Zi ∑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 + α)    

                                                                                                ■