对于DateRange类,什么是好的哈希代码?

它取决于我期望看到的值。

如果它最常具有不同的日值,而不是同一天的不同时间,并且它们在现在的一个世纪内,我会使用:

unchecked
{
    int hash = startDate.Year + endDate.Year - 4007;
    hash *= 367 + startDate.DayOfYear;
    return hash * 367 + endDate.DayOfYear;
}

这样可以很好地按预期值分配位,同时减少移位中丢失的位的数量。请注意,虽然在某些情况下,对素数的依赖性在碰撞时会非常糟糕(特别是当散列被送入某个使用相同素数模的对象中以避免在生成更小的散列并在其桶中分布时发生碰撞时),但我选择了在更明显的选择之上使用素数,因为它们只是上面,对于位分布来说仍然相当“紧”。我不太担心使用同一个素数两次,因为它们在这种方式下是如此的“紧”,但是如果您有一个基于哈希的集合,它有367个桶,那么它确实会受到伤害。这可以很好地(但不是很好地)处理过去或未来的日期,但是如果假设同一天内的范围(时间不同)很少或没有范围是错误的,因为信息完全丢失了,那么这是非常可怕的。

如果我期待(或写作供其他各方普遍使用,但不能假设其他情况),我会选择:

int startHash = startDate.GetHashCode();
return (((startHash >> 24) & 0x000000FF) | ((startHash >> 8) & 0x0000FF00) | ((startHash << 8) & 0x00FF0000) | (unchecked((int)((startHash << 24) & 0xFF000000)))) ^ endDate.GetHashCode();

如果第一个方法是基于这样一个假设,即datetime中的通用gethashcode没有我们想要的那么好,那么这个方法取决于它是否好,但是它混合了一个值的位。

在处理更明显的棘手情况时,例如两个值相同,或者彼此之间有一个相同的距离(例如很多1天或1小时的范围),这是很好的。在第一个例子效果最好的情况下,情况就不那么好了,但是如果在同一天使用很多范围,但时间不同,那么第一个例子就完全糟糕。

编辑:要对Dour的问题给出更详细的答复:

多尔正确地指出,这一页上的一些答案会丢失数据。事实上,他们都会丢失数据。

问题中定义的类有8.9607748310 ^三十七 不同的有效状态(或9.9564164810 ^三十六 如果我们不关心每个日期的datetimekind),并且gethashcode的输出有4294967296个可能的状态(其中一个-zero-也将被用作空值的hashcode,这通常可以与实际代码进行比较)。无论我们做什么,我们都会将信息量表减少2.31815886 10 ^二十七 . 我们丢失了很多信息!

有些人比其他人更容易失去,这很可能是真的。当然,很容易证明一些解决方案 可以 写一个有效但很差的答案会比其他人损失更多。

(更糟糕的可能有效的解决方案是 return 0; 它是有效的,因为它不会在相等的对象上出错或不匹配,但在所有值发生碰撞时,它会尽可能差。基于哈希的集合的性能变为O(n),并且随着O(n)的发展而变慢,因为所涉及的常量高于搜索无序列表等O(n)操作。

很难衡量到底损失了多少。考虑到XOR将剩下的信息量减半,XORing丢失前某些位的移位要比交换位多多少。即使是中殿 x ^ y 它的损失不超过swap和xor,只是在公共值上冲突更多;swap和xor将在普通xor没有的值上冲突。

一旦我们在不丢失更多信息的解决方案之间做出选择,但返回4294967296或接近4294967296的可能值,这些值之间的分布良好,那么问题就不再是 多少钱? 信息丢失(答案只有4.3137682110 ^{- 28} 保留原始信息),但 哪一个 信息丢失。

这就是我上面的第一个建议忽略时间成分的原因。一天有864000000000个“滴答”(100纳秒单位,日期时间的分辨率为),我扔掉了这些滴答中的两块(7.4649610)。 ^二十三 两者之间的可能值)是故意的,因为我正在考虑一个无论如何都不使用该信息的场景。在这种情况下,我特意设计了一种机制,以便 哪一个 信息会丢失,这改善了给定情况下的散列值,但是如果我们有不同的值,所有的开始和结束日期都不是在同一天发生,而是在不同的时间发生,那么它就变得毫无价值。

同样,x^y不会比其他任何信息丢失更多的信息,但是它丢失的信息比其他选择更重要。

在没有任何方法来预测哪些信息可能是重要的(特别是如果您的类是公共的,并且它的散列代码由外部代码使用)的情况下,我们在可以安全地进行的假设中受到了更大的限制。

作为一个整体,prime mult或prime mod方法比基于移位的方法更容易丢失信息,除非在基于哈希的方法中使用相同的prime进行进一步的哈希运算,具有讽刺意味的是,考虑到相同的目标(没有一个数字对其本身是相对prime的)。即使是素数),在这种情况下,它们更糟。另一方面,如果将基于移位的方法输入到基于移位的进一步散列中,那么基于移位的方法确实会失败。对于任意数据和任意使用,没有完美的散列(除非类只有很少的有效值,并且我们将它们全部匹配,在这种情况下,它更严格地说是一种编码,而不是我们生成的散列)。

简而言之,无论你做什么,你都会失去信息 哪一个 你输了,这很重要。

我从有效Java中使用这种方法来组合哈希:

unchecked
{
    int hash = 17;
    hash = hash * 31 + field1.GetHashCode();
    hash = hash * 31 + field2.GetHashCode();
    ...
    return hash;
}

在这种情况下,没有理由不起作用。

好吧,考虑一个好的哈希函数应该具有什么特征。它 必须 :

• 与equals一致-也就是说,如果两个对象的equals为true,那么两个哈希代码也必须相同。
• 永不崩溃

而且它 应该 :

• 非常快
• 对类似的输入给出不同的结果

我要做的是想出一个非常简单的算法;比如,从第一个哈希代码中提取16位,从第二个哈希代码中提取16位,然后将它们组合在一起。让自己成为 代表 样本;可能实际使用的日期范围,并查看此算法是否提供了良好的分布。

一个常见的选择是将两个散列进行异或运算。对于这种类型,这不一定是一个好主意,因为似乎有人希望表示从x到x的零长度范围。如果对两个相同日期时间的哈希执行XOR,则始终会得到零,这似乎是许多哈希冲突的一个秘诀。

您必须移动范围的一端,否则两个相等的日期将散列为零,我想这是一个非常常见的场景:

return startDate.GetHashCode() ^ (endDate.GetHashCode() << 4);

return startDate.GetHashCode() ^ endDate.GetHashCode();

可能是个好的开始。当开始日期和结束日期之间的距离相等但日期不同时,必须检查是否获得良好的分布。