89

鉴于像System.Collections.Generic.HashSet<>接受null作为集合成员这样的集合,人们可以询问哈希码null应该是什么。看起来框架使用0

// nullable struct type
int? i = null;
i.GetHashCode();  // gives 0
EqualityComparer<int?>.Default.GetHashCode(i);  // gives 0

// class type
CultureInfo c = null;
EqualityComparer<CultureInfo>.Default.GetHashCode(c);  // gives 0

对于可为空的枚举,这可能(有点)问题。如果我们定义

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

那么Nullable<Season>(也称为Season?)只能取五个值,但其中两个,即nullSeason.Spring,具有相同的哈希码。

像这样写一个“更好”的相等比较器是很诱人的:

class NewNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? Default.GetHashCode(x) : -1;
  }
}

但是有什么理由为什么null应该是的哈希码0

编辑/添加:

有些人似乎认为这是关于压倒一切Object.GetHashCode()的。事实上,事实并非如此。(.NET 的作者确实GetHashCode()Nullable<>结构中覆盖了GetHashCode()(不过, .NET在相关null

这是关于实现抽象方法EqualityComparer<T>.GetHashCode(T)或以其他方式实现接口方法IEqualityComparer<T>.GetHashCode(T)。现在,在创建这些指向 MSDN 的链接时,我看到它在那里说这些方法会抛出一个ArgumentNullExceptionif 它们的唯一参数是null. 这肯定是MSDN上的一个错误?.NET 自己的实现都不会引发异常。在这种情况下投掷将有效地破坏任何添加nullHashSet<>. 除非HashSet<>在处理一个null项目时做了一些特别的事情(我将不得不对此进行测试)。

新编辑/添加:

现在我尝试调试。使用HashSet<>,我可以确认使用默认的相等比较器,值Season.Springnull 在同一个存储桶中结束。这可以通过非常仔细地检查私有数组成员来确定m_bucketsm_slots. 请注意,根据设计,索引始终偏移 1。

然而,我上面给出的代码并没有解决这个问题。事实证明,HashSet<>当值为 . 时,甚至永远不会询问相等比较器null。这是来自的源代码HashSet<>

    // Workaround Comparers that throw ArgumentNullException for GetHashCode(null).
    private int InternalGetHashCode(T item) {
        if (item == null) { 
            return 0;
        } 
        return m_comparer.GetHashCode(item) & Lower31BitMask; 
    }

这意味着,至少对于 来说HashSet<>,甚至不可能更改 的哈希值null相反,一个解决方案是更改所有其他值的哈希,如下所示:

class NewerNullEnumEqComp<T> : EqualityComparer<T?> where T : struct
{
  public override bool Equals(T? x, T? y)
  {
    return Default.Equals(x, y);
  }
  public override int GetHashCode(T? x)
  {
    return x.HasValue ? 1 + Default.GetHashCode(x) : /* not seen by HashSet: */ 0;
  }
}
4

9 回答 9

25

只要为空值返回的哈希码与类型一致,就可以了。哈希码的唯一要求是被认为相等的两个对象共享相同的哈希码。

为 null 返回 0 或 -1,只要您选择一个并一直返回它,就可以了。显然,非空哈希码不应该返回您用于空的任何值。

类似的问题:

空字段上的GetHashCode?

当对象的标识符为空时,GetHashCode 应该返回什么?

此MSDN 条目的“备注”围绕哈希码进行了更详细的说明。令人痛心的是,该文档根本没有提供任何关于空值报道或讨论——甚至在社区内容中也没有。

要解决您的枚举问题,要么重新实现哈希码以返回非零,添加一个默认的“未知”枚举条目,相当于 null,或者干脆不使用可为空的枚举。

顺便说一句,有趣的发现。

我通常看到的另一个问题是哈希码不能表示一个 4 字节或更大的类型,该类型在没有至少一次冲突的情况下可以为空(随着类型大小的增加更多)。例如,一个 int 的哈希码就是 int,所以它使用整个 int 范围。您为 null 选择该范围内的什么值?无论您选择什么,都会与值的哈希码本身发生冲突。

碰撞本身并不一定是问题,但您需要知道它们的存在。哈希码仅在某些情况下使用。正如 MSDN 上的文档中所述,不保证哈希码会为不同的对象返回不同的值,因此不应期望如此。

于 2012-05-23T15:50:15.740 回答
6

它不一定——如果你愿意,你可以把它设为 42。

重要的是程序执行期间的一致性。

这只是最明显的表示,因为null通常在内部表示为零。这意味着,在调试时,如果您看到哈希码为零,它可能会提示您:“嗯……这是一个空引用问题吗?”

请注意,如果您使用类似 的数字0xDEADBEEF,那么有人可能会说您使用的是幻数……您会这样。(你也可以说零也是一个神奇的数字,而且你是对的……只是它被广泛使用,以至于在某种程度上是规则的例外。)

于 2012-05-23T16:15:43.143 回答
6

请记住,哈希码仅用作确定相等性的第一步,并且[是/应该]永远不要(被)用作关于两个对象是否相等的事实上的确定。

如果两个对象的哈希码不相等,那么它们将被视为不相等(因为我们假设不正确的实现是正确的 - 即我们不会事后猜测)。如果它们具有相同的哈希码,则应检查它们的实际相等性,在您的情况下,null枚举值将失败。

结果 - 在一般情况下,使用零与任何其他值一样好。

当然,在某些情况下,例如您的枚举,此零与实际值的哈希码共享。问题是,对您来说,额外比较的微小开销是否会导致问题。

如果是这样,那么为您的特定类型的可为空的情况定义您自己的比较器,并确保空值始终产生始终相同的哈希码(当然!)底层无法产生的值类型自己的哈希码算法。对于您自己的类型,这是可行的。对于其他人-祝你好运:)

于 2012-05-24T09:02:21.320 回答
4

但是为什么 null 的哈希码应该为 0 有什么原因吗?

它本来可以是任何东西。我倾向于同意 0 不一定是最佳选择,但它可能会导致最少的错误。

散列函数绝对必须为相同的值返回相同的散列。一旦存在执行此操作组件,这实际上是 .h 的哈希的唯一有效值null。如果对此有一个常数,例如 hm, object.HashOfNull,那么实现 an 的IEqualityComparer人必须知道使用该值。我认为,如果他们不考虑这一点,他们使用 0 的机会会略高于其他所有值。

至少对于HashSet<>,甚至不可能改变null的hash

如上所述,我认为完全不可能完全停止,因为存在已经遵循 null 哈希为 0 的约定的类型。

于 2012-06-12T13:29:47.737 回答
4

好问题。

我只是尝试编写此代码:

enum Season
{
  Spring,
  Summer,
  Autumn,
  Winter,
}

并像这样执行:

Season? v = null;
Console.WriteLine(v);

它返回null

如果我这样做,而不是正常

Season? v = Season.Spring;
Console.WriteLine((int)v);

如果我们避免强制0转换int.

所以..如果您执行以下操作:

Season? v = Season.Spring;  
Season? vnull = null;   
if(vnull == v) // never TRUE

编辑

来自MSDN

如果两个对象比较相等,则每个对象的 GetHashCode 方法必须返回相同的值。但是,如果两个对象比较不相等,则两个对象的 GetHashCode 方法不必返回不同的值

换句话说:如果两个对象具有相同的哈希码,但这并不意味着它们相等,因为 真正的相等性由Equals确定。

再次来自 MSDN:

只要确定对象的 Equals 方法的返回值的对象状态没有修改,对象的 GetHashCode 方法就必须始终返回相同的哈希码。请注意,这仅适用于应用程序的当前执行,并且如果再次运行应用程序,则可以返回不同的哈希码。

于 2012-05-23T15:50:02.907 回答
2

为简单起见,它为 0。没有这么硬的要求。您只需要保证哈希编码的一般要求。

例如,您需要确保如果两个对象相等,则它们的哈希码也必须始终相等。因此,不同的哈希码必须始终代表不同的对象(但反之亦然:两个不同的对象可能具有相同的哈希码,即使这种情况经常发生,那么这也不是一个高质量的哈希函数——它没有良好的抗碰撞性)。

当然,我的回答仅限于数学性质的要求。还有 .NET 特定的技术条件,您可以在此处阅读。0 表示空值不在其中。

于 2012-05-23T15:54:09.157 回答
1

就我个人而言,我发现使用可空值有点尴尬,并尽可能避免使用它们。你的问题只是另一个原因。虽然有时它们非常方便,但我的经验法则是尽可能不要将值类型与 null 混合,因为它们来自两个不同的世界。在 .NET 框架中,它们似乎做同样的事情 - 许多值类型提供TryParse方法,这是一种将值与无值 ( null) 分离的方法。

在您的特定情况下,很容易摆脱问题,因为您处理自己的Season类型。

(Season?)null对我来说意味着“未指定季节”,例如当您有一个不需要某些字段的网络表单时。在我看来,最好在本身中指定特殊的“价值”,enum而不是使用有点笨重的Nullable<T>。它会更快(没有装箱)更容易阅读(Season.NotSpecifiedvs null),并将解决您的哈希码问题。

当然,对于其他类型,例如int您不能扩展值域并将其中一个值命名为特殊值并不总是可行的。但是int?,如果有的话,哈希码冲突的问题要小得多。

于 2012-05-29T19:24:19.713 回答
1

所以这可以通过使用枚举值来避免(尽管 a未知Unknown似乎有点奇怪)。Season所以这样的事情会否定这个问题:

public enum Season
{
   Unknown = 0,
   Spring,
   Summer,
   Autumn,
   Winter
}

Season some_season = Season.Unknown;
int code = some_season.GetHashCode(); // 0
some_season = Season.Autumn;
code = some_season.GetHashCode(); // 3

然后,您将拥有每个季节的唯一哈希码值。

于 2012-05-23T16:06:09.327 回答
0
Tuple.Create( (object) null! ).GetHashCode() // 0
Tuple.Create( 0 ).GetHashCode() // 0
Tuple.Create( 1 ).GetHashCode() // 1
Tuple.Create( 2 ).GetHashCode() // 2
于 2020-06-06T18:55:19.350 回答