是否可以组合私有成员的哈希码来生成新的哈希码？

Question

我有一个对象，我想为其生成唯一的哈希值（覆盖 GetHashCode()），但我想避免溢出或不可预测的情况。

该代码应该是组合一小部分字符串的哈希码的结果。

哈希码将是生成缓存键的一部分，因此理想情况下它们应该是唯一的，但是被哈希的可能值的数量很小，所以我认为这里的概率对我有利。

这样的事情就足够了并且有更好的方法吗？

int hash = 0;
foreach(string item in collection){
    hash += (item.GetHashCode() / collection.Count)
}
return hash;

编辑：感谢到目前为止的回答。 @Jon Skeet：不，顺序并不重要，

我想这几乎是另一个问题，但由于我使用结果来生成缓存密钥（字符串），使用 MD5 这样的加密哈希函数或仅使用字符串是否有意义这个 int 的表示？

Answer 1

马克和乔恩指出的基本面还不错，但就结果分布的均匀性而言，它们远非最佳。 遗憾的是，许多 Knuth 人复制的“乘以素数”方法并不是的最佳选择在许多情况下，可以通过更便宜的计算函数来实现更好的分布（尽管这在现代硬件上非常轻微）。 事实上，将素数投入哈希的许多方面不是万能药。

如果这些数据用于相当大的哈希表，我建议阅读 Bret Mulvey 对各种现代技术的出色研究和解释（而且不是那么现代）哈希技术可以用c#轻松完成。

请注意，各种散列函数的字符串的行为严重偏向于字符串是短（粗略地说，在位开始溢出之前对多少个字符进行散列）还是长。

最简单、最容易实现的方法之一也是最好的方法之一，即 Jenkins 一次一个哈希。

private static unsafe void Hash(byte* d, int len, ref uint h)
{
    for (int i = 0; i < len; i++)
    {
        h += d[i];
        h += (h << 10);
        h ^= (h >> 6);
    }
}

public unsafe static void Hash(ref uint h, string s)
{
    fixed (char* c = s)            
    {
        byte* b = (byte*)(void*)c;
        Hash(b, s.Length * 2, ref h);
    }
}

public unsafe static int Avalanche(uint h)
{
    h += (h<< 3);   
    h ^= (h>> 11);  
    h += (h<< 15);  
    return *((int*)(void*)&h);
}

然后你可以像这样使用它：

uint h = 0;
foreach(string item in collection) 
{
    Hash(ref h, item);
}
return Avalanche(h);

你可以像这样合并多个不同的类型：

public unsafe static void Hash(ref uint h, int data)
{ 
    byte* d = (byte*)(void*)&data;
    AddToHash(d, sizeof(int), ref h);
}

public unsafe static void Hash(ref uint h, long data)
{ 
    byte* d= (byte*)(void*)&data;
    Hash(d, sizeof(long), ref h);
}

如果你只能将字段作为对象访问而不了解内部结构，你可以简单地对每个类型调用 GetHashCode() 并将该值组合起来，如下所示：

uint h = 0;
foreach(var item in collection) 
{
    Hash(ref h, item.GetHashCode());
}
return Avalanche(h);

遗憾的是你不能执行 sizeof(T) 因此你必须单独执行每个结构。

如果您希望使用反射，您可以在每个类型的基础上构造一个函数，该函数对所有字段进行结构标识和散列。

如果您希望避免不安全的代码，那么您可以使用位掩码技术从整数（如果处理字符串则为字符）中提取各个位，而不会带来太多额外的麻烦。

Answer 2

哈希值并不意味着是唯一的 - 它们只是意味着在大多数情况下分布良好。 它们只是为了保持一致。 请注意，溢出不应该成为问题。

仅仅相加通常不是一个好主意，除法当然也不是一个好主意。 这是我通常使用的方法：

int result = 17;
foreach (string item in collection)
{
    result = result * 31 + item.GetHashCode();
}
return result;

如果您处于已检查的上下文中，您可能想故意将其设为未检查。

请注意，这假设顺序很重要，即 { "a", "b" } 应该与 { "b", "a" } 不同。 如果情况并非如此，请告诉我们。

Answer 3

只要您要组合其哈希码的成员遵循哈希码规则，这种方法就没有任何问题。 简而言之...

1. 私有成员的哈希码在对象的生命周期内不应更改
2. 容器不得更改私有成员指向的对象，以免它反过来更改容器的哈希码

Answer 4

如果项目的顺序并不重要（即 {"a","b"} 与 {"b","a"} 相同），那么您可以使用互斥或​​来组合哈希代码：

hash ^= item.GetHashCode();

[编辑：作为马克在对不同答案的评论中指出，这有一个缺点，即还为 {"a"} 和 {"a","b","b"} 等集合提供相同的哈希码。]

如果顺序很重要，您可以改为乘以一个质数并添加：（

hash *= 11;
hash += item.GetHashCode();

当您相乘时，有时会出现被忽略的溢出，但是通过与质数相乘，您会丢失最少的信息。如果您与 16 这样的数字相乘，每次您都会丢失四位信息，因此在八个项目之后，第一个项目的哈希码将完全消失。）