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

Question

所以我正在阅读有关哈希表、哈希函数等的内容。我很感兴趣地在维基百科上阅读有关“动态完美哈希”如何涉及使用第二个哈希表作为数据结构来在特定存储桶中存储多个值的信息。

然而，我迷失的地方是如何选择通用哈希函数来对第二个哈希表执行哈希处理。谁能解释一下这个通用哈希函数是如何根据存储在桶中的值确定的？我隐约遵循维基百科“通用哈希函数”页面中的推理和逻辑，但很难对它有任何直觉。特别是，这些功能如何保证不发生冲突？或者至少，如果它们被处理掉，并且在检测到冲突时生成一个新的，我们如何知道这可以在实际的时间内完成(如果有的话)？

瓢虫书的解释好吗？

Answer 1

完美的哈希意味着即使在最坏的情况下，读取访问也需要恒定的时间。

对于插入 key ，没有最坏情况的保证，时间限制仅在平均情况下(或可能摊销)为真。

为了使插入足够快，第二级哈希表选择的键数非常大(k²)，足够大，以至于不太可能发生冲突。这不是问题。大小，因为第一级哈希均匀分布键，因此平均第二级哈希表仍然很小。

二级表的哈希函数是从一组参数化哈希函数中随机选择的。