使用C＃HashSet来解决相等不相等的问题 [英] Using C# HashSet to solve problems where equal is not equal

问题描述

我根据最近发现的关于 Dictionary 的性能特点，所以我使用 Dictionary< type，bool> 其中 bool 被忽略，但应该可以使用 HashSet 。

例如：

 字典< bounds，bool>交叠; 
 
 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）时间内找出。 / p>

我也想知道如果我改变一个绑定的（x，y）位置会发生什么，大概就像删除，然后将其添加到设置再次执行明智的，非常昂贵的？

我放入GetHashCode函数是什么？

strong>

如果这样工作，那么我使用这种机制来找出给定绑定重叠的其他限制。

在此系统中移动很少的边界，在填充集合后不会添加新的边界。

结论

新增的界限需要与旧版本重叠。有关详细信息，请参阅下面的反馈。

总而言之，不可能实现O（1）性能，因为与默认值不同，重叠检查不是传递的

间隔树是一个很好的解决方案。

解决方案

在这里，我没有使用相等的方式检查平等，而是重叠，这在其他地方一定会令人烦恼，但是有一个我为什么要这样做的原因。

我假设这意味着你会有一个场景，其中A.Equals（B）是真的，B.Equals（C）是真的，但是A.Equals（ C）是假的。换句话说，你的Equals不是传递的。

这是破坏Equals（）的规则，结果Dictionary将不适合你。 Equals / GetHashCode的规则是（从 http：// msdn。 microsoft.com/en-us/library/system.object.gethashcode.aspx ）：

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

如果您的Equals不可传递，那么您不可能写入一个有效的GetHashCode。 >

I'm basing this on performance characteristics I've recently found out about Dictionary, so I'm using Dictionary<type, bool> where the bool is ignored but supposedly I could use HashSet instead.

For example:

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

Here I'm not using equal to check for equality but instead for overlapping, which is bound to be annoying elsewhere but there is a reason why I'm doing it.

I'm presuming that if a value can be looked up from a key in O(1) time then so can a key from itself.

So I could presumably put thousands of bounds into overlap and do this:

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

To find out in O(1) time if a given bound overlaps any others from the collection.

I'd also like to know what happens if I change the (x, y) position of a bound, presumably it's like removing and then adding it into the set again performance wise, very expensive?

What do I put into the GetHashCode function?

goal

If this works then I'm after using this sort of mechanism to find out what other bounds a given bound overlaps.

Very few bounds move in this system and no new ones are added after the collection has been populated. Newly added bounds need to be able to overlap old ones.

conclusion

See the feedback below for more details.

In summary it's not possible to achieve the O(1) performance because, unlike the default equals, a check for overlapping is not transitive.

An interval tree however is a good solution.

解决方案

Here I'm not using equal to check for equality but instead for overlapping, which is bound to be annoying elsewhere but there is a reason why I'm doing it.

I'm assuming this means you will have a scenario where A.Equals(B) is true, B.Equals(C) is true, but A.Equals(C) is false. In other words, your Equals is not transitive.

That is breaking the rules of Equals(), and as a result Dictionary will not work for you. The rule of Equals/GetHashCode is (from http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx):

If two objects compare as equal, the GetHashCode method for each object must return the same value.

If your Equals is not transitive, then you can't possibly write a valid GetHashCode.

这篇关于使用C＃HashSet来解决相等不相等的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！