在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
当前回答
这是我的哈希码助手。它的优点是它使用泛型类型参数,因此不会导致装箱:
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);
}
其他回答
使用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>
由于此特性,哈希代码不应在创建它们的应用程序域之外使用,也不应将其用作集合中的关键字段,也不应该持久化。
请在此处阅读更多信息。
加密安全?
算法不必是加密哈希函数。这意味着它不必满足以下条件:
生成生成给定哈希值的消息是不可行的。找到具有相同哈希值的两个不同消息是不可行的。对消息进行一次小的更改应该会对哈希值进行广泛的更改,以使新的哈希值看起来与旧的哈希值不相关(雪崩效应)。
这是我的简单方法。我使用的是经典的生成器模式。它是类型安全的(无装箱/拆箱),并且与.NET 2.0兼容(无扩展方法等)。
它的用法如下:
public override int GetHashCode()
{
HashBuilder b = new HashBuilder();
b.AddItems(this.member1, this.member2, this.member3);
return b.Result;
}
这里是实际的生成器类:
internal class HashBuilder
{
private const int Prime1 = 17;
private const int Prime2 = 23;
private int result = Prime1;
public HashBuilder()
{
}
public HashBuilder(int startHash)
{
this.result = startHash;
}
public int Result
{
get
{
return this.result;
}
}
public void AddItem<T>(T item)
{
unchecked
{
this.result = this.result * Prime2 + item.GetHashCode();
}
}
public void AddItems<T1, T2>(T1 item1, T2 item2)
{
this.AddItem(item1);
this.AddItem(item2);
}
public void AddItems<T1, T2, T3>(T1 item1, T2 item2, T3 item3)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
}
public void AddItems<T1, T2, T3, T4>(T1 item1, T2 item2, T3 item3,
T4 item4)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
}
public void AddItems<T1, T2, T3, T4, T5>(T1 item1, T2 item2, T3 item3,
T4 item4, T5 item5)
{
this.AddItem(item1);
this.AddItem(item2);
this.AddItem(item3);
this.AddItem(item4);
this.AddItem(item5);
}
public void AddItems<T>(params T[] items)
{
foreach (T item in items)
{
this.AddItem(item);
}
}
}
我的大部分工作都是通过数据库连接完成的,这意味着我的类都具有来自数据库的唯一标识符。我总是使用数据库中的ID来生成哈希代码。
// Unique ID from database
private int _id;
...
{
return _id.GetHashCode();
}
这是我的哈希码助手。它的优点是它使用泛型类型参数,因此不会导致装箱:
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);
}
与夜编码器的解决方案非常相似,只是如果你想提高素数更容易。
PS:这是你嘴里吐出一点东西的时候之一,因为你知道这可以用9个默认值重构成一个方法,但它会更慢,所以你闭上眼睛,试着忘掉它。
/// <summary>
/// Try not to look at the source code. It works. Just rely on it.
/// </summary>
public static class HashHelper
{
private const int PrimeOne = 17;
private const int PrimeTwo = 23;
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9, T10>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9, T10 arg10)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
hash = hash * PrimeTwo + arg10.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8, T9>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8, T9 arg9)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
hash = hash * PrimeTwo + arg9.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7, T8>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7, T8 arg8)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
hash = hash * PrimeTwo + arg8.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6, T7>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6, T7 arg7)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
hash = hash * PrimeTwo + arg7.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5, T6>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5, T6 arg6)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
hash = hash * PrimeTwo + arg6.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4, T5>(T1 arg1, T2 arg2, T3 arg3, T4 arg4, T5 arg5)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
hash = hash * PrimeTwo + arg5.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, T4 arg4)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
hash = hash * PrimeTwo + arg4.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
hash = hash * PrimeTwo + arg3.GetHashCode();
return hash;
}
}
public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
{
unchecked
{
int hash = PrimeOne;
hash = hash * PrimeTwo + arg1.GetHashCode();
hash = hash * PrimeTwo + arg2.GetHashCode();
return hash;
}
}
}