使用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()
    {
        ...;
    }
}

在这里,我没有使用等于检查相等,而是重叠,这在其他地方一定会令人讨厌,但我有理由这样做.

我假设如果一个值可以在O(1)时间内从一个键中查找,那么一个键也可以从它自己查找.

所以我可能会把数千个边界重叠并做到这一点:

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

如果给定的绑定与集合中的任何其他绑定重叠,则在O(1)时间内找出.

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

我将什么放入GetHashCode函数？

目标

如果这有效,那么我在使用这种机制后找出给定边界重叠的其他边界.

在这个系统中很少有边界移动,并且在填充集合后没有添加新的边界.新添加的边界需要能够重叠旧的边界.

结论

有关详细信息,请参阅下面的反馈.

总之,不可能实现O(1)性能,因为与默认等于不同,检查重叠是不可传递的.

然而,间隔树是一个很好的解决方案.

Answer 1

在这里使用等式关系是完全错误的关系,因为等式必须是等价关系.也就是说,它必须是自反的 - 对于任何A,A == A.它必须是对称的 - A == B意味着B == A.并且它必须是可传递的 - 如果A == B且B == C然后A == C.

您提议违反过渡性财产; "重叠"不是传递关系,因此"重叠"不是等价关系,因此您不能将相等定义为重叠.

而不是试图做这个危险的事情,解决真正的问题.您的目标显然是采用一组间隔,然后快速确定给定间隔是否与任何间隔重叠.您想要的数据结构称为区间树 ; 它专门针对这个问题进行了优化,因此请使用它. 在任何情况下都不应尝试将哈希集用作间隔树.使用正确的工具:

http://wikipedia.org/wiki/Interval_tree

Answer 2

在这里,我没有使用等于检查相等,而是重叠,这在其他地方一定会令人讨厌,但我有理由这样做.

我假设这意味着你将有一个场景,其中A.Equals(B)为真,B.Equals(C)为真,但A.Equals(C)为假.换句话说,您的等于不可传递.

这违反了Equals()的规则,因此Dictionary不适合你.Equals/GetHashCode规则是(来自http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx):

如果两个对象比较相等,则每个对象的GetHashCode方法必须返回相同的值.

如果您的Equals不可传递,那么您不可能编写有效的GetHashCode.