4

请标记为重复，但到目前为止我发现的大多数问题都比我想要的更具体或更复杂。例如，在“什么是好的散列函数”中，接受的答案似乎是面向散列字符串的。

我最近开始使用 .NET 进行编程，但遗憾的是，内置类无法执行一些基本操作，例如检查相等性并找到它们的哈希值。我相信他们有他们的设计原因。无需为 .NET 辩护。当我需要使用集合作为字典的键时，我只想知道如何避免重要的旁白。例如，我希望两个包含所有相等值的不同 List 对象映射到字典中的同一条目。开箱即用，它们不这样做：List 的默认行为是 List 不等于除自身之外的任何东西，因此具有相同值的列表的另一个实例是不同的键。

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

在我的 GetHashCode 实现中是否提供了一些可以调用的东西？

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

4

3 回答 3

3

在这里要非常小心。如果你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 散列来计算散列码。还要查看Wang 散列（或位混合器）。）

除非您第一次计算该值并将其缓存，否则每次GetHashCode调用时您最终都会遍历所有项目。

所以你已经为你的集合创建了一个GetHashCodeandEquals并且你把一个实例放入了一个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>在字典或哈希表中使用或类似的集合作为键是非常罕见的。

于 2013-08-14T01:13:27.057 回答
2

以我的经验，如果你有一个东西的集合并且你想计算它们的哈希值，最好分别计算每个单独对象的哈希值；将所有这些哈希值收集到一个数组中。最后，计算散列值数组的散列值。

所有更简单的技术都相对较快地失效。（就像将这些值异或或乘以幻数和求和——这些都有各种病理性失败案例。）最后计算的一个额外的数组散列是一个很小的成本，并且总体上得到了回报。

于 2013-08-13T23:52:54.383 回答
0

一个好的散列函数同样适用于任何位的字符串——不仅仅是字符。但是，由于集合可能：

  1. 不一定在连续的内存块中，并且
  2. 包含您不想包含在散列中的部分（例如，从链表的一个元素到另一个元素的指针，对于具有相同内容的不同链表，这将是不同的，但在这种情况下，您希望具有相同的哈希值）。

...在我看来，这里的关键问题可能是“将一组单独的哈希值组合起来为集合生成哈希值的最佳方法是什么？”。

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

  1. 查找集合中项目的哈希值。
  2. 通过按照元素在集合中出现的顺序连接这些哈希值来创建位串。
  3. 使用任何合理的散列算法为该位串的散列值生成散列值。
  4. 使用上一步计算的哈希值作为集合的哈希值。
于 2013-08-13T23:53:20.887 回答