在列表上创建哈希值

本文关键字：哈希值 创建 列表 | 更新日期: 2023-09-27 18:07:13

我有一个包含 50 个实例的List<MyRichObject>。每个实例都有 1 或 2 个唯一属性，但在某种程度上它们都是唯一的，因为列表中只有一个位置，等等。

我想想出一种独特的方法来"散列"这个列表，这样它就与所有其他列表不同。在 .NET 4 中是否有一种聪明的方法可以做到这一点？

目的是为列表创建一种"名字对象"，以便可以将它们转储到队列中，并在以后根据其唯一值找到它们。

谢谢。

在列表上创建哈希值

TL;DR

public static int GetSequenceHashCode<T>(this IList<T> sequence)
{
    const int seed = 487;
    const int modifier = 31;
    unchecked
    {
        return sequence.Aggregate(seed, (current, item) =>
            (current*modifier) + item.GetHashCode());
    }            
}

为什么要为另一个答案而烦恼？

如果列表中有多个项目具有相同的哈希代码，则接受的答案可能会给出危险的不准确结果。例如，考虑以下输入：

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都是相同的。为什么？

如果你对一个数字本身进行XOR，你基本上会抵消它，即

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
                       // ↑   ↑ 
                       // these two cancel each other out

同样，对于每对foo和spam都会自我抵消的d。

哈希值是否必须代表列表的内容？换句话说，你会使用哈希来确定潜在的相等性吗？ 如果没有，那么只需创建一个新的 Guid 并使用它。

如果标识符确实需要表示列表的内容，则可以根据列表的内容生成哈希代码(这将效率低下，因为列表的内容可能会更改，因此您将无法缓存此值(或完全放弃哈希并使用Enumerable.SequenceEquals来确定相等性。

这是我如何实现获取List<T>哈希代码的示例。首先，如果你要得到一个特定对象的哈希代码，你真的应该确保该对象不会改变。如果该对象确实发生了更改，那么您的哈希代码就不再有用了。

处理可以"冻结"的列表(意味着在某个点之后不添加或删除任何项目(的最佳方法是调用 AsReadOnly 。这会给你一个ReadOnlyCollection<T>.为了安全起见，下面的实现取决于ReadOnlyCollection<T>，因此请记住这一点：

using System;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.Linq;
class Example
{
    static void Main()
    {
        var seqOne = new List<int> { 1, 2, 3, 4, 5, 6 };
        var seqTwo = new List<int> { 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<T>(this ReadOnlyCollection<T> sequence)
    {
        return sequence
            .Select(item => item.GetHashCode())
            .Aggregate((total, nextCode) => total ^ nextCode);
    }
}

哦，最后一件事 - 确保您的MyRichObject类型本身具有良好的GetHashCode实现，否则列表的哈希代码可能会在比较时产生大量误报。

相关文章：