在.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);
}
其他回答
微软引领了几种哈希方法。。。
//for classes that contain a single int value
return this.value;
//for classes that contain multiple int value
return x ^ y;
//for classes that contain single number bigger than int
return ((int)value ^ (int)(value >> 32));
//for classes that contain class instance fields which inherit from object
return obj1.GetHashCode();
//for classes that contain multiple class instance fields which inherit from object
return obj1.GetHashCode() ^ obj2.GetHashCode() ^ obj3.GetHashCode();
我可以猜测,对于多个大整数,您可以使用这个:
int a=((int)value1 ^ (int)(value1 >> 32));
int b=((int)value2 ^ (int)(value2 >> 32));
int c=((int)value3 ^ (int)(value3 >> 32));
return a ^ b ^ c;
对于多类型也是如此:首先使用GetHashCode()将所有类型转换为int然后int值将被xor'ed,结果是您的哈希值。
对于那些使用哈希作为ID(我的意思是一个唯一的值)的人来说,哈希自然被限制在数字个数,我认为哈希算法是5个字节,至少是MD5。
您可以将多个值转换为哈希值,其中一些值是相同的,因此不要将其用作标识符。(也许有一天我会使用你的组件)
这是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,因为添加泛型参数也会添加装箱操作。
这是我的简单方法。我使用的是经典的生成器模式。它是类型安全的(无装箱/拆箱),并且与.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);
}
}
}
ValueTuple-C#7更新
正如@cactuaroid在评论中提到的,可以使用值元组。这节省了一些击键,更重要的是纯粹在堆栈上执行(无垃圾):
(PropA, PropB, PropC, PropD).GetHashCode();
(注意:使用匿名类型的原始技术似乎在堆上创建了一个对象,即垃圾,因为匿名类型被实现为类,尽管编译器可能会对此进行优化。对这些选项进行基准测试会很有趣,但元组选项应该更优。)
匿名类型(原始答案)
Microsoft已经提供了一个很好的通用HashCode生成器:只需将属性/字段值复制到匿名类型并对其进行哈希:
new { PropA, PropB, PropC, PropD }.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请求。