在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
在.NET中,GetHashCode方法在整个.NET基类库的许多地方都使用。正确执行它对于在集合中或确定相等时快速查找项目尤为重要。
对于如何为自定义类实现GetHashCode,是否有标准算法或最佳实践,以便不会降低性能?
当前回答
这是我使用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请求。
其他回答
ReSharper用户可以使用ReSharper->Edit->generate Code->Equality Members生成GetHashCode、Equals等。
// ReSharper's GetHashCode looks like this
public override int GetHashCode() {
unchecked {
int hashCode = Id;
hashCode = (hashCode * 397) ^ IntMember;
hashCode = (hashCode * 397) ^ OtherIntMember;
hashCode = (hashCode * 397) ^ (RefMember != null ? RefMember.GetHashCode() : 0);
// ...
return hashCode;
}
}
这是Jon Skeet发布的上述算法的另一个流畅实现,但不包括分配或装箱操作:
public static class Hash
{
public const int Base = 17;
public static int HashObject(this int hash, object obj)
{
unchecked { return hash * 23 + (obj == null ? 0 : obj.GetHashCode()); }
}
public static int HashValue<T>(this int hash, T value)
where T : struct
{
unchecked { return hash * 23 + value.GetHashCode(); }
}
}
用法:
public class MyType<T>
{
public string Name { get; set; }
public string Description { get; set; }
public int Value { get; set; }
public IEnumerable<T> Children { get; set; }
public override int GetHashCode()
{
return Hash.Base
.HashObject(this.Name)
.HashObject(this.Description)
.HashValue(this.Value)
.HashObject(this.Children);
}
}
由于泛型类型约束,编译器将确保不使用类调用HashValue。但是没有编译器支持HashObject,因为添加泛型参数也会添加装箱操作。
这是一个很好的例子:
/// <summary>
/// Helper class for generating hash codes suitable
/// for use in hashing algorithms and data structures like a hash table.
/// </summary>
public static class HashCodeHelper
{
private static int GetHashCodeInternal(int key1, int key2)
{
unchecked
{
var num = 0x7e53a269;
num = (-1521134295 * num) + key1;
num += (num << 10);
num ^= (num >> 6);
num = ((-1521134295 * num) + key2);
num += (num << 10);
num ^= (num >> 6);
return num;
}
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="arr">An array of objects used for generating the
/// hash code.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode(params object[] arr)
{
int hash = 0;
foreach (var item in arr)
hash = GetHashCodeInternal(hash, item.GetHashCode());
return hash;
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <param name="obj3">The third object.</param>
/// <param name="obj4">The fourth object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and
/// data structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
T4 obj4)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <param name="obj3">The third object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
{
return GetHashCode(obj1, GetHashCode(obj2, obj3));
}
/// <summary>
/// Returns a hash code for the specified objects
/// </summary>
/// <param name="obj1">The first object.</param>
/// <param name="obj2">The second object.</param>
/// <returns>
/// A hash code, suitable for use in hashing algorithms and data
/// structures like a hash table.
/// </returns>
public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
{
return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
}
}
下面是如何使用它:
private struct Key
{
private Type _type;
private string _field;
public Type Type { get { return _type; } }
public string Field { get { return _field; } }
public Key(Type type, string field)
{
_type = type;
_field = field;
}
public override int GetHashCode()
{
return HashCodeHelper.GetHashCode(_field, _type);
}
public override bool Equals(object obj)
{
if (!(obj is Key))
return false;
var tf = (Key)obj;
return tf._field.Equals(_field) && tf._type.Equals(_type);
}
}
如果我们的财产不超过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更具性能。另一方面,这是内部的,所以我们必须复制代码,牺牲了我们在这里获得的大部分。此外,我们将负责记住首先与随机种子结合。我不知道如果我们跳过这一步会有什么后果。
在Equals()比较多个字段的大多数情况下,GetHash()对一个字段或多个字段进行散列并不重要。您只需确保计算哈希值非常便宜(请不要分配)和快速(没有繁重的计算,当然也没有数据库连接),并提供良好的分布。
重型起吊应是Equals()方法的一部分;哈希应该是一个非常便宜的操作,以便能够对尽可能少的项目调用Equal()。
最后一个提示:不要依赖GetHashCode()在多个应用程序运行中保持稳定。许多.Net类型不能保证它们的哈希代码在重新启动后保持不变,因此只能对内存中的数据结构使用GetHashCode()的值。