logo标签列表

完美哈希函数

functiondata-structureshash
7
最近我得到了一个作业，要求给出一个键的列表，是否有可能制作出没有冲突的哈希函数。经过一些研究，我发现在给定一个预排序的键列表时，可以制作出完美的哈希函数。
然而，除此之外我并不清楚该如何解释。请问有人能够给我一些关于完美哈希函数是如何制作的建议，或者给定一个预定义的列表会对哈希函数创造者产生什么影响从而使其能够实现完美的函数？
感谢任何帮助。
2个回答
9

要避免碰撞的唯一方法是在键和哈希值之间建立一对一关系。哈希值的范围必须至少与键的数量一样大，并且映射函数必须将每个键转换为唯一值。更多信息请参见：http://en.wikipedia.org/wiki/Perfect_hash

0
在CLRS书中，第11.5节“完美哈希”中，我们发现如何在给定固定集合的n个输入键的情况下，构建一个没有冲突的哈希表。概述：

  • 如果我们能够承受表大小m = n * n，则基于该部分中引用的定理11.9，我们知道可以轻松地从哈希函数的通用类中找到一个哈希函数，它不会产生冲突。

  • 否则，对于任何具有多个键的插槽，都可以保留“二级哈希表”。这样的表本身可以基于定理11.9的思想构建，因为现在该插槽中的键数nj很小，因此nj * nj也很小。

引用的定理11.9： “如果我们使用从哈希函数的通用类中随机选择的哈希函数h，在大小为m = n * n的哈希表中存储n个键，则任何冲突发生的概率小于1/2。”
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接