在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
当前回答
直到最近,我的回答都很接近乔恩·斯基特的回答。然而,我最近开始了一个使用两个哈希表的幂的项目,即内部表大小为8、16、32等的哈希表。
而且非常糟糕。因此,经过一点实验和研究后,我开始用以下方法重新散列我的散列:
public static int ReHash(int source)
{
unchecked
{
ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
ulong d = 0xE2ADBEEFDEADBEEF ^ c;
ulong a = d += c = c << 15 | c >> -15;
ulong b = a += d = d << 52 | d >> -52;
c ^= b += a = a << 26 | a >> -26;
d ^= c += b = b << 51 | b >> -51;
a ^= d += c = c << 28 | c >> -28;
b ^= a += d = d << 9 | d >> -9;
c ^= b += a = a << 47 | a >> -47;
d ^= c += b << 54 | b >> -54;
a ^= d += c << 32 | c >> 32;
a += d << 25 | d >> -25;
return (int)(a >> 1);
}
}
然后我的两个哈希表的能力就不再糟糕了。
但这让我很不安,因为上面的方法不应该奏效。或者更准确地说,除非原始的GetHashCode()以非常特殊的方式很差,否则它不应该工作。
重新混合哈希代码并不能改善一个好的哈希代码,因为唯一可能的效果是我们引入了更多的冲突。
重新混合哈希代码并不能改善糟糕的哈希代码,因为唯一可能的效果是我们将值53上的大量冲突更改为值183487291的大量冲突。
重新混合哈希代码只能改进哈希代码,该哈希代码至少在避免整个范围内的绝对冲突(232个可能值)方面做得相当好,但在为哈希表中的实际使用而进行模化时,在避免冲突方面做得很差。虽然二次幂表的简单模使这一点更加明显,但它对更常见的素数表也有负面影响,这并不是那么明显(重新散列的额外工作将超过好处,但好处仍然存在)。
编辑:我还使用了开放寻址,这也会增加对冲突的敏感度,也许比二的幂更敏感。
好吧,这令人不安的是,.NET(或这里的研究)中的string.GetHashCode()实现可以通过这种方式改进多少(由于较少的冲突,测试运行速度大约快20-30倍),更令人不安我自己的哈希代码可以改进多少(远远不止于此)。
我过去编写的所有GetHashCode()实现,实际上都是这个网站上答案的基础,比我想象的要糟糕得多。很多时候,它对于很多用途来说“足够好”,但我想要更好的东西。
所以我把这个项目放在一边(反正它是一个宠物项目),开始研究如何在.NET中快速生成一个好的、分布良好的哈希代码。
最后,我决定将SpookyHash移植到.NET。实际上,上面的代码是使用SpookyHash从32位输入生成32位输出的快速路径版本。
现在,SpookyHash不是一个好的快速记忆代码。我的端口就更少了,因为我手动内联了很多端口以提高速度*。但这就是代码重用的目的。
然后我把这个项目放在一边,因为正如最初的项目产生了如何产生更好的哈希代码的问题,所以这个项目产生了怎样产生更好的.NET memcpy的问题。
然后我回来了,并生成了大量重载,以便将几乎所有的原生类型(十进制†除外)轻松地输入到哈希代码中。
它速度很快,鲍勃·詹金斯(Bob Jenkins)值得称赞,因为我移植的原始代码速度更快,尤其是在64位机器上,算法经过了优化。
完整的代码可以在https://bitbucket.org/JonHanna/spookilysharp/src但是考虑到上面的代码是它的简化版本。
然而,由于它现在已经写好了,因此可以更容易地使用它:
public override int GetHashCode()
{
var hash = new SpookyHash();
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
它还需要种子值,因此,如果您需要处理不受信任的输入,并希望防止哈希DoS攻击,您可以根据正常运行时间或类似情况设置种子,并使攻击者无法预测结果:
private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
//produce different hashes ever time this application is restarted
//but remain consistent in each run, so attackers have a harder time
//DoSing the hash tables.
var hash = new SpookyHash(hashSeed0, hashSeed1);
hash.Update(field1);
hash.Update(field2);
hash.Update(field3);
return hash.Final().GetHashCode();
}
*这方面的一个大惊喜是,手动内联返回(x<<n)|(x>>-n)的旋转方法改进了性能。我本可以确定抖动会为我内联,但评测显示的情况并非如此。
†十进制虽然来自C#,但从.NET角度看不是本机。它的问题是,它自己的GetHashCode()将精度视为重要,而它自己的Equals()则没有。两者都是有效的选择,但不是那样混合。在实现自己的版本时,您需要选择执行一个或另一个,但我不知道您想要哪个。
‡通过比较。如果在字符串上使用,64位的SpookyHash要比32位的string.GetHashCode()快得多,这比64位的string.GetHashCode()要快得多。
其他回答
我在使用上面选择的实现时遇到了浮点和小数的问题。
此测试失败(浮点数;哈希值相同,即使我将2个值切换为负值):
var obj1 = new { A = 100m, B = 100m, C = 100m, D = 100m};
var obj2 = new { A = 100m, B = 100m, C = -100m, D = -100m};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
但是这个测试通过了(int):
var obj1 = new { A = 100m, B = 100m, C = 100, D = 100};
var obj2 = new { A = 100m, B = 100m, C = -100, D = -100};
var hash1 = ComputeHash(obj1.A, obj1.B, obj1.C, obj1.D);
var hash2 = ComputeHash(obj2.A, obj2.B, obj2.C, obj2.D);
Assert.IsFalse(hash1 == hash2, string.Format("Hashcode values should be different hash1:{0} hash2:{1}",hash1,hash2));
我改变了我的实现,不再对原始类型使用GetHashCode,它似乎工作得更好
private static int InternalComputeHash(params object[] obj)
{
unchecked
{
var result = (int)SEED_VALUE_PRIME;
for (uint i = 0; i < obj.Length; i++)
{
var currval = result;
var nextval = DetermineNextValue(obj[i]);
result = (result * MULTIPLIER_VALUE_PRIME) + nextval;
}
return result;
}
}
private static int DetermineNextValue(object value)
{
unchecked
{
int hashCode;
if (value is short
|| value is int
|| value is byte
|| value is sbyte
|| value is uint
|| value is ushort
|| value is ulong
|| value is long
|| value is float
|| value is double
|| value is decimal)
{
return Convert.ToInt32(value);
}
else
{
return value != null ? value.GetHashCode() : 0;
}
}
}
我想把我的最新发现添加到我经常提到的这个主题中。
我当前的visual studio/项目设置提供了将元组自动重构为结构的功能。这将生成如下GetHashCode函数:
public override int GetHashCode()
{
int hashCode = -2088324004;
hashCode = hashCode * -1521134295 + AuftragGesperrt.GetHashCode();
hashCode = hashCode * -1521134295 + Auftrag_gesperrt_von.GetHashCode();
hashCode = hashCode * -1521134295 + Auftrag_gesperrt_am.GetHashCode();
return hashCode;
}
编辑:为了澄清AuftragGesperrt、Auftrag _gesperrt_von和Auftrag-gesperrt _am是财产。如果微软的开发人员使用这个功能,这可能是一个不错的解决方案。
这是我使用JonSkeet实现的助手类。
public static class HashCode
{
public const int Start = 17;
public static int Hash<T>(this int hash, T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked((hash * 31) + h);
}
}
用法:
public override int GetHashCode()
{
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
如果要避免为System.Int32编写扩展方法:
public readonly struct HashCode
{
private readonly int _value;
public HashCode(int value) => _value = value;
public static HashCode Start { get; } = new HashCode(17);
public static implicit operator int(HashCode hash) => hash._value;
public HashCode Hash<T>(T obj)
{
var h = EqualityComparer<T>.Default.GetHashCode(obj);
return unchecked(new HashCode((_value * 31) + h));
}
public override int GetHashCode() => _value;
}
它仍然避免了任何堆分配,使用方式完全相同:
public override int GetHashCode()
{
// This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
// And the result is implicitly converted to `Int32`.
return HashCode.Start
.Hash(_field1)
.Hash(_field2)
.Hash(_field3);
}
编辑(2018年5月):EqualityComparer<T>。默认getter现在是JIT内在的-Stephen Toub在这篇博文中提到了pull请求。
我通常会使用Josh Bloch精彩的有效Java中给出的实现。它很快,创建了一个很好的哈希,不太可能导致冲突。选择两个不同的素数,例如17和23,并执行以下操作:
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = 17;
// Suitable nullity checks etc, of course :)
hash = hash * 23 + field1.GetHashCode();
hash = hash * 23 + field2.GetHashCode();
hash = hash * 23 + field3.GetHashCode();
return hash;
}
}
正如评论中所指出的,你可能会发现最好选择一个大素数来乘。很显然486187639很好。。。虽然我见过的大多数小数字的例子都倾向于使用素数,但至少有一些类似的算法经常使用非素数。例如,在后面的FNV示例中,我使用的数字显然很好,但初始值不是质数。(不过乘法常数是质数。我不知道这有多重要。)
这比XORing散列码的常见做法要好,主要原因有两个。假设我们有一个具有两个int字段的类型:
XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y
顺便说一下,早期的算法是C#编译器当前用于匿名类型的算法。
这个页面提供了很多选项。我认为,在大多数情况下,上述内容“足够好”,而且非常容易记住并正确理解。FNV替代方案同样简单,但使用不同的常数和XOR代替ADD作为组合操作。它看起来像下面的代码,但正常的FNV算法对单个字节进行操作,因此这需要进行修改,以每个字节执行一次迭代,而不是每个32位哈希值。FNV也设计用于可变长度的数据,而我们在这里使用它的方式总是用于相同数量的字段值。对这个答案的评论表明,这里的代码实际上并不像上面的添加方法那样有效(在测试的示例案例中)。
// Note: Not quite FNV!
public override int GetHashCode()
{
unchecked // Overflow is fine, just wrap
{
int hash = (int) 2166136261;
// Suitable nullity checks etc, of course :)
hash = (hash * 16777619) ^ field1.GetHashCode();
hash = (hash * 16777619) ^ field2.GetHashCode();
hash = (hash * 16777619) ^ field3.GetHashCode();
return hash;
}
}
请注意,需要注意的一点是,理想情况下,您应该防止在将其添加到依赖于哈希代码的集合后,对等式敏感(因此对哈希代码敏感)的状态发生变化。
根据文件:
可以为不可变引用类型重写GetHashCode。通常,对于可变引用类型,只有在以下情况下才应重写GetHashCode:您可以从不可变的字段计算哈希代码;或当可变对象包含在依赖其哈希代码的集合中时,可以确保该对象的哈希代码不会更改。
FNV文章的链接已断开,但这是互联网档案馆的一份副本:永恒的困惑-哈希的艺术
使用System.HashCode
如果使用的是.NET Standard 2.1或更高版本,则可以使用System.HashCode结构。在早期的框架中,它可以从Microsoft.Bcl.HashCode包中获得。有两种使用方法:
HashCode.Combine
Combine方法可用于创建哈希代码,最多可提供八个对象。
public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);
HashCode.添加
Add方法帮助您处理集合:
public override int GetHashCode()
{
var hashCode = new HashCode();
hashCode.Add(this.object1);
foreach (var item in this.collection)
{
hashCode.Add(item);
}
return hashCode.ToHashCode();
}
GetHashCode变得简单
System.HashCode的替代品,超级容易使用,但速度仍然很快。您可以阅读完整的博客文章“GetHashCode Made Easy”以了解更多详细信息和评论。
用法示例
public class SuperHero
{
public int Age { get; set; }
public string Name { get; set; }
public List<string> Powers { get; set; }
public override int GetHashCode() =>
HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}
实施
public struct HashCode : IEquatable<HashCode>
{
private const int EmptyCollectionPrimeNumber = 19;
private readonly int value;
private HashCode(int value) => this.value = value;
public static implicit operator int(HashCode hashCode) => hashCode.value;
public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);
public static bool operator !=(HashCode left, HashCode right) => !(left == right);
public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));
public static HashCode OfEach<T>(IEnumerable<T> items) =>
items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));
public HashCode And<T>(T item) =>
new HashCode(CombineHashCodes(this.value, GetHashCode(item)));
public HashCode AndEach<T>(IEnumerable<T> items)
{
if (items == null)
{
return new HashCode(this.value);
}
return new HashCode(GetHashCode(items, this.value));
}
public bool Equals(HashCode other) => this.value.Equals(other.value);
public override bool Equals(object obj)
{
if (obj is HashCode)
{
return this.Equals((HashCode)obj);
}
return false;
}
public override int GetHashCode() => this.value.GetHashCode();
private static int CombineHashCodes(int h1, int h2)
{
unchecked
{
// Code copied from System.Tuple a good way to combine hashes.
return ((h1 << 5) + h1) ^ h2;
}
}
private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;
private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
{
var temp = startHashCode;
var enumerator = items.GetEnumerator();
if (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
while (enumerator.MoveNext())
{
temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
}
}
else
{
temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
}
return temp;
}
}
什么是好算法?
表演
计算哈希码的算法需要很快。简单的算法通常会更快。不分配额外内存的内存也会减少垃圾收集的需求,这反过来也会提高性能。
具体来说,在C#哈希函数中,您经常使用unchecked关键字来停止溢出检查以提高性能。
确定性
哈希算法需要是确定性的,即给定相同的输入,它必须始终产生相同的输出。
减少碰撞
计算哈希代码的算法需要将哈希冲突保持在最小值。哈希冲突是在两个不同对象上对GetHashCode的两次调用产生相同哈希代码时发生的情况。请注意,碰撞是允许的(有些人认为不允许),但应将其保持在最低限度。
许多哈希函数包含像17或23这样的幻数。这些是特殊的素数,与使用非素数相比,由于其数学财产有助于减少散列冲突。
哈希一致性
一个好的哈希函数应该在其输出范围内尽可能均匀地映射期望的输入,即,它应该基于均匀分布的输入输出广泛的哈希。它应该具有哈希一致性。
阻止的DoS
在.NETCore中,每次重新启动应用程序时,都会得到不同的哈希代码。这是防止拒绝服务攻击(DoS)的安全功能。对于.NET Framework,应通过添加以下App.config文件来启用此功能:
<?xml version ="1.0"?>
<configuration>
<runtime>
<UseRandomizedStringHashAlgorithm enabled="1" />
</runtime>
</configuration>
由于此特性,哈希代码不应在创建它们的应用程序域之外使用,也不应将其用作集合中的关键字段,也不应该持久化。
请在此处阅读更多信息。
加密安全?
算法不必是加密哈希函数。这意味着它不必满足以下条件:
生成生成给定哈希值的消息是不可行的。找到具有相同哈希值的两个不同消息是不可行的。对消息进行一次小的更改应该会对哈希值进行广泛的更改,以使新的哈希值看起来与旧的哈希值不相关(雪崩效应)。