在.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（）要快得多。
其他回答
在Equals（）比较多个字段的大多数情况下，GetHash（）对一个字段或多个字段进行散列并不重要。您只需确保计算哈希值非常便宜（请不要分配）和快速（没有繁重的计算，当然也没有数据库连接），并提供良好的分布。
重型起吊应是Equals（）方法的一部分；哈希应该是一个非常便宜的操作，以便能够对尽可能少的项目调用Equal（）。
最后一个提示：不要依赖GetHashCode（）在多个应用程序运行中保持稳定。许多.Net类型不能保证它们的哈希代码在重新启动后保持不变，因此只能对内存中的数据结构使用GetHashCode（）的值。
如果我们的财产不超过8处（希望如此），这里还有另一种选择。
ValueTuple是一个结构，似乎有一个可靠的GetHashCode实现。
这意味着我们可以简单地这样做：
// Yay, no allocations and no custom implementations!
public override int GetHashCode() => (this.PropA, this.PropB).GetHashCode();
让我们来看看.NETCore当前对ValueTuple的GetHashCode的实现。
这来自ValueTuple：
internal static int CombineHashCodes(int h1, int h2)
{
return HashHelpers.Combine(HashHelpers.Combine(HashHelpers.RandomSeed, h1), h2);
}
internal static int CombineHashCodes(int h1, int h2, int h3)
{
return HashHelpers.Combine(CombineHashCodes(h1, h2), h3);
}
这来自HashHelper：
public static readonly int RandomSeed = Guid.NewGuid().GetHashCode();
public static int Combine(int h1, int h2)
{
unchecked
{
// RyuJIT optimizes this to use the ROL instruction
// Related GitHub pull request: dotnet/coreclr#1830
uint rol5 = ((uint)h1 << 5) | ((uint)h1 >> 27);
return ((int)rol5 + h1) ^ h2;
}
}
英语：
向左旋转（循环移位）h1 5个位置。将结果和h1相加。将结果与h2进行异或运算。首先对{static random seed，h1}执行上述操作。对于每个其他项目，对上一个结果和下一个项目（例如h2）执行操作。
如果能更多地了解这个ROL-5散列代码算法的财产，那就太好了。
遗憾的是，为我们自己的GetHashCode延迟ValueTuple可能不像我们希望的那样快。相关讨论中的这条评论说明了直接调用HashHelpers.Combine更具性能。另一方面，这是内部的，所以我们必须复制代码，牺牲了我们在这里获得的大部分。此外，我们将负责记住首先与随机种子结合。我不知道如果我们跳过这一步会有什么后果。
我想把我的最新发现添加到我经常提到的这个主题中。
我当前的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是财产。如果微软的开发人员使用这个功能，这可能是一个不错的解决方案。
这是一个实现Josh Bloch实现的静态助手类；并且提供了显式重载来“防止”装箱，并且还专门为长原语实现哈希。
您可以传递与equals实现匹配的字符串比较。
因为Hash输出始终是int，所以您可以只链接Hash调用。
using System;
using System.Collections;
using System.Collections.Generic;
using System.Reflection;
using System.Runtime.CompilerServices;
namespace Sc.Util.System
{
/// <summary>
/// Static methods that allow easy implementation of hashCode. Example usage:
/// <code>
/// public override int GetHashCode()
/// => HashCodeHelper.Seed
/// .Hash(primitiveField)
/// .Hsh(objectField)
/// .Hash(iEnumerableField);
/// </code>
/// </summary>
public static class HashCodeHelper
{
/// <summary>
/// An initial value for a hashCode, to which is added contributions from fields.
/// Using a non-zero value decreases collisions of hashCode values.
/// </summary>
public const int Seed = 23;
private const int oddPrimeNumber = 37;
/// <summary>
/// Rotates the seed against a prime number.
/// </summary>
/// <param name="aSeed">The hash's first term.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
private static int rotateFirstTerm(int aSeed)
{
unchecked {
return HashCodeHelper.oddPrimeNumber * aSeed;
}
}
/// <summary>
/// Contributes a boolean to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aBoolean">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, bool aBoolean)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (aBoolean
? 1
: 0);
}
}
/// <summary>
/// Contributes a char to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aChar">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, char aChar)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aChar;
}
}
/// <summary>
/// Contributes an int to the developing HashCode seed.
/// Note that byte and short are handled by this method, through implicit conversion.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aInt">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, int aInt)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ aInt;
}
}
/// <summary>
/// Contributes a long to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aLong">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, long aLong)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ (int)(aLong ^ (aLong >> 32));
}
}
/// <summary>
/// Contributes a float to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aFloat">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, float aFloat)
{
unchecked {
return HashCodeHelper.rotateFirstTerm(aSeed)
+ Convert.ToInt32(aFloat);
}
}
/// <summary>
/// Contributes a double to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aDouble">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, double aDouble)
=> aSeed.Hash(Convert.ToInt64(aDouble));
/// <summary>
/// Contributes a string to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aString">The value to contribute.</param>
/// <param name="stringComparison">Optional comparison that creates the hash.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(
this int aSeed,
string aString,
StringComparison stringComparison = StringComparison.Ordinal)
{
if (aString == null)
return aSeed.Hash(0);
switch (stringComparison) {
case StringComparison.CurrentCulture :
return StringComparer.CurrentCulture.GetHashCode(aString);
case StringComparison.CurrentCultureIgnoreCase :
return StringComparer.CurrentCultureIgnoreCase.GetHashCode(aString);
case StringComparison.InvariantCulture :
return StringComparer.InvariantCulture.GetHashCode(aString);
case StringComparison.InvariantCultureIgnoreCase :
return StringComparer.InvariantCultureIgnoreCase.GetHashCode(aString);
case StringComparison.OrdinalIgnoreCase :
return StringComparer.OrdinalIgnoreCase.GetHashCode(aString);
default :
return StringComparer.Ordinal.GetHashCode(aString);
}
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// Each element may be a primitive, a reference, or a possibly-null array.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aArray">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, IEnumerable aArray)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (object item in aArray) {
++countPlusOne;
if (item is IEnumerable arrayItem) {
if (!object.ReferenceEquals(aArray, arrayItem))
aSeed = aSeed.Hash(arrayItem); // recursive call!
} else
aSeed = aSeed.Hash(item);
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null array to the developing HashCode seed.
/// You must provide the hash function for each element.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aArray">CAN be null.</param>
/// <param name="hashElement">Required: yields the hash for each element
/// in <paramref name="aArray"/>.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash<T>(this int aSeed, IEnumerable<T> aArray, Func<T, int> hashElement)
{
if (aArray == null)
return aSeed.Hash(0);
int countPlusOne = 1; // So it differs from null
foreach (T item in aArray) {
++countPlusOne;
aSeed = aSeed.Hash(hashElement(item));
}
return aSeed.Hash(countPlusOne);
}
/// <summary>
/// Contributes a possibly-null object to the developing HashCode seed.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="aObject">CAN be null.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int Hash(this int aSeed, object aObject)
{
switch (aObject) {
case null :
return aSeed.Hash(0);
case bool b :
return aSeed.Hash(b);
case char c :
return aSeed.Hash(c);
case int i :
return aSeed.Hash(i);
case long l :
return aSeed.Hash(l);
case float f :
return aSeed.Hash(f);
case double d :
return aSeed.Hash(d);
case string s :
return aSeed.Hash(s);
case IEnumerable iEnumerable :
return aSeed.Hash(iEnumerable);
}
return aSeed.Hash(aObject.GetHashCode());
}
/// <summary>
/// This utility method uses reflection to iterate all specified properties that are readable
/// on the given object, excluding any property names given in the params arguments, and
/// generates a hashcode.
/// </summary>
/// <param name="aSeed">The developing hash code, or the seed: if you have no seed, use
/// the <see cref="Seed"/>.</param>
/// <param name="aObject">CAN be null.</param>
/// <param name="propertySelector"><see cref="BindingFlags"/> to select the properties to hash.</param>
/// <param name="ignorePropertyNames">Optional.</param>
/// <returns>A hash from the properties contributed to <c>aSeed</c>.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashAllProperties(
this int aSeed,
object aObject,
BindingFlags propertySelector
= BindingFlags.Instance
| BindingFlags.Public
| BindingFlags.GetProperty,
params string[] ignorePropertyNames)
{
if (aObject == null)
return aSeed.Hash(0);
if ((ignorePropertyNames != null)
&& (ignorePropertyNames.Length != 0)) {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (!propertyInfo.CanRead
|| (Array.IndexOf(ignorePropertyNames, propertyInfo.Name) >= 0))
continue;
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
} else {
foreach (PropertyInfo propertyInfo in aObject.GetType()
.GetProperties(propertySelector)) {
if (propertyInfo.CanRead)
aSeed = aSeed.Hash(propertyInfo.GetValue(aObject));
}
}
return aSeed;
}
/// <summary>
/// NOTICE: this method is provided to contribute a <see cref="KeyValuePair{TKey,TValue}"/> to
/// the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
/// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on the Key or Value here if that itself is a KeyValuePair.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="keyValuePair">The value to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeyAndValue<TKey, TValue>(this int aSeed, KeyValuePair<TKey, TValue> keyValuePair)
=> aSeed.Hash(keyValuePair.Key)
.Hash(keyValuePair.Value);
/// <summary>
/// NOTICE: this method is provided to contribute a collection of <see cref="KeyValuePair{TKey,TValue}"/>
/// to the developing HashCode seed; by hashing the key and the value independently. HOWEVER,
/// this method has a different name since it will not be automatically invoked by
/// <see cref="Hash(int,object)"/>, <see cref="Hash(int,IEnumerable)"/>,
/// or <see cref="HashAllProperties"/> --- you MUST NOT mix this method with those unless
/// you are sure that no KeyValuePair instances will be passed to those methods; or otherwise
/// the generated hash code will not be consistent. This method itself ALSO will not invoke
/// this method on a Key or Value here if that itself is a KeyValuePair or an Enumerable of
/// KeyValuePair.
/// </summary>
/// <param name="aSeed">The developing HashCode value or seed.</param>
/// <param name="keyValuePairs">The values to contribute.</param>
/// <returns>The new hash code.</returns>
[MethodImpl(MethodImplOptions.AggressiveInlining)]
public static int HashKeysAndValues<TKey, TValue>(
this int aSeed,
IEnumerable<KeyValuePair<TKey, TValue>> keyValuePairs)
{
if (keyValuePairs == null)
return aSeed.Hash(null);
foreach (KeyValuePair<TKey, TValue> keyValuePair in keyValuePairs) {
aSeed = aSeed.HashKeyAndValue(keyValuePair);
}
return aSeed;
}
}
}
这是我的哈希码助手。它的优点是它使用泛型类型参数，因此不会导致装箱：
public static class HashHelper
{
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
return 31 * arg1.GetHashCode() + arg2.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
return 31 * hash + arg3.GetHashCode();
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3,
T4 arg4)
{
unchecked
{
int hash = arg1.GetHashCode();
hash = 31 * hash + arg2.GetHashCode();
hash = 31 * hash + arg3.GetHashCode();
return 31 * hash + arg4.GetHashCode();
}
}
public static int GetHashCode<T>(T[] list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
public static int GetHashCode<T>(IEnumerable<T> list)
{
unchecked
{
int hash = 0;
foreach (var item in list)
{
hash = 31 * hash + item.GetHashCode();
}
return hash;
}
}
/// <summary>
/// Gets a hashcode for a collection for that the order of items
/// does not matter.
/// So {1, 2, 3} and {3, 2, 1} will get same hash code.
/// </summary>
public static int GetHashCodeForOrderNoMatterCollection<T>(
IEnumerable<T> list)
{
unchecked
{
int hash = 0;
int count = 0;
foreach (var item in list)
{
hash += item.GetHashCode();
count++;
}
return 31 * hash + count.GetHashCode();
}
}
/// <summary>
/// Alternative way to get a hashcode is to use a fluent
/// interface like this:<br />
/// return 0.CombineHashCode(field1).CombineHashCode(field2).
/// CombineHashCode(field3);
/// </summary>
public static int CombineHashCode<T>(this int hashCode, T arg)
{
unchecked
{
return 31 * hashCode + arg.GetHashCode();
}
}
此外，它还具有扩展方法来提供流畅的界面，因此您可以这样使用它：
public override int GetHashCode()
{
return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}
或者像这样：
public override int GetHashCode()
{
return 0.CombineHashCode(Manufacturer)
.CombineHashCode(PartN)
.CombineHashCode(Quantity);
}
推荐文章
- 如何为构造函数定制Visual Studio的私有字段生成快捷方式?
- 为什么Visual Studio 2015/2017/2019测试运行器没有发现我的xUnit v2测试
- AppSettings从.config文件中获取值
- 如何检查IEnumerable是否为空或空?
- 没有ListBox。SelectionMode="None"，是否有其他方法禁用列表框中的选择?
- 在c#代码中设置WPF文本框的背景颜色
- HyperLogLog算法是如何工作的?
- 如何在iis7应用程序池中设置。net Framework 4.5版本
- 如何分裂()一个分隔字符串到一个列表<字符串>
- 如何指定最小值，但没有使用范围数据注释属性的最大小数?
- 递归执行广度优先搜索
- 如何在PowerShell中获得本地主机名?
- 为什么在Java和。net中不能修改字符串?
- 四舍五入到一个数字的最接近倍数
- 'throw'和'throw new Exception()'的区别
