在列表上创建哈希值？

Question

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

我想提出一种独特的方法来"散列"这个列表,因此它与所有其他列表都是唯一的.在.NET 4中有一种聪明的方法吗？

目的是为列表创建一种"monniker",以便将它们转储到队列中,然后根据它们的独特价值找到它们.

谢谢.

Answer 1

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产生不同的seqeuence哈希,但GetSequenceHashCode暗示a,c并且d都是相同的.为什么？

如果你自己对一个数字进行异或,你基本上取消它,即

8 ^ 8 == 0;

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

异或相同的XOR再次给出原始结果,即

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

和同样与d其中每对foo和spam自行抵消.