Go语言视频零基础入门到精通

zjuwzp

算法导论中的定理：
如果h选择一组全域散列函数，哈希表大小为m，并且用链接法解决冲突，则

如果关键字k不在哈希表中，则关键字k被散列到的链表的长度的期望至多为a。
如果k在表中，则关键字k所在的链表的长度的期望最多为1+a。

请教：这个定理怎么理解：关键字k不在哈希表中，则关键字k被散列到的链表？
          k竟然散列到列表中怎么还能不在哈希表中？

lagel

您好：你这个问题，你看看下面这个例子：

可以用如下方法构造一个全域散列函数类

选择一个足够大的质数p，使得每一个可能的关键字k都落在0到p-1之间。
设M表示集合{0,1,2,...,p-1}，N表示集合{1,2,...,p-1}。
构造哈希函数ha,b(k)=((a * k + b) mod p) mod m，其中a∈M，b∈N。
则Πa,b={ha,b：a∈M，b∈N}即为一个全域散列函数

参考链接：http://blog.csdn.net/goodluckwhh/article/details/11581015
http://www.junevimer.com/2014/06 ... universal%20hashing