为什么是哈希集比 HashSet 慢得多?

小编典典

为什么是哈希集比 HashSet 慢得多?

all

我想存储一些像素位置而不允许重复，所以首先想到的是HashSet<Point>或类似的类。然而，与类似的东西相比，这似乎非常慢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);
        }
    }
}

所以，我的问题是：

这有什么原因吗？我检查了答案，但 22.5 秒比那个答案中显示的数字多得多。
有没有更好的方法来存储没有重复的点？

阅读 71

2022-08-29

共1个答案

小编典典

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

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

另一个问题是 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 倍，轻松击败了字符串测试。

2022-08-29