完美的散列函数是否保证没有碰撞？

我一直在阅读和学习哈希和哈希表，并与一些代码一起训练（我对这个还是很新的，所以我可能会说我错过了一些错误的东西）。我对这个问题提出了完美的散列函数。只要我有，不知怎的，具有完美的哈希函数我自己的自定义类型：完美的散列函数是否保证没有碰撞？

class Foo 
{ 
    private int data; 

    override int GetHashCode() 
    { 
     return data.GetHashCode(); 
    } 
}

的一个int哈希码是int本身，所以我有一个完美的哈希函数，对不对？但是，当我们使用散列函数由简单的公式对象以一个哈希表映射：

index = foo.GetHashCode() % hashtable.Length

，我们得到的是取决于我们也多少元素在哈希表中的变量指标。如果散列表的大小是int.MaxValue，那么我们将有一个完美的散列函数。例如，假设我们有一个大小为2的哈希表。如果我们散列例如数字1和3我们得到

1 % 2 = 1 
3 % 2 = 1

碰撞！我了解哈希和哈希表有什么问题吗？它表明完美的散列函数并不完美。

来源

2013-05-11 Bosak

如果你可以写一个完美的散列函数，我想有一百万美元在等着你。 – ChiefTwoPencils 2013-05-11 20:41:23

@ C.Lang一个完美的散列函数在限制可散列数据集时很容易编写。 – 2013-05-11 20:54:03

@SethCarnegie：谢谢。我通过非限制性的实现了解到。根据他在朱利安的回答中的评论，这是OP所指的。无论如何，只是另一件事缠绕我的头：）\ – ChiefTwoPencils 2013-05-11 21:15:35

是的，一个完美的散列函数可以保证不会发生冲突。

这就是它的定义！

维基百科（http://en.wikipedia.org/wiki/Perfect_hash_function）

用于一组S A完美散列函数是散列函数映射S中不同元件的一组整数，没有碰撞。一个完美的哈希函数有很多相同的应用程序中的其他散列函数，但没有冲突解决必须实施

来源

2013-05-11 20:44:40

是的，但它实际上有碰撞见我做的例子。这是一个给出一对一关系的函数。问题不在散列函数中，而是以计算索引的方式（'i = hash（obj）％length'） – Bosak 2013-05-11 20:48:08

然后你做的例子不是一个完美的散列函数。然而，你的问题的答案是“一个完美的哈希函数保证没有碰撞？”必须是“是”，因为正如我所指出的那样，这是完美散列函数的定义。 – 2013-05-11 22:34:40

优势你拥有一切权利，直到这一点

index = foo.GetHashCode() % hashtable.Length

你的哈希函数是完美的，但是当你计算模数时，你实际上使用了不同的散列函数。在这种情况下，你的散列函数int.GetHashCode是的完美，但是你的数据结构使用的是foo.GetHashCode() % hashtable.Length不是。也就是说，有一件事是你的对象的哈希值，而另一件事是持有这些对象的结构使用的哈希值。

为了让您的数据结构更完美，它的最大尺寸也必须是整数。我们为什么不碰撞Dictionary？其实，我们做到了。如果两个对象A和B在字典中具有相同的散列，我们就会发生冲突。会发生什么是该字典运行A.Equals(B)作为最终检查，看看这两个对象实际上是否相同。如果他们是，你会得到重复的例外。如果他们不这样做，他们都被保存在相同的字典哈希中。

来源

2013-05-11 20:48:47

是的，我想了解它，但不是如何实施哈希表？例如在C＃中的字典。而不是一个长度为int.MaxValue的数组太大而不能有效，并且大量内存将被浪费？ – Bosak 2013-05-11 20:52:14

是的，但字典确实有碰撞。会发生的是，无论何时发生碰撞，字典都会检查两个碰撞对象的“Equals”方法。那一个是最后的检查 – 2013-05-11 20:53:56

是的，我知道他们有碰撞，我知道有很多碰撞求解算法存在，但事实并非如此。所以你知道一个完美的散列函数是否可以存在（使用模数），以便它适用于任何大小的数组。 – Bosak 2013-05-11 20:59:56

是的！（如所述，根据定义）
从哪里获得p.h.f从一开始？你想散列一个固定，即常数将S的不同（即无多集）值设为集合1 .. | S |，双射。显然那时，p.h.f取决于集合S
此外，删除从S上单个元素，并添加一个又一个，你几乎肯定会得到一个碰撞（新元素的与旧的）。
所以，你实际上想要“为这样一个明确定义/描述的集合设置p.h.f.”。然后我们可以尝试找到一个。

来源

2013-12-07 14:33:53 Michael

完美的散列函数是否保证没有碰撞？

回答

相关问题