.net 为什么 HashSet 比 HashSet 慢这么多

发布于09月11日

我想在不允许重复的情况下存储一些像素位置，所以首先想到的是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秒.

而以下代码(which is not a good choice for obvious reasons)只需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);
        }
    }
}

So, my questions are:

这有什么原因吗？我 Select 了this answer秒，但22.5秒比答案中显示的数字要多得多.
有没有更好的方法来存储不重复的点？

推荐答案

Point struct 导致了两个性能问题.当你向测试代码中添加Console.WriteLine(GC.CollectionCount(0));时，你可以看到一些东西.您将看到点测试需要~3720个集合，而字符串测试只需要~18个集合.不是免费的.当你看到一个值类型包含这么多集合时，你需要总结"哦，太多装箱了".

争论的焦点是HashSet<T>需要IEqualityComparer<T>才能完成任务.因为您没有提供一个，所以需要退回到EqualityComparer.Default<T>()返回的一个.该方法可以很好地处理字符串，它实现了IEquatable.但并不是为了说明问题，这是一种值得借鉴的类型.NET 1.0，却从未得到泛型的喜爱.它所能做的就是使用对象方法.

另一个问题是这一点.GetHashCode()在这个测试中没有出色的表现，因为碰撞太多，所以它会敲打对象.相当严重.String有一个优秀的GetHashCode实现.

通过为哈希集提供一个好的比较器，可以解决这两个问题.就像这个:

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倍，很容易就超过了字符串测试.

.net 为什么 HashSet 比 HashSet 慢这么多

推荐答案

.net相关问答推荐

Docker失败文件找不到

SeriLog LogConext.PushProperty在ASP.NET MVC 5中不能使用OWIN中间件

SLN配置文件：映射问题

无法在 Blazor Server 应用程序中触发 InputRadio 的 onchange 事件

Dotnet 反射：使用 F# 中的out参数调用 MethodInfo 上的调用

在 ASP.NET MVC 中我可以在哪里放置自定义类？

.NET 中的线程安全集合

C# - 获取不包括隐藏文件的文件列表

使用 Thread.Abort() 有什么问题

使用 Task.Factory.StartNew 传递方法参数

我应该默认推荐密封类吗？

为什么 .NET 中没有可序列化 XML 的字典？

为什么要判断这个！= null？

如何右对齐 DataGridView 列中的文本？

静态析构函数

关于 Enumerable.Range 与传统 for 循环的 foreach 的思考

仅使用 XAML 绘制纯色三角形

将字典值转换为数组

在 C# 中，为什么不能将 List 对象存储在 List

无法加载文件或程序集System.ValueTuple