完美的哈希函数是否保证没有冲突？

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)作为最终检查运行,以查看这两个对象实际上是否相同.如果是,则会因为重复而获得例外.如果他们不这样做,他们都被保存在相同的字典哈希下.