小编典典

为什么像这样实现ValueType.GetHashCode()?

c#

ValueType.cs

**操作:我们返回哈希码的算法有点复杂。我们看
**用于第一个非静态字段并获取其哈希码。如果类型没有
**非静态字段,我们返回该类型的哈希码。我们不能接受
**静态成员的哈希码,因为该成员的类型与 
**原始类型,我们将陷入无限循环。

今天,当我在字典中使用KeyValuePair作为键(它存储xml属性名称(枚举)和它的值(字符串))时,我对此颇为bit恼,并期望它具有基于其所有字段计算的哈希码,但根据实现,它仅考虑了关键部分。

示例(来自Linqpad的c / p):

void Main()
{
    var kvp1 = new KeyValuePair<string, string>("foo", "bar");
    var kvp2 = new KeyValuePair<string, string>("foo", "baz");

    // true
    (kvp1.GetHashCode() == kvp2.GetHashCode()).Dump();
}

我猜第一个非静态字段表示以声明顺序排列的第一个字段,当出于某种原因更改源中的变量顺序并认为它不会在语义上更改代码时,也会引起麻烦。


阅读 257

收藏
2020-05-19

共1个答案

小编典典

更新:此答案(部分地)是我撰写的博客文章GetHashcode的基础,该文章详细介绍了的设计特征。感谢您提出有趣的问题!


我没有实现它,也没有与实现它的人交谈。但我可以指出几件事。

(继续之前,请注意,这里我是专门讨论哈希码,目的是平衡哈希表,哈希表的内容由非敌对用户选择。数字签名,冗余校验或确保某些用户在对表提供程序发起拒绝服务攻击时确保哈希表的良好性能超出了本讨论的范围。)

首先,正如乔恩(Jon)正确指出的那样,给定算法确实实现了所需的GetHashCode约定。就您的目的而言,它可能不是最佳选择,但这是合法的。这是所有
需要 的是事情比较相等具有相等的散列码。

那么,除了合同之外,“拥有的东西”又是什么呢?良好的哈希码实现应为:

1)快。非常快!请记住,哈希代码的全部重点是要在哈希表中 快速
找到一个相对空的插槽。如果哈希码的O(1)计算实际上比天真地执行查找所需的O(n)速度慢,则哈希码解决方案就是净损失。

2)对于给定的输入分布,在32位整数的空间中分布良好。整数上的分布越差,哈希表将变得更像是朴素的线性查找。

那么,考虑到这两个 相互冲突的 目标,您如何针对任意值类型创建哈希算法?任何时候花在确保良好分布的复杂哈希算法上的时间都是浪费的时间。

一个常见的建议是“先对所有字段进行哈希处理,然后对所得的哈希码进行异或”。但这就是问题所在。对两个32位int进行XOR运算时,只有当输入本身分布得非常好并且彼此不相关时才可以分配良好,这是不太可能的情况:

// (Updated example based on good comment!)
struct Control
{
    string name;
    int x;
    int y;
}

x和y在32位整数的整个范围内分布良好的可能性是什么?非常低。它们 很小 而且 彼此靠近的
可能性会好得多,在这种情况下,将它们的哈希码进行异或处理会使情况 变得更糟 ,而不是 更好 。将彼此接近的整数异或在一起,将大多数位清零。

此外,这是字段数的O(n)!具有许多小字段的值类型将花费相对较长的时间来计算哈希码。

基本上,我们所处的情况是用户自己没有提供哈希代码实现;他们不在乎,或者他们不希望将此类型用作哈希表中的键。假设您 没有 关于类型的 语义信息
,那么最好的办法是什么?最好的办法就是快,并在大多数时候给出良好的结果。

在大多数情况下,两个不同的结构实例将在它们的 大多数 字段中有所不同,而不仅仅是它们的 一个
字段,因此仅选择其中一个并希望它是一个不同的实例似乎是合理的。

在大多数情况下,两个不同的结构实例在其字段中将具有一定的冗余性,因此将多个字段的哈希值组合在一起可能会减少而不是增加哈希值中的熵,即使它消耗了以下时间:哈希算法旨在保存。

将此与C#中的匿名类型设计进行比较。对于匿名类型,我们 确实 知道很可能将类型用作表的键。我们 确实
知道,匿名类型实例之间极有可能存在冗余(因为它们是笛卡尔积或其他联接的结果)。因此,我们确实将所有字段的哈希码合并为一个哈希码。如果由于计算的哈希码过多而导致性能不佳,则可以自由使用自定义标称类型而不是匿名类型。

2020-05-19