c# - 完美的散列函数能保证不发生碰撞吗？

Question

我一直在阅读和学习哈希和哈希表，并尝试了一些代码(我对此还是很陌生，所以我可能会说一些我误解了的错误)。我遇到了完美哈希函数的问题。前提是我有自己的自定义类型，它以某种方式具有完美的哈希函数:

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

碰撞!我对散列和散列表有什么误解吗？事实证明，完美的哈希函数并不完美。

Answer 1

在这之前你一切都好

index = foo.GetHashCode() % hashtable.Length

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

为了使您的数据结构也完美，其最大大小也必须是整数的数量。

那么为什么我们在 Dictionary 中没有冲突？实际上，我们有。如果两个对象 A 和 B 在字典中确实有相同的散列，我们就会发生冲突。发生的情况是字典运行 A.Equals(B) 作为最终检查，以查看两个对象实际上是否相同。如果是，您将获得重复项的异常(exception)。如果他们不这样做，则它们都保存在相同的字典哈希下。