所以我正在阅读关于哈希表，哈希函数等的内容 . 我很感兴趣在维基百科上阅读“动态完美哈希”如何使用第二个哈希表作为数据结构来存储特定桶中的多个值 .
然而，当我遇到如何选择通用散列函数来执行第二个散列表的散列时 . 任何人都可以解释这个通用哈希函数是如何根据存储在存储桶中的值确定的？我模糊地遵循维基百科的“通用哈希函数”页面中的推理和逻辑，但我正在努力对它有任何直觉 . 特别是，这些功能如何保证不发生冲突？或者至少，如果它们被处理掉并且如果检测到碰撞就会产生新的，那么我们怎么知道这可以在实际的时间内完成呢？
瓢虫书的解释好吗？
2 回答
完美散列意味着即使在最坏的情况下，读访问也需要恒定的时间 .
对于插入密钥，没有最坏情况保证，时间范围仅平均为真（或可能是摊销） .
为了使插入足够快，第二级哈希表被选择为非常大的密钥数量（k2），足够大以使冲突变得不太可能 . 这不是问题w.r.t. size，因为第一级哈希均匀地分配密钥，因此平均二级哈希表仍然很小 .
从一组参数化散列函数中随机选择第二级表的散列函数 .
看一些麻省理工学院的讲座怎么样？ :)
MIT’s Introduction to Algorithms, Lectures 7 and 8: Hashing