我希望在我的所有类中覆盖对象的 GetHashCode() 方法。此方法返回一个 Int32。我所知道的所有加密哈希函数的返回值都不适合 32 位整数。我想尽可能地避免碰撞。我应该截断像 SHA-whatever 这样的安全散列，还是使用 32 位散列？如果使用 32 位散列，最好使用什么 32 位散列？
问问题
4480 次
4 回答
7
只是给大家一点信息。跨不同 .NET 平台的 GetHashCode() 有所不同。例如：.NET 2.0 中的 "Hello".GetHashCode() 与 .NET 4.0 中的 "Hello".GetHashCode() 产生不同的结果。因此，为什么不能使用 .NET 开箱即用地序列化 HashTable 或字典。
实现您自己的哈希算法可提供跨平台的一致性。只是让你知道，你不想低于 Int32。我的建议是坚持使用 Int64（长）。这样你就有更少的冲突，这是散列的目标:) 这是我几年前写的一个库。每个哈希算法都有其优点和缺点（速度与最少碰撞）。此特定版本使用字符串作为输入，但您可以根据需要对其进行修改：
static public class StringHash
{
//---------------------------------------------------------------------
static public Int64 RSHash(String str)
{
const Int32 b = 378551;
Int32 a = 63689;
Int64 hash = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash = hash * a + str[i];
a = a * b;
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 JSHash(String str)
{
Int64 hash = 1315423911;
for (Int32 i = 0; i < str.Length; i++)
{
hash ^= ((hash << 5) + str[i] + (hash >> 2));
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 ELFHash(String str)
{
Int64 hash = 0;
Int64 x = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash = (hash << 4) + str[i];
if ((x = hash & 0xF0000000L) != 0)
{
hash ^= (x >> 24);
}
hash &= ~x;
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 BKDRHash(String str)
{
const Int64 seed = 131; // 31 131 1313 13131 131313 etc..
Int64 hash = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash = (hash * seed) + str[i];
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 SDBMHash(String str)
{
Int64 hash = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash = str[i] + (hash << 6) + (hash << 16) - hash;
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 DJBHash(String str)
{
Int64 hash = 5381;
for (Int32 i = 0; i < str.Length; i++)
{
hash = ((hash << 5) + hash) + str[i];
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 DEKHash(String str)
{
Int64 hash = str.Length;
for (Int32 i = 0; i < str.Length; i++)
{
hash = ((hash << 5) ^ (hash >> 27)) ^ str[i];
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 BPHash(String str)
{
Int64 hash = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash = hash << 7 ^ str[i];
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 FNVHash(String str)
{
Int64 fnv_prime = 0x811C9DC5;
Int64 hash = 0;
for (Int32 i = 0; i < str.Length; i++)
{
hash *= fnv_prime;
hash ^= str[i];
}
return hash;
}
//---------------------------------------------------------------------
static public Int64 APHash(String str)
{
Int64 hash = 0xAAAAAAAA;
for (Int32 i = 0; i < str.Length; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ str[i] * (hash >> 3));
}
else
{
hash ^= (~((hash << 11) + str[i] ^ (hash >> 5)));
}
}
return hash;
}
}
于 2013-04-19T01:33:12.280 回答
2
Eric Lippert 创建了一篇关于如何正确实现 GetHashCode() 方法的精彩博客文章。您需要记住 GetHashCode() 的目的是将对象放入哈希表中。将它用于此目的意味着您将更可能希望在未来某个时间遍历它或对其进行排序。如果您使用加密函数来执行此操作，您的迭代或排序过程将运行得非常慢。加密功能旨在保护数据，而不是唯一标识它们。通读 Eric Lippert 的博文。它会帮助你
于 2013-04-19T01:16:52.327 回答
2
您可以GetHashCode通过截断 SHA 哈希来实现。但你可能不应该。
的目的GetHashCode是允许将对象插入到哈希表中。哈希表的目的是优化搜索：平均而言，在哈希表中找到一个键只需要 O(1) 时间，而对于树来说是 O(log n)，对于未排序的列表来说是 O(n)。
您确实希望您的GetHashCode方法最大限度地减少冲突，以防止您的哈希表查找退化为 O(n) 时间。但是您也希望它们快速，因为哈希表的全部意义在于优化。如果您的哈希码需要很长时间来计算，您不妨将数据存储在List.
加密哈希很慢。它们通常是这样设计的，以阻止暴力攻击。这使得它们不适合与GetHashCode.
那么，应该如何实施GetHashCode呢？一种简单且常用的方法就是对Equals函数中使用的所有成员变量进行异或运算。
struct Complex
{
double real;
double imag;
public override int GetHashCode()
{
return real.GetHashCode() ^ imag.GetHashCode();
}
// ...
}
另一种适用于类数组对象的简单方法是多项式哈希函数。
class MyClass
{
int[] data;
public override int GetHashCode()
{
int result = 0;
foreach (int n in data)
{
result = result * 41 + n;
}
return result;
}
// ...
}
如果您的类包含大量要散列的数据，您可能希望将散列码保存在成员变量中并在构造期间预先计算它，以便GetHashCode()可以使用该变量。
于 2013-04-19T00:23:11.837 回答
0
哈希值的宽度越短，发生冲突的可能性就越大。由于Int32最多存储 4294967296 个不同的值，因此您需要考虑这是否会为您的目的保留足够独特的值 - 这取决于这是用于安全性还是身份检查。
我对您为什么要覆盖感兴趣GetHashCode()，该值是否必须适合 32 位？如果是，为什么？
于 2013-04-18T23:00:33.737 回答