一个用于集合的简单通用哈希函数

Question

一个用于集合的简单通用哈希函数

4

请标记为重复，但我找到的大多数问题都太具体或比我要找的更复杂。例如，在 "什么是好的哈希函数" 中，被接受的答案似乎是面向字符串的。

最近我开始在.NET中编程，我觉得内置类缺乏一些基本功能，比如检查相等性和查找散列值。我相信它们有设计上的理由；没有必要为.NET辩护。我只想知道如何避免需要使用集合作为字典键时出现重大偏离。例如，我希望两个包含完全相同值的不同List对象映射到字典中的同一条目。默认情况下，它们不能：对于List，列表仅等于它本身，因此具有相同值的另一个列表实例是不同的键。

实现Equals很简单，而我不确定的是哈希函数。

提供了可以在我的GetHashCode实现中调用的内容吗？

如果我必须从头开始写，有什么非常简单但足够好的哈希算法吗？我可以使用SHA1，但我认为这可能过度了。我可以只是异或所有项的哈希值，但我认为这会有一些恶劣的碰撞属性。我不在乎计算哈希值的速度有多快，但我不希望我的哈希表在具有某些特定分布的数据集上变慢到线性。我想要的是非常简单，以至于我能够记住它。如果您能解释（或链接到）为什么它有效，那就更好了。

- morningstar

3个回答

2

根据我的经验，如果您有一组事物，并且想要计算它们的哈希值，则最好单独计算每个对象的哈希值；将所有这些哈希值收集到一个数组中。最后，计算您的哈希值数组的哈希。

所有简单的技术都很快失败。（例如，将值进行XOR运算或乘以魔数并求和 - 这些都有各种病态的失败情况。）在最后计算一个额外的哈希数组的成本很小，但总体效果很好。

- StilesCrisis

计算哈希值数组的哈希值 - 解释这是一个显而易见的步骤。 - morningstar

在我的情况下，我使用了Bob Jenkins的“lookup3”算法来对一块内存进行哈希。http://burtleburtle.net/bob/hash/doobs.html 您可以使用任何您喜欢的方法 - CRC32、MD5、Adler-32 或其他可将不透明的内存块输入并返回哈希值的方法。 - StilesCrisis

0

一个好的哈希函数应该对任何位数的字符串都能同样适用，而不仅仅是字符。然而，由于一个集合可能会有以下情况：

不一定在连续的内存块中，以及
包含您不想包含在哈希中的部分（例如从链表的一个元素指向另一个元素的指针，这些指针对于具有相同内容但不同链表的不同链表来说是不同的，但对于此情况，您希望它们具有相同的哈希值）。

因此，我认为关键问题可能是“将一组单独的哈希值组合成集合的哈希值的最佳方法是什么？”。

在我看来，XOR集合中各个元素的哈希值是一个合理的方法。我立即看到的唯一问题是，它会导致两个包含相同元素但顺序不同的集合哈希到相同的值。避免此问题的算法可能如下所示：

找到集合中每个项的哈希值。
按照元素在集合中出现的顺序将这些哈希值连接成一个位串。
使用任何合理的哈希算法为该哈希值位串生成一个哈希值。
使用上一步计算出的哈希值作为集合的哈希值。

- Simon

将值进行异或在一般情况下效果不佳。我曾经尝试过这种方法，但失败的次数太多了。您的第二种方法（将哈希结果附加到一个位字符串中，然后对该位字符串进行哈希）效果很好。基本上这是我在答案中推荐的改述 :) - StilesCrisis

我发现了一个早期的问题和答案集，其中讨论了组合哈希值的方法。请参见为什么XOR是默认的组合哈希方式？。简而言之：XOR很好，因为它保持熵，但是XOR相同的值会得到零结果（并且相同的值很常见，所以这是不好的），XOR也是可交换的（这是我在我的答案中提到的），这也可能不理想。因此，像@StilesCrisis建议的那样对单个哈希值的位串进行哈希，是更可取的。 - Simon

听起来还不错，但我遇到过一些参考资料，其中一些字符串哈希函数是针对ASCII字符进行优化的。例如，底部4位预计是最重要的。 - morningstar

从个人经验来看，我发现异或运算非常快，尽管它会比基准测试引起更多的冲突。碰撞是不可避免的，任何哈希函数都会引起它们。我建议制作一个小型测试套件。选择多个哈希函数并进行比较。我这样做了，速度与冲突的权衡使我选择了异或。 - Kshitij Banerjee

Kshitij，我和你做了一样的事情，做出了同样的选择，然后几年后我想知道为什么我的哈希表会发生这么多冲突。改变了它，突然间我的哈希表又开始正常工作了，代价是在一个微小的不透明数据块上再次调用哈希函数。 - StilesCrisis

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jim Mischel · Accepted Answer

在这里要非常小心。如果你为 List<T>（或类似的集合）创建了一个 GetHashCode 方法，那么它可能会像这样执行：

public override int GetHashCode()
{
    int hash = 13;
    foreach (var t in this)
    {
        // X is an operation (undefined here) that somehow combines
        // the previous hash value and the item's hash value
        hash = hash X t.GetHashCode();
    }
    return hash;
}

我建议使用类似于 Jenkins哈希的算法来计算哈希码。同时，还可以考虑Wang哈希（或位混合器）。

除非你在第一次计算并缓存它，否则每次调用GetHashCode时都会迭代所有项。

所以，你已经为集合创建了GetHashCode和Equals方法，并将其实例放入了Dictionary中。现在，你必须非常小心，不要更改集合（即不要添加或删除任何项），也不要更改集合内部的任何项。否则，GetHashCode的值将发生变化，而字典将无法正常工作。

如果你想将集合用作字典的键，我强烈建议你确保该集合是不可变的。

考虑另一个问题。列表相等的概念并不像您所示那样简单。例如，列表[1, 2, 3, 4, 5]和[5, 1, 3, 4, 2]是否相等？这取决于您对相等的定义。当然，如果您对相等的定义是“包含相同的项”，则A.Union(B) == A.Intersect(B)，这意味着它们相等。但是，如果顺序很重要，则列表不相等。

如果您的定义是“包含相同的项”，那么我上面展示的哈希码计算将无法工作，因为哈希码计算依赖于顺序。因此，如果您想计算这些列表的哈希码，您必须首先对它们进行排序。

如果列表不能包含重复项，则计算相等性就是创建一个哈希集合来存储一个列表，并在该哈希集合中查找另一个列表中的每个项。如果列表可以包含重复项，则您必须对其进行排序以确定相等性，或者使用某种具有计数的字典。这两者都意味着列表中包含的对象将实现某种形式的相等比较器等。

一些相等性的定义完全不考虑重复项。也就是说，[1, 2, 3] 等于 [3, 3, 3, 2, 1, 1]。

考虑到相等性的差异以及在定义 List<T> 的行为中允许这些差异所需的工作量，我能理解设计集合类的人为什么没有实现值相等性。特别是考虑到使用 List<T> 或类似的集合作为字典或哈希表中的键相当罕见。