在一个列表上创建哈希值？

28 浏览
0 Comments

在一个列表上创建哈希值？

我有一个包含50个实例的List。每个实例都有1或2个独特的属性，但从某种意义上说它们都是独一无二的，因为列表中的位置也是唯一的。

我想找到一种独特的方式来对这个列表进行"哈希"，以便它与其他所有列表都不同。在.NET 4中有没有聪明的方法可以做到这一点？

这样做的目的是为列表创建一种"标识符"，以便它们可以被放入队列中，并且可以根据其独特值稍后找到。

谢谢。

0

2 答案

0 Comments

问题：在一个列表上创建哈希值的原因和解决方法

哈希是否代表列表的内容？换句话说，你是否使用哈希来确定可能的相等性？如果不是的话，只需创建一个新的 GUID 并使用它。

如果标识符确实需要表示列表的内容，那么您可以根据列表的内容生成一个哈希码（这将是低效的，因为您将无法缓存此值，因为列表的内容可能会更改），或者放弃哈希，并使用 Enumerable.SequenceEquals 来确定相等性。

下面是我实现获取 List 的哈希码的示例。首先，如果要为特定对象获取哈希码，你确实应该确保该对象不会更改。如果该对象发生更改，则哈希码将不再有效。

与可以“冻结”（即在某一点之后不能添加或删除项）的列表一起工作的最佳方法是调用 AsReadOnly。这将为您提供一个 ReadOnlyCollection。下面的实现依赖于 ReadOnlyCollection，以确保安全，请记住这一点：

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
class Example
{
    static void Main()
    {
        var seqOne = new List { 1, 2, 3, 4, 5, 6 };
        var seqTwo = new List { 6, 5, 4, 3, 2, 1 };
        var seqOneCode = seqOne.AsReadOnly().GetSequenceHashCode();
        var seqTwoCode = seqTwo.AsReadOnly().GetSequenceHashCode();
        Console.WriteLine(seqOneCode == seqTwoCode);
    }
}
static class Extensions
{
    public static int GetSequenceHashCode(this ReadOnlyCollection sequence)
    {
        return sequence
            .Select(item => item.GetHashCode())
            .Aggregate((total, nextCode) => total ^ nextCode);
    }
}

另外，确保您的 MyRichObject 类具有良好的 GetHashCode 实现，否则列表的哈希码在比较时可能会产生许多误报。

谢谢。这不是为了确定相等性，而是为了创建一个基于列表内容唯一的值。我创建了 500 个这样的列表并将它们放入队列中，我想检查队列并确保队列中的所有内容都是不同的。

- 我明白了，但在队列中检查不同的项是一个相等性的问题。你知道一个项是不同的方式是它不等于任何其他项。这些列表在放入队列后是否会更改？

感谢帮助我思考这个问题。不，一旦列表进入队列，它们就不会再更改。我相信我确实想要基于每个列表的内容创建一个哈希。

太棒了。我以前使用序列化做了一些复杂的事情，然后得到一个哈希。你的方法看起来更好。谢谢。

0
0 Comments

最近在研究在列表上创建哈希值的问题时，我发现了一个有趣的解决方案。在这个问题中，我发现了一个问题，以及一个修复这个问题的方法。

问题的出现是因为在现有的解决方案中，如果列表中有多个具有相同哈希码的项，那么可能会产生不准确的结果。这个问题可以通过以下示例来说明：

var a = new []{ "foo" };
var b = new []{ "foo", "bar" };
var c = new []{ "foo", "bar", "spam" };
var d = new []{ "seenoevil", "hearnoevil", "speaknoevil" };

这些示例产生了不同的结果，表明它们都是唯一的集合。很好！现在我们来尝试一个重复的示例：

var e = new []{ "foo", "bar", "spam" };

`GetSequenceHashCode` 应该为 `c` 和 `e` 产生相同的结果 - 它确实如此。到目前为止还不错。现在我们来尝试一下顺序不同的示例：

var f = new []{ "spam", "bar", "foo" };

糟糕了... `GetSequenceHashCode` 表示 `f` 等于 `c` 和 `e`，但事实并非如此。为什么会发生这种情况呢？让我们先来看看实际的哈希码值，以 `c` 为例：

int hashC = "foo".GetHashCode() ^ 
            "bar".GetHashCode() ^ 
            "spam".GetHashCode();

由于这里的确切数字并不重要，为了更清晰地演示，让我们假设这三个字符串的哈希码是 `foo=8`，`bar=16` 和 `spam=32`。所以：

int hashC = 8 ^ 16 ^ 32;

或者将其分解为二进制表示：

8 ^ 16 ^ 32 == 56;
//  8 = 00001000
//  ^
// 16 = 00010000
//  ^
// 32 = 00100000
//  =
// 56   00111000

现在你应该能看到为什么这个实现忽略了列表中的项目顺序，即 `8^16^32 = 16^8^32 = 32^16^8` 等等。

其次，还存在一个重复项的问题。即使你假设在不同的顺序中拥有相同的内容是可以接受的（这不是我鼓励的方法），我认为没有人会认为下面的行为是可取的。让我们尝试一些含有重复项的变种：

var a = new []{ "foo", "bar", "spam" };
var b = new []{ "foo", "bar", "spam", "foo" };
var c = new []{ "foo", "bar", "spam", "foo", "foo" };
var d = new []{ "foo", "bar", "spam", "foo", "foo", "spam", "foo", "spam", "foo" };

尽管 `a` 和 `b` 生成了不同的序列哈希，但 `GetSequenceHashCode` 表示 `a`、`c` 和 `d` 都是相同的。为什么呢？

如果你使用一个数与自身进行异或运算，你就会将它消除掉，即：

8 ^ 8 == 0;
//  8 = 00001000
//  ^
//  8 = 00001000
//  =
//  0 = 00000000

再次异或相同的数会得到原始结果，即：

8 ^ 8 ^ 8 == 8;
//  8 = 00001000
//  ^
//  8 = 00001000
//  ^
//  8 = 00001000
//  =
//  8 = 00001000

因此，如果我们再次看一下 `a` 和 `c`，将简化后的哈希码代入：

var a = new []{ 8, 16, 32 };
var c = new []{ 8, 16, 32, 8, 8 };

计算哈希码为：

int hashA = 8 ^ 16 ^ 32;         // = 56
int hashC = 8 ^ 16 ^ 32 ^ 8 ^ 8; // = 56
                       // ↑   ↑ 
                       // 这两个彼此抵消掉了

对于 `d` 也是如此，其中每对 `foo` 和 `spam` 都会相互抵消。

在这个回答中，提供了一个很好的解决方案。将我的实现更改为 `IEnumerable` 的扩展，以包括其他集合。我很好奇种子和修饰符的值是从哪里来的，或者只要修饰符不是 0 或 1 就行。

31 和 487 都是质数。为什么使用质数？这个问题已经在其他回答中有了详细的解释，例如：[why should hash functions use a prime number modulus](https://stackoverflow.com/questions/1145217)

0