c# - 使用C#HashSet解决等不等的问题

Question

我的依据是我最近发现的关于 Dictionary 的性能特征，所以我使用 Dictionary<type, bool> bool在哪里被忽略但据说我可以使用 HashSet相反。

例如:

Dictionary<bounds, bool> overlap;

class bounds
{
    public float top_left_x, top_left_y, width, height;

    public bool equal(bounds other)
    {
        return upper_left_x + width > other.upper_left_x &&
        upper_left_x < other.upper_left_x + other.width &&
        upper_left_y + height > other.upper_left_y &&
        upper_left_y < other.upper_left_y + other.height;
    }

    public ... GetHashCode()
    {
        ...;
    }
}

在这里，我没有使用 equal 检查是否相等，而是检查重叠，这在其他地方肯定会很烦人，但我这样做是有原因的。

我假设如果可以在 O(1) 时间内从键中查找值，那么从键本身也可以。

所以我大概可以将数千个边界重叠并执行此操作:

overlap.ContainsKey(new bounds(...));

在 O(1) 时间内找出给定边界是否与集合中的任何其他边界重叠。

我还想知道如果我更改边界的 (x, y) 位置会发生什么，大概就像删除然后再将其添加到集合中一样性能明智，非常昂贵？

我应该在 GetHashCode 函数中输入什么？

目标

如果这可行，那么我将使用这种机制找出给定边界重叠的其他边界。

此系统中移动的边界很少，并且在填充集合后不会添加新边界。新添加的边界需要能够与旧边界重叠。

结论

有关详细信息，请参阅下面的反馈。

总而言之，不可能实现 O(1) 性能，因为与默认的 equals 不同，重叠检查不是可传递的。

然而，区间树是一个很好的解决方案。

Answer 1

在这里使用相等关系完全是错误的关系，因为相等必须是等价关系。也就是说，它必须是自反的 -- A == A 对于任何 A。它必须是对称的 -- A == B 意味着 B == A。并且它必须是可传递的——如果 A == B 和 B == C 那么 A == C。

你提议违反传递属性； “重叠”不是传递关系，因此“重叠”不是等价关系，因此不能将相等定义为重叠。

与其尝试做这种危险的事情，不如解决真正的问题。您的目标显然是采用一组间隔，然后快速确定给定间隔是否与这些间隔中的任何一个重叠。您想要的数据结构称为区间树； 它经过专门优化以准确解决该问题，因此请使用它。 在任何情况下，您都不应尝试将哈希集用作区间树。使用正确的工具来完成这项工作:

http://wikipedia.org/wiki/Interval_tree