小编典典

为什么是哈希集比 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 秒比那个答案中显示的数字多得多。
  • 有没有更好的方法来存储没有重复的点?

阅读 89

收藏
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