使用C#哈希集来解决equal不等于的问题

本文关键字：不等于 问题 equal 解决 哈希集 使用 | 更新日期: 2023-09-27 18:19:44

这是基于我最近发现的关于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）性能，因为与默认的equals不同，对重叠的检查是不可传递的。

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

使用C#哈希集来解决equal不等于的问题

等式关系是完全错误的关系，因为等式需要是equivalence关系。也就是说，它必须是自反性的--对于任何A，A==A。它必须是对称的--A==B意味着B==A.它必须是传递性的--如果A==B和B==C，则A==C。

你提出的是对传递性的侵犯；"重叠"不是传递关系，因此"重叠"也不是等价关系，因此不能将相等定义为重叠。

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

http://wikipedia.org/wiki/Interval_tree

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

我假设这意味着你将有一个场景，其中a.Equals（B）为真，B.Equals）（C）为真但a.Equal斯（C）是假的。换句话说，您的Equals是不可传递的。

这违反了Equals（）的规则，因此Dictionary将不适用于您。Equals/GetHashCode的规则是（来自http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx)：

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

如果Equals不可传递，则不可能编写有效的GetHashCode。

如果您使用我上面提到的派生类方法，您需要以下内容：

public class Bounds
{
    public Point position;
    public Point size; // I know the width and height don't really compose
                       // a point, but this is just for demonstration
    public override int GetHashCode(){...}
}
public class OverlappingBounds : Bounds
{
    public override bool Equals(object other)
    {
        // your implementation here
    }
}
// Usage:
if (_bounds.ContainsKey(new OverlappingBounds(...))){...}

但是由于GetHashCode（）方法需要始终返回相同的值，因此运行时复杂性很可能是O（n）而不是O（1）。

您不能使用Dictionary或HashSet来检查边界是否重叠。为了能够使用字典（或哈希集），您需要满足以下属性的Equals()和GetHashCode()方法：

  1. Equals()方法是一个等价关系
  2. a.Equals(b)必须表示a.GetHashCode() == b.GetHashCode()

您不能满足这两个要求，所以您必须使用另一个数据结构：间隔树。

在自定义hashcode calculation的字典上，不能保证O(1)的性能。如果我在GetHashCode()方法中放入一些WebService请求，它应该为我控制所提供的2个项的相等性，那么很明显，时间永远不会像预期的那样是O(1)。好吧，这是一种"边缘案例"，但只是给出一个想法。

通过以您认为可以做到的方式（假设这是可能的）执行imo，您否定了Dictionary<K,V>提供的好处，因此在大型集合上也需要恒定的密钥恢复时间。

它需要在你拥有的合理数量的对象上进行测量，但我首先会尝试使用List<T>就像一个物体支架，并制作这样的东西：

var bounds = new List<Bound> {.... initialization... }
Bound providedBound = //something. Some data filled in it. 
var overlappedany = bounds.Any<Bound>(b=>return b.Equals(providedBound));
相关文章：