完美的哈希函数
最近我收到了一份作业，询问给定一个键列表是否可以创建一个没有任何冲突的哈希函数。经过一些研究，我发现给定一个预先排序的键列表，完美的哈希函数是可能的。
然而，我不太确定除此之外该说些什么。谁能给我一些关于如何制作完美哈希函数的建议，或者给出预定义列表对于允许完美函数的哈希函数创建者到底有什么作用？
感谢您的任何帮助。
I was recently given a homework that asked whether given a list of keys it would be possible to make a hash function that doesnt have any collisions. Doing some research, I found out that given a preordered list of keys, perfect hash functions are possible.
However, I'm not quite sure what to say beyond that. Could anyone give me some advice on how perfect hash functions are made, or what exactly giving a predefined list does to a hash function creator that allows for a perfect function?
Thanks for any help.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
避免冲突的唯一方法是密钥和哈希值之间具有一对一的关系。哈希值的范围必须至少与键的数量一样大，并且映射函数必须将每个键转换为唯一的值。更多信息请参见：http://en.wikipedia.org/wiki/Perfect_hash
The only way to have no collisions is to have a 1-to-1 relationship between the key and the hash value. The range of hash values must be at least as large as the number of keys, and the mapping function must transform each key to a unique value. Much more info here: http://en.wikipedia.org/wiki/Perfect_hash
在 CLRS 书籍第 11.5 节“完美哈希”中，我们发现如何给定一组固定的
n输入键，我们可以构建一个没有冲突的哈希表。概要：如果我们能够承受表大小
m = n*n，那么根据该节中的定理 11.9（下面引用），我们知道我们可以轻松地从哈希函数的通用类，不会产生冲突。否则，可以为任何具有超过 1 个键的槽保留“辅助哈希表”。这样的表本身可以基于定理11.9的思想来构建，因为现在该槽中的键
nj的数量很小，因此将是nj*nj.引述定理 11.9：
“如果我们使用从通用类中随机选择的哈希函数
h将n个键存储在大小为m=n*n的哈希表中哈希函数，那么发生冲突的概率小于 1/2。”In CLRS book, section 11.5 "Perfect hashing", we find how given a fixed set of
ninput keys, we can build a hash-table with no collision. Outline:if we can afford table size
m = n*n, then based on Theorem 11.9 (quoted below) in that section, we know that we can easily find a hash-function from a universal-class of hash-functions, which gives no collision.otherwise, "secondary hash tables" can be kept for any slot with more than 1 key. Such table itself can be built based on the idea of Theorem 11.9, because now the number of keys
nj, in that slot, are small, and so will benj*nj.Theorem 11.9, quoted:
"If we store
nkeys in a hash table of sizem=n*nusing a hash functionhrandomly chosen from a universal class of hash functions, then the probability of there being any collisions is less than 1/2."