题
怎么默认的行为 GetHashCode()
工作?并且它处理结构、类阵列,等等。有效和足够好?
我试图决定在什么情况下我应该包我自己和在什么情况下我可以放心地依赖默认实施以做的很好。我不想要重新发明轮子,如果在所有可能的。
解决方案
namespace System {
public class Object {
[MethodImpl(MethodImplOptions.InternalCall)]
internal static extern int InternalGetHashCode(object obj);
public virtual int GetHashCode() {
return InternalGetHashCode(this);
}
}
}
<强> InternalGetHashCode 强>被映射到的 ObjectNative :: GetHashCode的强>在CLR中,它看起来像这样的功能:
FCIMPL1(INT32, ObjectNative::GetHashCode, Object* obj) {
CONTRACTL
{
THROWS;
DISABLED(GC_NOTRIGGER);
INJECT_FAULT(FCThrow(kOutOfMemoryException););
MODE_COOPERATIVE;
SO_TOLERANT;
}
CONTRACTL_END;
VALIDATEOBJECTREF(obj);
DWORD idx = 0;
if (obj == 0)
return 0;
OBJECTREF objRef(obj);
HELPER_METHOD_FRAME_BEGIN_RET_1(objRef); // Set up a frame
idx = GetHashCodeEx(OBJECTREFToObject(objRef));
HELPER_METHOD_FRAME_END();
return idx;
}
FCIMPLEND
在全面实施的 GetHashCodeEx 是相当大的,所以它更容易只是链接到的 C ++源代码。
其他提示
对于类来说,默认值本质上是引用相等,这通常没问题。如果编写一个结构体,则更常见的是覆盖相等性(尤其是为了避免装箱),但无论如何编写结构体的情况都很少!
当覆盖相等性时,您应该始终有一个匹配的 Equals()
和 GetHashCode()
(IE。对于两个值,如果 Equals()
返回 true 他们 必须 返回相同的哈希码,但相反的是 不是 必需) - 通常还提供 ==
/!=
运营商,并经常实施 IEquatable<T>
也。
为了生成哈希码,通常使用因子和,因为这可以避免配对值的冲突 - 例如,对于基本的 2 字段哈希:
unchecked // disable overflow, for the unlikely possibility that you
{ // are compiling with overflow-checking enabled
int hash = 27;
hash = (13 * hash) + field1.GetHashCode();
hash = (13 * hash) + field2.GetHashCode();
return hash;
}
这样做的优点是:
- {1,2} 的哈希值与 {2,1} 的哈希值不同
- {1,1} 的哈希值与 {2,2} 的哈希值不同
等等 - 如果仅使用未加权的总和或异或(^
), ETC。
该文件 GetHashCode
方法 对象 说的 "默认这种方法的实施必须不被用来作为一个独特的目标识符的散列的目的。" 和一个 ValueType 说的 "如果你打电话的源类型的GetHashCode方法,返回值可能不适用于作为一个关键在哈希表"。.
基本数据类型的喜欢 byte
, short
, int
, long
, char
和 string
实施一个良好的GetHashCode方法。其他一些课程和结构,就像 Point
例如,实施一个 GetHashCode
方法,可能会或可能不适合特定需求。你只需要尝试,看看它是否足够好。
文件每一类或结构可以告诉你如果它复盖默认的实现或没有。如果它不能替代它,你应该用你自己的执行。对于任何类或结构创建自己在这里你需要用的 GetHashCode
方法,应该使自己的实施使用适当的成员来计算的散列码。
因为我找不到解释 为什么的:我们应该重写自定义结构GetHashCode
和Equals
和 为什么的<答案/ STRONG>的默认实现“不可能适合用作哈希表中的关键字”,我会留下一个链接到的这个博客帖子,这就解释了为什么有问题的真实案例即发生了。
我建议在阅读整个柱,但这里是一个摘要(强调和澄清)。
原因结构默认散列是缓慢的,不太好:
在帖子中描述的CLR被设计的方式,在每一个部件中的呼叫或
System.ValueType
类型System.Enum
定义[可]导致的拳击分配强> [...]的哈希函数的实施者面临的困境:使散列函数的良好分布或使之快。在某些情况下,有可能实现他们两个,但它是很难做到这一点一般在
ValueType.GetHashCode
。struct的典型的散列函数“结合”的所有字段的散列码。但要获得一个字段的散列码在
ValueType
方法的唯一方法是为使用反射即可。因此,CLR笔者决定在分配和默认GetHashCode
版本的交易速度只是返回第一个非空场的哈希码并“munges”它与一个类型ID [...]这是一种合理的行为,除非它不是。例如,如果你够倒霉的和你的结构的第一个字段为大多数情况下,相同的值,则哈希函数将提供相同的结果所有的时间。而且,正如你可以想像,这样会导致剧烈的性能影响,如果这些实例存储在一个哈希集合或哈希表。[...]的基于反射的实现是慢即可。很慢。
[...]两者
ValueType.Equals
和ValueType.GetHashCode
有一个特殊的优化。如果一个类型不具有“指针”和包装妥当[...]则更为优化的版本被使用:在4个字节和GetHashCode
方法的实例,并且异或块Equals
迭代比较了使用memcmp
两个实例。 [...]但是优化是非常棘手的。首先,它是很难被启用优化时,需要了解[...]其次,内存比较不一定给你正确的结果。下面是一个简单的例子:[...]-0.0
和+0.0
相等,但是具有不同的二进制表示
现实世界中的问题:
private readonly HashSet<(ErrorLocation, int)> _locationsWithHitCount;
readonly struct ErrorLocation
{
// Empty almost all the time
public string OptionalDescription { get; }
public string Path { get; }
public int Position { get; }
}
我们使用含有默认平等实现自定义结构的元组。和不幸的是,该结构有一个任选的第一字段,它几乎总是等于[空字符串] 即可。的表现还行,直到集合中元素的数量增加显著造成一个真正的性能问题,以分钟来初始化集合的项目数以万计。
因此,要回答“在什么情况下,我应该收拾我自己和在什么情况下,我可以放心地依靠默认的实现”的问题,至少在案件的结构的,你应该重写Equals
和GetHashCode
时,您的自定义的结构可能会被用作一个哈希表或Dictionary
的关键。结果
我还建议在这种情况下执行IEquatable<T>
,避免拳击。
至于其他的答案说,如果你正在写一个的类的使用参考平等默认哈希通常是罚款,所以我不会在这种情况下麻烦了,除非你需要重写Equals
(那么你就必须相应地重写GetHashCode
)。
一般来说,如果你忽略equals,要重写GetHashCode。这样做的原因是因为两者都是用来比较的类/结构的平等。
等于检查当使用 FOO A,B;
如果(A == B)
由于我们知道指针没有可能匹配,我们可以比较的内部构件。
Equals(obj o)
{
if (o == null) return false;
MyType Foo = o as MyType;
if (Foo == null) return false;
if (Foo.Prop1 != this.Prop1) return false;
return Foo.Prop2 == this.Prop2;
}
的GetHashCode一般是用哈希表。由你的类生成的哈希码应始终是相同的一类给状态。
我通常做的,
GetHashCode()
{
int HashCode = this.GetType().ToString().GetHashCode();
HashCode ^= this.Prop1.GetHashCode();
etc.
return HashCode;
}
有人会说,哈希码只应每一次对象的生命周期来计算,但我不同意这一点(我可能是错的)。
使用对象提供的默认实现,除非你有相同的参考你的类之一,他们不会彼此相等。通过重写的Equals和GetHashCode,可以基于内部值,而不是物体的参考报告平等。
如果你只是处理波苏斯您可以使用此工具在一定程度上简化你的生活:
var hash = HashCodeUtil.GetHashCode(
poco.Field1,
poco.Field2,
...,
poco.FieldN);
...
public static class HashCodeUtil
{
public static int GetHashCode(params object[] objects)
{
int hash = 13;
foreach (var obj in objects)
{
hash = (hash * 7) + (!ReferenceEquals(null, obj) ? obj.GetHashCode() : 0);
}
return hash;
}
}