17

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

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

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

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

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

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

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

4

4 回答 4

24

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

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

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

如果您处于选中的上下文中，您可能想要故意使其未选中。

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

于 2009-07-03T12:46:05.057 回答
24

Marc 和 Jon 指出的基本原理还不错，但就结果分布的均匀性而言，它们远非最佳。可悲的是，许多人从 Knuth 复制的“乘以素数”方法并不是最佳选择，在许多情况下，可以通过更便宜的计算函数来实现更好的分布（尽管这在现代硬件上非常轻微）。事实上，将素数放入散列的许多方面并不是灵丹妙药。

如果此数据用于显着大小的哈希表，我建议阅读Bret Mulvey对使用 c# 轻松完成的各种现代（而不是那么现代）散列技术的出色研究和解释。

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

最简单和最容易实现的一种也是最好的一种，Jenkins One at a time hash。

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) 所以你必须单独做每个结构。

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

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

于 2009-07-03T13:43:28.430 回答
1

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

  1. 私有成员的哈希码在对象的生命周期内不应该改变
  2. 容器不能改变私有成员指向的对象，以免反过来改变容器的哈希码
于 2009-07-03T12:45:55.477 回答
1

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

hash ^= item.GetHashCode();

[编辑：正如马克在对不同答案的评论中指出的那样，这样做的缺点是也给 {"a"} 和 {"a","b","b"} 之类的集合提供了相同的哈希码。]

如果顺序很重要，您可以乘以素数并添加：

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

（当你乘法时，你有时会得到一个被忽略的溢出，但是通过与素数相乘，你会丢失最少的信息。如果你乘以像 16 这样的数字，每次都会丢失四位信息，所以在八项，第一项的哈希码将完全消失。）

于 2009-07-03T12:58:16.743 回答