动态完美散列和通用散列函数 - 解释吗？

Question

所以我阅读了关于哈希表，哈希函数等我很感兴趣，以在有关的“动态完美散列”如何涉及使用第二哈希表作为数据结构，以特定桶中存储多值维基读取。

从哪里获得然而输了，是当它涉及到一个通用散列函数是如何选择进行散列为第二哈希表。任何人都可以解释这种通用散列函数是如何确定其存储在桶中的值？我隐约按照维基百科的“通用散列函数”页面中的推理和逻辑，但我在努力有任何的直觉。特别是，如何做这些功能保证没有冲突？或者至少，如果他们处置和新生成的，如果检测到冲突，我们怎么知道这会在一段真实的量来完成，如果在所有？

瓢虫书解释好吗？

Answer 1

这读访问完美散列装置采用恒定的时间，即使在最坏的情况下。

有关插入键不存在的最坏情况的保证，时间界限仅在平均真实的（或也许摊销）。

若要插入足够快的第二级哈希表被选择用于键的数目（K ² ），足够大，使得碰撞变得足够不可能很大。这不是一个问题w.r.t.大小，因为第一级散列，使得平均第二级哈希表都还小均匀分布的密钥。

对于第二级表中的散列函数是随机选择的从一组参数化的散列函数。

Answer 2

如何看一些麻省理工学院的演讲？ :) 点击 MIT的算法导论，讲座7,8：散列