c# - 为什么 HashSet 比 HashSet 慢这么多？

Question

我想存储一些不允许重复的像素位置，所以首先想到的是 HashSet<Point>或类似的类(class)。然而，与 HashSet<string> 之类的东西相比，这似乎非常慢.

例如，这段代码:

HashSet<Point> points = new HashSet<Point>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(new Point(x, y));
        }
    }
}

大约需要 22.5 秒。

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

HashSet<string> points = new HashSet<string>();
using (Bitmap img = new Bitmap(1000, 1000))
{
    for (int x = 0; x < img.Width; x++)
    {
        for (int y = 0; y < img.Height; y++)
        {
            points.Add(x + "," + y);
        }
    }
}

那么，我的问题是:

• 这是有原因的吗？我检查了 this answer ，但 22.5 秒远远超过该答案中显示的数字。
• 有没有更好的方法来存储不重复的点？

Answer 1

Point 结构引发了两个性能问题。添加 Console.WriteLine(GC.CollectionCount(0)); 时可以看到的内容到测试代码。您会看到点测试需要约 3720 个集合，但字符串测试只需要约 18 个集合。不是免费的。当您看到一个值类型引发了如此多的集合时，您需要得出结论“呃，太多装箱了”。

问题在于 HashSet<T>需要一个 IEqualityComparer<T>完成它的工作。由于您没有提供，因此需要回退到 EqualityComparer.Default<T>() 返回的一个.该方法可以很好地处理字符串，它实现了IEquatable。但对于 Point 而言，它是一种源自 .NET 1.0 的类型，从未得到泛型的喜爱。它所能做的就是使用对象方法。

另一个问题是 Point.GetHashCode() 在此测试中表现不佳，碰撞太多，因此它对 Object.Equals() 的影响非常大。 String 具有出色的 GetHashCode 实现。

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

class PointComparer : IEqualityComparer<Point> {
    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<Point> list = new HashSet<Point>(new PointComparer());

现在它快了大约 150 倍，轻松击败了字符串测试。