动态完美散列和通用散列函数 - 请解释一下？

Question

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

然而,当我遇到如何选择通用散列函数来执行第二个散列表的散列时.任何人都可以解释这个通用哈希函数是如何根据存储在存储桶中的值确定的？我模糊地遵循维基百科的"通用哈希函数"页面中的推理和逻辑,但我很难对它有任何直觉.特别是,这些功能如何保证不发生冲突？或者至少,如果它们被处理掉并且如果检测到碰撞就会产生新的一个,我们怎么知道这可以在实际的时间内完成呢？

瓢虫书的解释好吗？

Answer 1

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

对于插入密钥，没有最坏情况的保证，时间限制仅在平均情况下（或者可能是摊销的）为真。

为了使插入足够快，第二级哈希表被选择为非常大的键数（k ²），大到足以使得冲突变得足够不可能。这对于大小来说不是问题，因为第一级哈希均匀地分布键，因此平均而言第二级哈希表仍然很小。

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