《算法导论》中关于链式哈希命中查找运行时间数学证明，一上来就给出公式没看明白，在网上搜了一圈没找到解答心中疑问的文字，于是写下这篇。
题目是计算在链式哈希表中，在均匀散列的情况下，命中查找的运行时间。
分析：命中查找的运行时间，就是一个键数目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 + α)
■
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
