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

Question

我有一个对象,我想生成一个唯一的哈希(覆盖GetHashCode()),但我想避免溢出或不可预测的事情.

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

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

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

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

编辑:感谢您的答案到目前为止.@Jon Skeet:不,订单并不重要

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

Answer 1

哈希并不意味着是唯一的-他们只是为了很好地分布在大多数情况下.它们只是意味着一致.请注意,溢出应该不是问题.

只是添加通常不是一个好主意,而划分当然不是.这是我通常使用的方法:

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

如果您处于已检查的上下文中,则可能需要故意将其取消选中.

请注意,这假定顺序很重要,即{"a","b"}应与{"b","a"}不同.如果不是这样,请告诉我们.

Answer 2

Marc和Jon指出的基本面并不差,但就结果分布的均匀性而言,它们远非最优.可悲的是,许多人从Knuth复制的"乘以素数"方法并不是最好的选择,在许多情况下,通过更便宜的计算功能可以实现更好的分配(尽管这在现代硬件上非常轻微).事实上,将素数投入散列的许多方面并不是灵丹妙药.

如果这个数据用于大小很大的哈希表,我建议阅读Bret Mulvey对 c#轻松完成的各种现代(并非现代)哈希技术的优秀研究和解释.

请注意,使用各种散列函数的字符串的行为严重偏向于字符串很短(粗略地说在字符串开始溢出之前有多少字符被散列)或长.

最简单和最容易实现的一个也是最好的之一,Jenkins One一次哈希.

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

如果您希望使用反射,您可以在每个类型的基础上构建一个在所有字段上执行结构标识和散列的函数.

如果你想避免使用不安全的代码,那么你可以使用位掩码技术从int中提取单个位(如果处理字符串则为chars),而不需要太多额外的麻烦.