是否可以组合私有成员的哈希码来生成新的哈希码?
-
21-08-2019 - |
题
我有一个对象,我想为其生成唯一的哈希值(覆盖 GetHashCode()),但我想避免溢出或不可预测的情况。
该代码应该是组合一小部分字符串的哈希码的结果。
哈希码将是生成缓存键的一部分,因此理想情况下它们应该是唯一的,但是被哈希的可能值的数量很小,所以我认为这里的概率对我有利。
这样的事情就足够了并且有更好的方法吗?
int hash = 0;
foreach(string item in collection){
hash += (item.GetHashCode() / collection.Count)
}
return hash;
编辑:感谢到目前为止的回答。@乔恩斯基特:不,顺序并不重要
我想这几乎是另一个问题,但由于我使用结果来生成缓存键(字符串),使用 MD5 这样的加密哈希函数或仅使用此 int 的字符串表示形式是否有意义?
解决方案
这是马克和乔恩指出,基本面不差,但他们远远没有达到最佳其结果的分布的均匀性方面。可悲的是方法,通过这么多的人从克努特复制“由素数相乘”是不是最好的选择很多情况下更好的分布可以用更便宜的来实现计算功能(虽然这是的非常的轻微现代硬件)。事实上投掷素数成散列的许多方面是没有万能一>
如果该数据用于显著大小的哈希表,我建议布雷特·穆尔维的出色的研究和解释各种现代(和不那么现代)散列技术用c#轻易完成。
请注意,随着各种散列函数字符串的行为是朝向wehther字符串是短的(粗略地说有多少个字符的位开始到超过流动之前被散列),或长严重偏见。
其中一个最简单和最容易实现也是最好的一个,所述詹金斯一次一个散列。
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),所以必须执行各自独立结构体。
如果你想使用反射可以基于每个类型的基础上构造一个函数,它确实结构同一性和散列上的所有字段。
如果你想避免不安全的代码,那么你可以使用位掩码技术(如处理字符串和字符)与没有太多额外的麻烦拔出从单个整数位。
其他提示
hash是不是的意味着的是独一无二的 - 他们只是为了很好地分布在大多数情况下。他们只是为了保持一致。需要注意的是溢出不应该是一个问题。
只需添加通常不是一个好主意,当然划分不是。下面是我通常使用的方法:
int result = 17;
foreach (string item in collection)
{
result = result * 31 + item.GetHashCode();
}
return result;
如果您在选中的上下文是否则,你可能想故意让它选中。
请注意,这里假设顺序是很重要的,即该{“一”,“B”}应该从{“B”,“一个”}不同。请让我们知道这是不是这样的。
只要您要组合其哈希码的成员遵循哈希码规则,这种方法就没有任何问题。简而言之 ...
- 私有成员的哈希码在对象的生命周期内不应更改
- 容器不得更改私有成员指向的对象,以免它反过来更改容器的哈希码
如果该项目的顺序并不重要(即{“一”,“B”}相同{“B”,“A”}),则可以使用排他性或到散列代码结合:
hash ^= item.GetHashCode();
[编辑:作为标记在到一个不同的答案评论所指出的,这具有也得到像{“一”}和{“一”,“B”,“B”}相同的散列码集合中的缺点]
如果顺序很重要,你可以改为由一个素数乘法和加法:
hash *= 11;
hash += item.GetHashCode();
(当你乘你有时会得到被忽略溢出,但如果用你失去了最基本的信息素数相乘,如果你不是用一个数字,如16倍,你将失去的每次4位信息,所以经过八个项目从所述第一项目的哈希码将被完全消失了。)