为什么HashSet<T>类不用于实现Enumerable.Distinct

我需要访问IEnumerable.Distinct大O表示法 的渐近时间和空间复杂度

所以我在看扩展方法的实现,Enumerable.Distinct我看到它是使用和内部类实现的Set,这几乎是一个带有"开放寻址"的哈希表的经典实现

很快引起注意的是,很多代码Set只是一个复制粘贴HashSet,有一些遗漏

但是,这种简化的Set实现有一些明显的缺陷,例如Resize不使用素数作为插槽大小的方法,就像HashSet看到的那样,请参阅HashHelpers.ExpandPrime

所以,我的问题是:

这里代码重复的原因是什么,为什么不坚持DRY原则？特别是考虑到这两个类都在同一个程序集中System.Core

它看起来HashSet会表现得更好,所以我应该避免使用Distinct扩展方法,并编写我自己的扩展方法,HashSet而不是使用Set？

Jon Hanna.. 6

这几乎是具有"开放寻址"的哈希表的经典实现

再看一遍.它与列表头单元格分开链接.虽然插槽都在一个阵列中,但在碰撞情况下找到下一个插槽是通过检查next当前插槽的字段来完成的.这比使用链接列表和每个节点作为单独的堆对象具有更好的缓存效率,但在这方面不如开放寻址那么好.同时,它避免了一些开放式寻址效果不佳的情况.

Set中的很多代码只是来自HashSet的复制粘贴,有一些遗漏

AFAICT使用哈希集的私有实现的原因是Enumerable并且HashSet几乎在同一时间独立开发.这只是我的猜想,但它们都是用.NET 3.5引入的,所以它是可行的.

很可能HashSet从复制开始Set,然后更好地公开曝光,尽管这两者都可能都基于与列表头单元格分开链接的相同原则

在性能方面,HashSet使用素数意味着它更有可能避免与较差的哈希冲突(但这只是一个优势,这不是一个简单的问题),但Set在很多方面更轻,特别是在.NET中核心,其中不需要的东西被删除.特别是,该版本Set采用的事实,即一旦一个项目被删除(这情况发生,例如,在优势Intersect),永远不会有新增项目,这使得它能够省去freelist与此相关的任何工作,这HashSetcouldn"做.即使是最初的实施也没有跟踪版本以便在枚举期间捕获变化,这是一个很小的成本,但是每次添加和删除的成本都是如此.

因此,对于具有不同哈希码分布的不同数据集,有时一个表现更好,有时另一个表现更好.

特别是考虑到这两个类都在同一个程序集System.Core中

仅在某些版本的.NET中,在某些版本中,它们位于不同的程序集中.在.NET Core中,我们有两个版本Set,一个在程序System.Linq集中,另一个在单独的程序集中System.Linq.Expressions.前者如上所述被削减,后者被替换为使用,HashSet因为它在那里做得少.

当然System.Core是第一位的,但是这些元素可以完全分开的事实说明System.Core不是一个单一依赖关系的整体blob.

现在有一种ToHashSet()方法在.NET核心的版本的LINQ使得更换的可能性Set有HashSet更合理的,虽然不是没有脑子.我认为@james-ko正在考虑测试这样做的好处.

它看起来HashSet会表现得更好

由于上面解释的原因,情况可能并非如此,但可能确实如此,具体取决于源数据.这是在考虑经过一些不同的linq方法的优化之前(在linq的初始版本中并不多,但在.NET Core中很少).

所以我应该避免使用Distinct扩展方法,并编写我自己的扩展方法,HashSet而不是使用Set.

使用Distinct().如果你有一个瓶颈,那么它可能HashSet会在给定的数据集中获胜,但是如果你确实尝试这样做,请确保你的分析与你的代码在现实生活中会遇到的实际值非常接近.没有必要决定一种方法是基于某些任意测试更快,如果你的应用程序遇到另一个做得更好的情况.(如果我发现这是一个问题点,我会先看看有问题GetHashCode()的类型是否可以改进速度或比特分配,首先).

这几乎是具有"开放寻址"的哈希表的经典实现

再看一遍.它与列表头单元格分开链接.虽然插槽都在一个阵列中,但在碰撞情况下找到下一个插槽是通过检查next当前插槽的字段来完成的.这比使用链接列表和每个节点作为单独的堆对象具有更好的缓存效率,但在这方面不如开放寻址那么好.同时,它避免了一些开放式寻址效果不佳的情况.

Set中的很多代码只是来自HashSet的复制粘贴,有一些遗漏

AFAICT使用哈希集的私有实现的原因是Enumerable并且HashSet几乎在同一时间独立开发.这只是我的猜想,但它们都是用.NET 3.5引入的,所以它是可行的.

很可能HashSet从复制开始Set,然后更好地公开曝光,尽管这两者都可能都基于与列表头单元格分开链接的相同原则

在性能方面,HashSet使用素数意味着它更有可能避免与较差的哈希冲突(但这只是一个优势,这不是一个简单的问题),但Set在很多方面更轻,特别是在.NET中核心,其中不需要的东西被删除.特别是,该版本Set采用的事实,即一旦一个项目被删除(这情况发生,例如,在优势Intersect),永远不会有新增项目,这使得它能够省去freelist与此相关的任何工作,这HashSetcouldn"做.即使是最初的实施也没有跟踪版本以便在枚举期间捕获变化,这是一个很小的成本,但是每次添加和删除的成本都是如此.

因此,对于具有不同哈希码分布的不同数据集,有时一个表现更好,有时另一个表现更好.

特别是考虑到这两个类都在同一个程序集System.Core中

仅在某些版本的.NET中,在某些版本中,它们位于不同的程序集中.在.NET Core中,我们有两个版本Set,一个在程序System.Linq集中,另一个在单独的程序集中System.Linq.Expressions.前者如上所述被削减,后者被替换为使用,HashSet因为它在那里做得少.

当然System.Core是第一位的,但是这些元素可以完全分开的事实说明System.Core不是一个单一依赖关系的整体blob.

现在有一种ToHashSet()方法在.NET核心的版本的LINQ使得更换的可能性Set有HashSet更合理的,虽然不是没有脑子.我认为@james-ko正在考虑测试这样做的好处.

它看起来HashSet会表现得更好

由于上面解释的原因,情况可能并非如此,但可能确实如此,具体取决于源数据.这是在考虑经过一些不同的linq方法的优化之前(在linq的初始版本中并不多,但在.NET Core中很少).

所以我应该避免使用Distinct扩展方法,并编写我自己的扩展方法,HashSet而不是使用Set.

使用Distinct().如果你有一个瓶颈,那么它可能HashSet会在给定的数据集中获胜,但是如果你确实尝试这样做,请确保你的分析与你的代码在现实生活中会遇到的实际值非常接近.没有必要决定一种方法是基于某些任意测试更快,如果你的应用程序遇到另一个做得更好的情况.(如果我发现这是一个问题点,我会先看看有问题GetHashCode()的类型是否可以改进速度或比特分配,首先).