关于哈希函数(hash function)全域哈希(universal hashing)如何查找的问题

fishenal
  • 3.4k

最近在coursera上学习数据结构,学到哈希表这块对于universal family这块的描述实在是理解不了。
ppt上相关内容如下:

Universal Family
Definition: Let U be the universe the set of all possible keys.
A set of hash functions ℋ = {h : U →{0,1,2,...,m−1}} is called a universal family
if for any two keys x,y ∈ U,x ̸= y the probability of collision
Pr[h(x) = h(y)] ≤ 1/m

我的理解是生成一个随机h函数集H,在运行hash function的时候,调用其中的随机h,这样可以保证任意两个key x和y相等的概率小于等于1/m,m为list长度,可以保证散列足够分散,这我能理解,但是这个函数是不确定的啊,那么如何在后续的Find方法中,根据查找的key得知我插入时的随机h函数呢?

其实课程中介绍了随机选取key的方法,而且明确说明这种方法是不确定的,无法作为hash function使用,而后面的课程中又介绍了这种通过universal family 全域哈希的方法,我实在想不明白在Find中是如何操作的?

我也找了一些中文资料,介绍的重点都在hash function本身,包括通过一个参数不断累加去寻找空位置的方法,但这个方法同样不知道这个位置叠加了几次,总不能在每次Find的时候再重新去算吧,这样消耗也太大了,Find的时候又怎么能通过key定义到hash table的位置呢?

回复
阅读 2.1k
撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏