在.NET中,null的哈希码是否应始终为零?

90

鉴于像 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的作者确实在Nullable<>结构中重写了GetHashCode(),这是相关的。)用户编写的无参GetHashCode()实现永远无法处理我们寻找其哈希码的对象为null的情况。

这段内容是关于实现抽象方法EqualityComparer<T>.GetHashCode(T)或者实现接口方法IEqualityComparer<T>.GetHashCode(T)。在创建到MSDN的链接时,我发现它们说如果它们的唯一参数是null,那么这些方法会抛出一个ArgumentNullException。这肯定是MSDN上的一个错误吧?.NET自己的所有实现都不会抛出异常。在这种情况下抛出异常将有效地破坏任何尝试向HashSet<>添加null的尝试。除非HashSet<>在处理null项时做了一些特殊的处理(我将进行测试)。

新增编辑/补充:

现在我尝试进行调试。使用HashSet<>,我可以确认在默认的相等比较器下,值Season.Springnull将会位于同一个桶中。这可以通过仔细检查私有数组成员m_bucketsm_slots来确定。请注意,索引总是按设计偏移了一个。
然而,我上面提供的代码并没有解决这个问题。事实证明,当值为null时,HashSet<>甚至不会询问相等比较器。这是从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;
  }
}

26
为什么空值的哈希码不应该是零?哈希冲突并不是世界末日,你知道的。 - Hot Licks
3
除了这是一个众所周知,相当普遍的冲突之外,它并不是糟糕甚至不是一个非常严重的问题,只是很容易避免。 - Chris Pfohl
8
为什么我会想到“如果.NET框架跳下桥,你会跟着它跳吗”? - Adam Houldsworth
3
只是出于好奇,什么是“null season”? - SwDevMan81
1
对于第一部分,我们还注意到,不出所料,System.Runtime.CompilerServices.RuntimeHelpers.GetHashCode(null) 也会返回 0 - Jeppe Stig Nielsen
显示剩余11条评论
9个回答

27
只要对于该类型返回的空值的哈希码是一致的,那么就可以了。哈希码的唯一要求是被认为相等的两个对象共享相同的哈希码。
返回0或-1作为null的哈希码,只要您选择一个并始终返回它,就可以工作。显然,非空哈希码不应返回用于null的任何值。
类似问题: 在null字段上调用GetHashCode? 当对象的标识符为空时,GetHashCode应该返回什么?MSDN条目的“备注”更详细地讨论了哈希码。值得注意的是,文档根本没有提供有关null值的任何覆盖范围或讨论,甚至没有社区内容。
为了解决枚举问题,可以重新实现哈希码以返回非零值,添加一个默认的“未知”枚举条目等同于null,或者简单地不使用可空枚举。
顺便说一句,这是一个有趣的发现。
我看到的另一个问题是,哈希码无法表示可为空的4字节或更大类型而不发生至少一个碰撞(随着类型大小的增加,会发生更多碰撞)。例如,int的哈希码只是int本身,因此它使用整个int范围。在该范围内选择哪个值为null?无论你选择哪个值,都会与该值的哈希码本身发生碰撞。
碰撞本身并不一定是问题,但你需要知道它们的存在。哈希码仅在某些情况下使用。如MSDN文档所述,哈希码不能保证为不同对象返回不同的值,因此不应期望如此。

我认为你提供的问题并不完全相似。当你在自己的类(或结构体)中重写Object.GetHashCode()时,你知道只有当人们实际拥有你的类的实例时才会触发这段代码。该实例不能为null。这就是为什么你不会以if (this == null) return -1;开始覆盖Object.GetHashCode()的原因。"为null"和"拥有一些字段为null的对象"之间存在区别。 - Jeppe Stig Nielsen
你说:“显然,非空哈希码不应返回您用于 null 的任何值。” 我同意这是理想情况。这也是我首先提出问题的原因,因为每当我们编写一个枚举“T”时,(T?)null(T?)default(T) 将具有相同的哈希码(在当前 .NET 实现中)。如果 .NET 的实现者更改了 null 的哈希码 System.Enum 的哈希码算法,则可以更改此行为。 - Jeppe Stig Nielsen
我同意链接是针对空内部字段的。您提到它是为IEqualityComparer<T>,在您的实现中哈希码仍然特定于类型,因此您仍处于相同的情况,即类型一致性。对于任何类型的null返回相同的哈希码并不重要,因为nulls没有类型。 - Adam Houldsworth
1
注意:我已经两次更新了我的问题。结果发现(至少在HashSet<>中)更改null的哈希码是行不通的。 - Jeppe Stig Nielsen

6

它不一定要是零 -- 如果你想的话,你可以将其设为42。

在程序执行期间,一致性才是最重要的。

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

请注意,如果你使用像0xDEADBEEF这样的数字,那么有人可能会说你正在使用一个魔数... 事实上你确实是这样做了。(你也可以说零是一个魔数,而且你也没错... 只不过它被广泛使用,成为规则的例外。)


6
请记住,哈希码仅用作确定相等性的第一步,而且绝不能作为确定两个对象是否相等的实际标准。如果两个对象的哈希码不相等,则将它们视为不相等(因为我们假定底层实现是正确的,即我们不会推测这一点)。如果它们具有相同的哈希码,则应检查它们是否实际相等,对于你的情况而言,null 值和枚举值都将失败。因此,在通常情况下,使用零和其他任何值一样好。当然,会出现像你的枚举一样的情况,其中这个零值与一个实际值的哈希码共享。问题在于,对于你来说,额外比较的微不足道的开销是否会导致问题。如果是这样,请为可为空的特定类型定义自己的比较器,并确保 null 值始终产生相同的哈希码(当然!)并且该值不可能被底层类型自己的哈希码算法生成。对于你自己的类型,这是可以实现的。对于其他类型,祝好运 :)

4
好问题。
我刚试着编写了这个:

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

并且像这样执行:

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

它返回null

如果我使用普通的语句,而不是...

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

如果按预期 0 被返回,或者如果我们避免对 int 进行转换,只返回简单的 Spring

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

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

编辑

来自MSDN

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

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

再次来自MSDN:

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


6
根据定义,"collision" 意味着两个不同的对象具有相同的哈希码。您已经证明这些对象是不同的。那么它们是否具有相同的哈希码?根据原始问题所说,它们确实具有相同的哈希码,这意味着这是一种碰撞情况。发生碰撞并不是世界末日,只是比如果 "null" 哈希到 0 以外的某个值更可能出现碰撞,从而影响性能。 - Servy
1
那么你的回答实际上是什么意思呢?你说Season.Spring不等于null。嗯,这并没有错,但它并没有真正回答问题,不是吗? - Servy
2
@Servy:问题是这样说的:为什么我有两个不同对象(null和Spring)具有相同的哈希码。所以答案是,即使具有相同的哈希码,它们也不相等,因此没有发生冲突。顺便说一下。 - Tigran
3
回答:为什么不?嗯,楼主已经预先回答了你的“为什么不”的问题。选择0比选择其他数更容易导致冲突。他想知道为什么选择0,目前还没有人回答他这个问题。 - Servy
1
这个答案并没有包含任何OP不知道的内容,从提问的方式可以看出来。 - Konrad Rudolph
显示剩余12条评论

4
但是,为什么空值的哈希码应该是0呢?
它本来可以是任何值。我倾向于认为0并不一定是最好的选择,但这可能会导致最少的错误。
哈希函数绝对必须为相同的值返回相同的哈希值。一旦存在一个组件能够做到这一点,这就是空值哈希的唯一有效值。如果有一个常量,比如object.HashOfNull,那么实现IEqualityComparer的人就必须知道使用该值。如果他们没有考虑到这一点,他们使用0的机会略高于其他值。
至少对于HashSet<>而言,甚至无法更改空值的哈希值。
如上所述,我认为这完全不可能,因为已经存在遵循空值哈希为0约定的类型。

当一个人为某个特定类型T实现方法EqualityComparer<T>.GetHashCode(T)时,如果该类型允许null,那么当参数为null时,就必须做一些事情。你可以选择(1)抛出ArgumentNullException、(2)返回0或者(3)返回其他值。我理解你的回答是建议在这种情况下始终返回0 - Jeppe Stig Nielsen
@JeppeStigNielsen 我不确定是使用 throw 还是 return,但如果你选择 return 的话,那么一定是零。 - Roman Starkov

2
为了简单起见,它的值为0。没有强制性的要求。您只需要确保散列编码的一般要求即可。
例如,您需要确保如果两个对象相等,则它们的哈希码必须始终相等。因此,不同的哈希码必须始终表示不同的对象(但反之则不一定成立:即使两个不同的对象具有相同的哈希码,但如果这种情况经常发生,则说明这不是一个良好的哈希函数——它没有很好的碰撞抵抗能力)。
当然,我将我的答案限制在数学性质的要求上。还有.NET特定的技术条件,您可以在这里阅读到。对于空值来说,它的值不是0。

1

可以通过使用一个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

那么,每个季节都会有独特的哈希码值。


1
是的,但这实际上并没有回答问题。按照问题的描述,null将与Uknown相冲突。有什么区别? - Tigran
@Tigran - 这个版本不使用可空类型。 - SwDevMan81
我明白了,但问题是关于可空类型的。 - Tigran
我在 Stack Overflow 上看到过很多次人们将改进建议作为答案提供。 - SwDevMan81

1

个人而言,我觉得使用可空值有点棘手,尽可能避免使用。你的问题只是另一个原因。有时它们非常方便,但我的经验法则是,如果可能的话,不要混合值类型和 null,因为它们来自两个不同的世界。在 .NET 框架中,它们似乎做了相同的事情 - 很多值类型提供了 TryParse 方法,这是一种将值与无值 (null) 分离的方法。

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

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

当然,对于其他类型,比如int,你无法扩展值域,并且将其中一个值命名为特殊并不总是可行的。但是,对于int?,哈希码冲突问题要小得多,甚至可能不存在。

当你说“boxing”时,我认为你的意思是“wrapping”,即将一个结构值放入Nullable<>结构中(其中HasValue成员将被设置为true)。你确定问题用int?确实更小吗?很多时候我们只使用几个int值,这等同于一个枚举(理论上可以有许多成员)。 - Jeppe Stig Nielsen
通常情况下,当需要有限数量的已知值(2-10)时,我们会选择枚举类型。如果限制更大或没有限制,则使用 int 更合适。当然,个人偏好因人而异。 - Maciej

0
Tuple.Create( (object) null! ).GetHashCode() // 0
Tuple.Create( 0 ).GetHashCode() // 0
Tuple.Create( 1 ).GetHashCode() // 1
Tuple.Create( 2 ).GetHashCode() // 2

1
这是一个有趣的方法。如果您能编辑答案并加入一些额外的解释,尤其是考虑到问题的性质,那将会非常有用。 - Jeremy Caney

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接