为什么HashSet<Point>比HashSet<string>慢得多？

我想存储一些像素位置而不允许重复,所以首先想到的是HashSet或类似的类.然而,与类似的情况相比,这似乎非常缓慢HashSet.

例如,这段代码:

HashSet points = new HashSet();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x 

大约需要22.5秒.

虽然以下代码(由于显而易见的原因不是一个好的选择)只需1.6秒:

HashSet points = new HashSet();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x 

所以,我的问题是:


这有什么理由吗？我检查了这个答案,但22.5秒比答案中显示的数字更多.
有没有更好的方法来存储没有重复的点？

    

  




  
  
  

    

      

        Hans Passant..
         286
      
      
Point结构引发了两个性能问题.添加Console.WriteLine(GC.CollectionCount(0));到测试代码时可以看到的内容.您会看到Point测试需要~3720个集合,但字符串测试只需要~18个集合.不是免费的.当你看到一个值类型诱导如此多的集合时,你需要得出结论"呃哦,太多拳击".

问题是HashSet需要一个IEqualityComparer完成它的工作.由于你没有提供一个,它需要回退到一个返回的EqualityComparer.Default().该方法可以很好地完成字符串,它实现了IEquatable.但不是Point,它是一种类似于.NET 1.0的类型,从来没有得到泛型的爱.它所能做的只是使用Object方法.

另一个问题是Point.GetHashCode()在这个测试中没有做太多的工作,碰撞太多,所以它对Object.Equals()非常重要.String具有出色的GetHashCode实现.

您可以通过为HashSet提供一个好的比较器来解决这两个问题.像这个:

class PointComparer : IEqualityComparer {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y <<16) ^ obj.X;
    }
}


并使用它:

HashSet list = new HashSet(new PointComparer());


它现在大约快150倍,轻松击败字符串测试.


1> Hans Passant..：
Point结构引发了两个性能问题.添加Console.WriteLine(GC.CollectionCount(0));到测试代码时可以看到的内容.您会看到Point测试需要~3720个集合,但字符串测试只需要~18个集合.不是免费的.当你看到一个值类型诱导如此多的集合时,你需要得出结论"呃哦,太多拳击".

问题是HashSet需要一个IEqualityComparer完成它的工作.由于你没有提供一个,它需要回退到一个返回的EqualityComparer.Default().该方法可以很好地完成字符串,它实现了IEquatable.但不是Point,它是一种类似于.NET 1.0的类型,从来没有得到泛型的爱.它所能做的只是使用Object方法.

另一个问题是Point.GetHashCode()在这个测试中没有做太多的工作,碰撞太多,所以它对Object.Equals()非常重要.String具有出色的GetHashCode实现.

您可以通过为HashSet提供一个好的比较器来解决这两个问题.像这个:

class PointComparer : IEqualityComparer {
    public bool Equals(Point x, Point y) {
        return x.X == y.X && x.Y == y.Y;
    }

    public int GetHashCode(Point obj) {
        // Perfect hash for practical bitmaps, their width/height is never >= 65536
        return (obj.Y <<16) ^ obj.X;
    }
}


并使用它:

HashSet list = new HashSet(new PointComparer());


它现在大约快150倍,轻松击败字符串测试.

        
它的灵感来自鼠标在窗户中的位置.对于您想要显示的任何位图,它都是完美的哈希. 
+1用于提供GetHashCode方法实现.只是出于好奇,你是怎么来特别的`obj.X <<16 | obj.Y;`实施. 
@AkashKC我不是很熟悉C#,但据我所知,整数通常是32位.在这种情况下,您需要2个数字的哈希值,并通过左移一个16位,确保每个数字的"低"16位不会用"|""影响"另一个数字.对于3个数字,将22和11用作移位是有意义的.对于4个数字,它将是24,16,8.但是仍然会发生碰撞但只有数字变大.但它也至关重要取决于`HashSet`的实现.如果它使用带有"位截断"的开放式地址(我不认为它!),左移方法可能会很糟糕. 
@HansPassant:我想知道在GetHashCode中使用XOR而不是OR可能稍好一些 - 如果点坐标可能超过16位(可能不在常见显示器上,但不久将来).// XOR在散列函数中通常比OR好,因为它丢失的信息较少,反转等等.//例如,如果允许负坐标,考虑如果Y为负,X贡献会发生什么. 
很高兴知道.编写像你这样的哈希码的任何文档或最佳指南？实际上,我仍然想知道上面的哈希码是否伴随您的经验或您遵循的任何准则. 

2> InBetween..：
性能下降的主要原因是拳击正在进行(正如Hans Passant的回答中所述).

除此之外,哈希码算法使问题恶化,因为它会导致更多的调用,Equals(object obj)从而增加装箱转换的数量.

另请注意,哈希码的Point计算方法是x ^ y.这会在您的数据范围内产生非常小的色散,因此HashSet人口过多 - 这种情况不会发生string,其中散列的散射要大得多.

您可以通过实现自己的Point结构(平凡)并使用更好的哈希算法来解决该问题,例如通过移动坐标:

(x <<16) ^ y


有关哈希码的一些好建议,请阅读Eric Lippert关于该主题的博客文章.

        
当你可以创建一个实现`IEqualityComparer `的类并且保持与`Point`一起使用的其他东西的兼容性同时获得没有穷人`GetHashCode`的好处并且需要时,不需要实现`Point`. `Equals()`中的框. 
查看Point的参考源,`GetHashCode`执行:`unchecked(x ^ y)`而对于`string`,它看起来要复杂得多. 
@AhmedAbdelhameed这可能是因为你在哈希集中添加的成员比你意识到的少(再次由于哈希码算法的可怕分散).完成填充后,"list"的数量是多少？ 
@AhmedAbdelhameed你的测试是错误的.你是一遍又一遍地添加相同的长片,所以实际上你插入的元素很少.插入`point`时,`HashSet`将在内部调用`GetHashCode`,对于每个具有相同哈希码的点,将调用`Equals`来确定它是否已经存在 
嗯..好吧,为了检查你的假设是否正确,我只是尝试使用`HashSet ()`,并使用`list.Add(unchecked(x ^ y));`来向HashSet添加值.这实际上甚至比`HashSet `*(345 ms)*更快.这与你描述的有什么不同吗？ 
@AhmedAbdelhameed  - 不知道,但我看了[这里](https://referencesource.microsoft.com/#System.Drawing/commonui/System/Drawing/Point.cs,a041be61667d4c9a​​) 
@InBetween我不打算使用`Point`,除非我需要它用于点东西,在这种情况下我需要`Point`.在正面,corefx有一个更好的哈希代码和一个`IEquatable `的实现,希望有一天会转移到netfx.