动态完美哈希和通用哈希函数 - 请解释一下?

5

我正在学习哈希表、哈希函数等相关知识。在维基百科上,我看到了“动态完美哈希”是如何使用第二个哈希表作为数据结构来存储特定桶中的多个值。

然而,我迷失的地方是如何选择通用哈希函数来执行第二个哈希表的哈希。有人能解释一下如何从存储在桶中的值中确定这个通用哈希函数吗?我大致理解了维基百科“通用哈希函数”页面中的推理和逻辑,但对此没有任何直觉。特别是,这些函数如何保证不会发生冲突?或者至少,如果检测到冲突并且将其丢弃并生成一个新的哈希函数,我们如何知道是否可以在现实时间内完成这个过程?

请用通俗易懂的语言解释一下?

2个回答

4
完美哈希意味着即使在最坏的情况下,读取访问也只需常数时间。对于插入键而言,没有最坏情况的保证,时间上限仅在平均情况下(或者说或许是分摊的)。为了使插入足够快,第二级哈希表被选择得非常大以适应键的数量(k2),足够大以至于碰撞变得足够不可能。这并不是大小方面的问题,因为第一级哈希均匀地分布键,以至于平均而言第二级哈希表仍然很小。第二级表的哈希函数是从一组参数化哈希函数中随机选择的。

谢谢 - 知道插入性能没有 "保证" 已经有所帮助。你最后一句话涉及到我想了解的内容 - 参数化哈希函数的自动/随机选择过程 - 你知道一个例子/能解释一下维基百科上的吗? - Ray

3

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接