动态完美哈希和通用哈希函数 - 请解释一下？
因此，我正在阅读有关哈希表、哈希函数等的内容。我很感兴趣地在维基百科上阅读有关“动态完美哈希”如何涉及使用第二个哈希表作为数据结构来在特定存储桶中存储多个值的信息。
然而，我迷失的地方是当涉及到如何选择通用哈希函数来对第二个哈希表执行哈希时。 谁能解释一下这个通用哈希函数是如何根据存储在桶中的值确定的？ 我隐约遵循维基百科“通用哈希函数”页面中的推理和逻辑，但很难对它有任何直觉。 特别是，这些函数如何保证不发生冲突？ 或者至少，如果它们被处理掉，并且在检测到冲突时生成新的，我们怎么知道这可以在实际的时间内完成（如果有的话）？
请问瓢虫书有解释吗？
So I'm reading up about hash tables, hash functions etc. I was intrigued to read on wikipedia about how "dynamic perfect hashing" involves using a second hash table as the data structure to store multiple values within a particular bucket.
Where I get lost however, is when it comes to how a universal hash function is selected to perform the hashing for that second hash table. Can anyone explain how this universal hash function is determined from the values being stored in the bucket? I vaguely following the reasoning and logic in wikipedia's "universal hash function" page, but am struggling to have any intuition on it. In particular, how do these functions guarantee no clashes? Or atleast, if they're disposed of and a new one generated if a clash is detected, how do we know this can be done in a realistic amount of time if at all?
Ladybird book explanation please?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
完美散列意味着即使在最坏的情况下，读取访问也需要恒定的时间。
对于插入密钥，没有最坏情况的保证，时间限制仅在平均情况下（或者可能是摊销的）为真。
为了使插入足够快，第二级哈希表被选择为非常大的键数量（k2），足够大以便碰撞变得足够不可能。 这对于大小来说不是问题，因为第一级哈希均匀地分布键，因此平均而言第二级哈希表仍然很小。
第二级表的哈希函数是从一组参数化哈希函数中随机选择的。
Perfect hashing means that read access takes constant time even in the worst case.
For inserting keys there are no worst-case guarantees, the time bounds are only true on average (or maybe amortized).
To make insertion fast enough the second level hash table is chosen very large for the number of keys (k2), large enough so that collisions become sufficiently unlikely. This is not a problem w.r.t. size because the first level hash distributes keys evenly so that on average second level hash tables are still small.
The hash function for the second level tables are chosen at random from a set of parameterized hash functions.
观看一些麻省理工学院的讲座怎么样？ :)
麻省理工学院的算法简介，讲座 7 和 8：哈希
How about watching some MIT lectures? :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing