SortedSet<T>与HashSet<T>的区别

Question

我的问题是：既然有SortedSet<T>，那为什么还需要使用HashSet<T>呢？毕竟在SortedSet中，所有HashSet的方法都是可用的，并且SortedSet还有一个优势，即提供了已排序的集合！即使如此，HashSet仍然存在。那它到底有什么用处呢？

- Batrickparry

---

如果您希望项目无序且唯一，那么使用 HashSet<T> 如何？来自 MSDN > HashSet<T> 类提供高性能的集合操作。集合是一个不包含重复元素且元素没有特定顺序的集合。http://msdn.microsoft.com/en-us/library/bb359438.aspx - OnesimusUnbound

如果你有一组事物本来就没有良序，那怎么办呢？比如说，你想在三维空间中制作一个排序后的点集，你该按什么进行排序呢？ - Eric Lippert

在使用 HashSet<T> 时需要知道的一个（有时候）有用的事情是：即使在 64 位应用程序中，它也可以存储多达 ~4800 万个 Guid 或 long 或 ~9500 万个 int，之后会抛出 OutOfMemoryException。SortedSet<T> 的容量极限似乎要高得多。如果因某些原因需要在内存中保留数亿个项目，则 HashSet<T> 可能不是一个好选择。 - Vladimir Reshetnikov

根据文档，“对于非常大的HashSet<T>对象，您可以通过在运行时环境中将<gcAllowVeryLargeObjects>配置元素的enabled属性设置为true来将最大容量增加到64位系统上的20亿个元素。” @Vladimir - bkqc

Answer 1

如果你不需要排序功能，就不应该使用带有排序功能的类，因为这意味着你的应用程序将比其所需做更多的工作。(换言之，这会让你的应用程序变得更快)。

- Jacob

---

更重要的是，算法将运行得更快。哈希运算的时间复杂度为O(1)，而排序集合很可能使用二叉搜索树，平均情况下时间复杂度为O(log n) -- 性能差得多。 - Christian Mann

集合用于存储唯一的元素，列表可以包含重复的条目。请参阅http://msdn.microsoft.com/en-us/library/bb359438.aspx上的HashSet<T>文档。它说：集合是一个不包含重复元素并且元素没有特定顺序的集合。 - OnesimusUnbound

这是算法计算强度的粗略指标。请参见 http://en.wikipedia.org/wiki/Big_O_notation - Jacob

@新手：通俗地说，运行在O(1)时间复杂度的算法意味着它无论输入的大小如何，都会以相同的时间运行。否则，时间将取决于输入的大小n，并表示为n的函数。例如，线性：O(n)，二次方：O(n^2)等。大O符号维基页面可能很难理解，这个总结得很好。 - Jeff Mercado

@BlueMonkMN，在线版本（MSDN）相对于您的旧版本显然已经修正。SortedSet<> 的查找时间是 O(log n)，HashSet<> 是 O(1)，而 List<> 是 O(n)。 - Lucero

Answer 2

这是关于选择合适的工具来完成工作的问题。这取决于你将如何使用你的集合。 这个页面有一个详细列出各种集合类之间的区别的漂亮表格。

以下是从那个表格中提取出来的关于你所询问的集合的内容：

集合	排序	连续性？	直接访问？	查找	操作	备注
HashSet	无序	是	通过键	键：O(1)	O(1)	唯一的无序集合，类似于字典，但键和值是同一个对象。
SortedSet	排序	否	通过键	键：O(log n)	O(log n)	唯一的排序集合，类似于排序字典，但键和值是同一个对象。

注意：

• 连续性？指的是连续的存储？
• 查找指的是查找效率
• 操作指的是操作效率

- Zar Shardan

---

@Svisstack 技术上，在哈希集中的查找是O(m)，其中m是哈希函数的平均哈希冲突率。对于一个完美均匀分布的哈希函数，结果查询是O(1)；对于一个完全糟糕的哈希函数，总会冲突，这将使查询成为O(n)，其中n是集合的大小。通常只使用具有良好哈希函数的类型的哈希集，使其在大多数实际情况下为O(1)。那么是什么让你认为它是O(log(n))? - Servy

@Svisstack https://zh.wikipedia.org/wiki/哈希表 - Zar Shardan

@Svisstack，“你不能假设你的哈希函数是好的”。 好吧，你可以。 实际上大多数人都这样做。 如果您不能正确地哈希对象，则不应在基于哈希的集合中使用它。 有些人会在该注释上加上一个星号，以表示它假定具有良好哈希，因为您是对的，即使它是有效的假设，也是表示O（1）时所做的假设。“如果发生碰撞，那么您基本上有了Set” 不，那么你有一个列表。 在其中搜索需要进行线性搜索，其复杂度为O(m)，其中m是哈希桶中的项目数。 - Servy

@Svisstack 非常少的数据结构被设计成在项目数量超过int.MaxValue时仍能正常工作，甚至根本无法正常工作。说如果你有比int.MaxValue多得多的项目，操作不再是O(1)就毫无意义了，因为从一开始就不支持这种用例，所以这不是一个有用的考虑点。像HashSet、List和Dictionary等东西都会彻底崩溃，因为数组不允许那么大，它们都是由一个大数组支持的。 - Servy

@Svisstack "如果我们想要在世界上这样做，只需将一个项目放入哈希集中，您将拥有与将最大随机项目放入同一哈希集中相同的包含时间。" 是的。这是绝对正确的，假设该项目具有良好定义的哈希函数。这就是哈希集的用处所在。检查项目是否在集合中需要大约相同数量的时间，无论集合中的项目数量如何。它对您可以执行此操作的时间有限制（该项目需要高效哈希），但这通常是可以实现的条件。 - Servy

Answer 3

HashSet<T>和SortedSet<T>都实现了接口ISet<T>，这是一种保存唯一元素的数据结构。

它们之间的主要区别在于它们用于存储数据的底层数据结构。 HashSet<T>使用哈希表，而SortedSet<T>使用红黑树，这是一种平衡的二叉树。

使用哈希表的HashSet<T>比SortedSet<T>执行基本操作（即添加、删除、查找）更快，因为HashSet<T>的复杂度为O(1)，这意味着它将独立于输入数据大小在恒定的时间内执行基本操作，而SortedSet<T>的复杂度为log(N)，这意味着它将根据输入的大小以对数方式执行基本操作。例如，如果输入数据的大小是1,000，则程序在10个步骤中执行基本操作，如果是1,000,000，则程序在20个步骤中执行基本操作。

结论：如果您不需要元素被排序，请使用HashSet<T>，否则请使用SortedSet<T>。这意味着使用HashSet<T>是更可取的，除非您需要排序。

- Behnam Mirzabeygi

---

这是该问题下最好的答案。非常有信息量，感谢分享。 - RainCast