2

我一直在阅读和学习散列和散列表，并使用了一些代码（我对此仍然很陌生，所以我可能会说一些我误解的错误）。我遇到了完美哈希函数的问题。假设我有自己的自定义类型，它以某种方式具有完美的哈希函数：

class Foo
{
    private int data;

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

Anint的哈希码就是它int本身，所以我有一个完美的哈希函数，对吧？但是当我们使用哈希函数通过简单的公式将对象映射到哈希表时：

index = foo.GetHashCode() % hashtable.Length

我们得到一个变量索引，它也取决于我们在哈希表中有多少元素。如果哈希表的大小仅为 int.MaxValue，那么我们将拥有一个完美的哈希函数。例如，假设我们有一个大小为 2 的哈希表。如果我们对数字 1 和 3 进行哈希处理，我们得到

1 % 2 = 1
3 % 2 = 1

碰撞！我对哈希和哈希表有什么误解吗？结果表明，完美的哈希函数并不完美。

4

3 回答 3

7

到此为止，您都可以

index = foo.GetHashCode() % hashtable.Length

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

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

那么为什么我们没有碰撞Dictionary呢？事实上，我们这样做。如果两个对象在字典A中B确实具有相同的哈希值，我们就会发生冲突。发生的情况是字典A.Equals(B)作为最终检查运行，以查看两个对象是否实际上相同。如果是，则您会因重复而获得例外。如果他们不这样做，他们都被保存在同一个字典哈希下。

于 2013-05-11T20:48:47.370 回答
3

  1. 是的！（如前所述，根据定义）

  2. 您首先从哪里获得phf？你想散列一个固定的，即不同（即没有多重集）值的常量集 S到集 1..|S|，双射。显然，phf 取决于集合 S。

  3. 此外，从 S 中删除一个元素并添加另一个元素，几乎肯定会发生碰撞（新元素与旧元素的碰撞）。

  4. 因此，您实际上想要“用于某某定义/描述的集合的 phf”。然后我们可以尝试找到一个。

于 2013-12-07T14:33:53.063 回答
2

是的，完美的哈希函数保证不会发生冲突。

这就是它的定义！

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

集合 S 的完美散列函数是将 S 中的不同元素映射到一组整数的散列函数，没有冲突。完美的散列函数与其他散列函数有许多相同的应用，但优点是不必实现冲突解决

于 2013-05-11T20:44:40.613 回答