什么是DateRange类的好hashCode

Question

我有以下课程

public class DateRange
{
    private DateTime startDate;
    private DateTime endDate;
    public override bool Equals(object obj)
    {
        DateRange other = (DateRange)obj;
        if (startDate != other.startDate)
            return false;
        if (endDate != other.endDate)
            return false;
        return true;
    }
    ...
}

我需要在一个使用DateRange键入的字典中存储一些值,如:

Dictionary<DateRange, double> tddList;

我应该如何覆盖类的GetHashCode()方法DateRange？

Answer 1

我使用Effective Java中的这种方法来组合哈希:

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

在这种情况下,没有理由不能正常工作.

Answer 2

这取决于我期望看到它使用的值.

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

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的关注做出更详细的回应:

Dour正确指出,此页面上的一些答案会丢失数据.事实是,他们都失去了数据.

在问题中定义的类有8.96077483×10 ^37种不同的有效状态(或9.95641648×10 ³⁶,如果我们不关心每个日期的DateTimeKind),和GetHashCode的输出具有4294967296种可能的状态(其中之一-零-也将被用作空值的哈希码,这通常可以与实际代码进行比较).无论我们做什么,我们都会以2.31815886×10 ²⁷的比例缩小信息.这是我们丢失的很多信息!

我们可能会失去一些比其他人更多的损失.当然,通过编写有效但非常差的答案,很容易证明某些解决方案可能比其他解决方案损失更多.

(更糟的可能的有效的解决方案是return 0;其是有效的,因为它在相等的对象从来没有错误或不匹配,但穷尽可能它发生碰撞的所有值.基于散列的集合的性能变得O(n)和缓慢的O (n)因为所涉及的常数高于搜索无序列表的O(n)操作.

很难衡量损失多少.考虑到XOR将剩余的信息量减半,在XORing丢失之前,某些比特的移位要比交换比特多少多少.即使是幼稚的人x ^ y也不会失去掉掉交换的权利,它只会在共同的价值观上发生冲突; swap-and-xor会在plain-xor没有的值上发生碰撞.

一旦我们得到不与这些值之间的良好的销售损失比可能更多的信息,但返回4294967296或接近4294967296个可能值解决方案之间进行选择,那么问题就不再有多少信息丢失(答案只有4.31376821×10 ^-28的原始信息仍然存在)但丢失了哪些信息.

这就是为什么我上面的第一个建议忽略了时间成分.有8640亿"蜱"(该100nanosecond单位的DateTime具有的分辨率),在一天,我扔掉那些蜱(7.46496×10的两个块²³的目的,两者之间可能的值),因为我想一个场景无论如何不使用该信息的地方.在这种情况下,我特意结构化的方式来挑选机制,其信息会丢失,这提高了特定情况下的哈希值,但这样的确,如果完全不值钱的,我们有所有的开始和结束日期,没有发生不同的价值取向同一天,但在不同的时间.

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

如果没有任何方法可以预测哪些信息可能具有重要性(特别是如果您的类是公开的,并且外部代码使用其哈希码),那么我们可以安全地做出更多限制.

作为一个整体的黄金MULT或原-MOD方法在该信息更好它们失去比基于移位方法中,当相同的素数是用来在进一步的散列可能发生基于散列的方法内,讽刺用相同的除记住目标(没有数字是相对本质的!甚至是素数)在这种情况下它们更糟糕.另一方面,基于移位的方法如果被用于基于移位的进一步哈希则真的会倒下.任意数据和任意使用都没有完美的哈希值(除非一个类的有效值很少,我们将它们全部匹配,在这种情况下,它更严格地说是编码而不是我们生成的哈希).

总之,你会失去不管你做什么的信息,这其中你失去这很重要.