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

Question

我想存储一些像素位置而不允许重复,所以首先想到的是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秒比答案中显示的数字更多.
• 有没有更好的方法来存储没有重复的点？

Answer 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倍,轻松击败字符串测试.

Answer 2

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

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

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

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

(x << 16) ^ y

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