在.NET中,如果null的哈希码始终为零

Question

鉴于像System.Collections.Generic.HashSet<>accept 这样的集合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?)可以只取五个值,但其中两个,即null和Season.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(),其中,其哈希码我们所追求的目标是永远不能处理的情况null.

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

新编辑/附加:

现在我尝试了调试.有了HashSet<>,我可以确认使用默认的相等比较器,值Season.Spring和null 将在同一个桶中结束.这可以通过非常仔细地检查私有数组成员确定m_buckets和m_slots.请注意,索引始终按设计偏移一.

但是,我上面给出的代码并没有解决这个问题.事实证明,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;
  }
}

Answer 1

只要为null返回的哈希码对于类型是一致的,你应该没问题.对哈希码的唯一要求是两个被认为相等的对象共享相同的哈希码.

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

类似的问题:

空字段上的GetHashCode？

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

这个MSDN条目的"备注" 详细介绍了哈希码.尖锐,文档不提供任何覆盖或空值的讨论都 -甚至没有在社会上的内容.

要使用枚举解决您的问题,请重新实现哈希代码以返回非零,添加等效于null的默认"未知"枚举条目,或者只是不使用可为空的枚举.

顺便说一句有趣的发现.

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

碰撞本身并不一定是个问题,但你需要知道它们在那里.哈希码仅在某些情况下使用.正如MSDN上的文档所述,哈希代码不能保证为不同的对象返回不同的值,因此不应该这样做.

Answer 2

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

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

结果 - 使用零与一般情况下的任何其他值一样好.

当然,会有一些情况,比如你的枚举,这个零与真实值的哈希码共享.问题是,对于您来说,额外比较的微不足道的开销是否会导致问题.

如果是这样,那么为你的特定类型的nullable的情况定义你自己的比较器,并确保null值总是产生一个总是相同的哈希码(当然!)和一个不能由底层产生的值类型自己的哈希码算法.对于您自己的类型,这是可行的.对于其他人 - 祝你好运:)

Answer 3

它不具有为零 - 42,如果你想它,你可以做.

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

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

请注意,如果你使用类似的数字0xDEADBEEF,那么有人可能会说你正在使用一个神奇的数字...而你会有所帮助.(你可以说零也是一个神奇的数字,你会说得对...除了它被广泛使用,因为它有点像规则的例外.)