1

我有以下课程

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？

4

5 回答 5

6

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

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

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

于 2010-08-19T20:37:53.677 回答
5

这取决于我希望看到它使用的值。

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

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个不同的有效状态（如果我们不关心每个日期的 DateTimeKind，则为 9.95641648×10 36 个），GetHashCode 的输出有 4294967296 个可能的状态（其中一个 - 零 -也将用作空值的哈希码，通常可以与实际代码进行比较）。无论我们做什么，我们都会以 2.31815886 × 10 27的比例减少信息。我们丢失了很多信息！

很可能是真的，我们在某些方面会比在其他方面失去更多。当然，通过编写一个有效但非常糟糕的答案，很容易证明某些解决方案可能比其他解决方案损失更多。

（更糟糕的可能有效解决方案是return 0;有效的，因为它永远不会在相等的对象上出错或不匹配，但尽可能差，因为它会碰撞所有值。基于散列的集合的性能变为 O(n)，并且慢为 O (n) 去，因为所涉及的常数高于搜索无序列表这样的 O(n) 操作）。

很难衡量损失了多少。考虑到 XOR 将剩余的信息量减半，在 XORing 之前移位某些位比交换位损失多少。即使是幼稚的x ^ y人也不会失去比交换和异或更多的东西，它只是更多地在共同价值观上发生冲突；交换和异或将在普通异或没有的值上发生冲突。

一旦我们在不丢失更多信息但返回 4294967296 或接近 4294967296 个可能值且这些值之间分布良好的解决方案之间做出选择，那么问题不再是丢失了多少信息（答案仅保留 4.31376821×10 -28的原始信息）但丢失了哪些信息。

这就是为什么我上面的第一个建议忽略了时间成分。一天有 864000000000 个“滴答声”（DateTime 的分辨率为 100 纳秒单位），我故意扔掉其中的两块滴答声（两者之间的可能值为 7.46496×10 23个可能值），因为我正在考虑一个场景无论如何都不会使用该信息。在这种情况下，我特意构建了机制，以便选择哪些信息会丢失，从而改善给定情况下的哈希值，但是如果我们有不同的值并且开始和结束日期都没有发生，那么它绝对毫无价值同一天，但在不同的时间。

同样，x ^ y 不会比其他任何一个丢失更多的信息，但它确实丢失的信息比其他选择更可能是重要的。

在没有任何方法可以预测哪些信息可能很重要（尤其是如果您的类将是公共的并且它的哈希码被外部代码使用）的情况下，那么我们在可以安全地做出的假设方面受到更多限制。

总体而言，prime-mult 或 prime-mod 方法在丢失信息方面比基于移位的方法更好，除非在可能发生在基于散列的方法内部的进一步散列中使用相同的素数，具有讽刺意味的是记住目标（没有数字与自身相对质数！甚至质数）在这种情况下，它们会更糟。另一方面，如果将基于移位的方法输入到基于移位的进一步哈希中，则基于移位的方法确实会失败。对于任意数据和任意使用没有完美的散列（除非一个类的有效值很少并且我们将它们全部匹配，在这种情况下，它比我们产生的散列更严格地是一种编码）。

简而言之，无论你做什么，你都会丢失信息，重要的是你丢失了什么。

于 2010-08-19T22:14:25.463 回答
4

好吧，考虑一个好的散列函数应该具有哪些特征。它必须：

  • 与 Equals 一致 - 也就是说，如果 Equals 对于两个对象为真，那么这两个哈希码也必须相同。
  • 永不崩溃

它应该：

  • 非常快
  • 为相似的输入给出不同的结果

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

一个常见的选择是将两个散列异或在一起。对于这种类型，这不一定是一个好主意，因为似乎有人想要表示从 X 到 X 的零长度范围。如果你对两个相等的 DateTimes 的哈希值进行异或运算，你总是得到零，这看起来像一个很多哈希冲突的秘诀。

于 2010-08-19T20:41:47.980 回答
1

您必须移动范围的一端，否则两个相等的日期将散列为零，我想这是一种很常见的情况：

return startDate.GetHashCode() ^ (endDate.GetHashCode() << 4);
于 2010-08-19T20:38:01.587 回答
0 
return startDate.GetHashCode() ^ endDate.GetHashCode();

可能是一个好的开始。当 startDate 和 endDate 之间的距离相等但日期不同时，您必须检查是否获得了良好的分布。

于 2010-08-19T20:35:03.897 回答