algorithm - 集合的简单通用哈希函数

Question

请标记为重复，但到目前为止我发现的大多数问题都太具体或比我正在寻找的更复杂。例如。在 "What is a good hash function" ，接受的答案似乎是针对哈希字符串。

我最近开始使用 .NET 进行编程，但我发现很遗憾，内置类缺乏执行一些基本操作的能力，例如检查相等性和查找它们的哈希值。我敢肯定他们有他们的设计原因；无需捍卫 .NET。我只想知道当我需要使用集合作为字典的键时如何避免重大的偏离。例如，我想要包含所有相等值的两个不同的 List 对象映射到字典中的相同条目。开箱即用，他们不这样做:List 的默认行为是 List 不等于除自身以外的任何内容，因此具有相同值的列表的另一个实例是不同的键。

实现 Equals 非常简单。这是我不确定的哈希函数。

是否只有我可以在我的 GetHashCode 实现中调用的东西？

如果我必须从头开始编写，什么是真正简单但足够好的哈希算法？我可以使用 SHA1，但我认为这太过分了。我可以只对项目的所有哈希值进行异或，但我认为这会有一些令人讨厌的碰撞属性。我不在乎计算哈希是否快得惊人，但我不希望我的哈希表在具有某些特定分布的数据集上变慢到线性。我想要的是简单到我可以记住的东西。如果您能解释(或链接到)它为什么有效，则加分。

Answer 1

这里要格外小心。如果你创建一个 GetHashCode List<T> 的方法(或类似的集合)，那么大概它会做这样的事情:

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 hash 的方法来计算哈希码。另请查看 Wang hash(或位混合器)。)

除非您第一次计算该值并将其缓存，否则每次都会迭代所有项目 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> 的情况并不常见。或类似的集合作为字典或哈希表中的键。