什么时候应该使用 HashSet < T > 类型？

我正在探索 HashSet<T>类型，但我不明白它在集合中的位置。

可以用它来代替 List<T>吗？我认为 HashSet<T>的性能会更好，但是我看不到单独访问它的元素。

它只是用于枚举吗？

96483 次浏览
小开

HashSet 是通过散列实现的 准备好了。集合是不包含重复元素的值的集合。集合中的值通常也是无序的。因此，不能使用集合来替换列表(除非您一开始就应该使用集合)。

如果你想知道什么是一套可能是好的: 任何地方，你想摆脱重复，显然。作为一个稍微做作的示例，假设您有一个软件项目的10.000个修订版本的列表，并且您希望了解有多少人为该项目做出了贡献。您可以使用 Set<string>并迭代修订列表，然后将每个修订的作者添加到集合中。一旦您完成了迭代，集合的大小就是您所寻找的答案。

小开

性能是选择 HashSet 而不是 List 的一个不好的理由。相反，还有什么能更好地抓住你的意图呢？如果顺序很重要，那么 Set (或 HashSet)就出局了。如果允许重复，同样地。但有很多情况下，我们不在乎顺序，我们宁愿没有重复-这就是你想要一套。

小开

中的数据结构。NET 框架，该框架能够将 数学模型表示为对象。在这种情况下，它使用散列码(每个项的 GetHashCode结果)来比较集合元素的相等性。

集合与列表的不同之处在于，它只允许其中包含的相同元素出现一次。如果您尝试添加第二个相同的元素，HashSet<T>将返回 false。事实上，元素的查找非常快(O(1)时间) ，因为内部数据结构只是一个散列表。

如果您想知道使用哪一个，请注意，在适合使用 HashSet<T>的地方使用 List<T>并不是最大的错误，尽管它可能会导致在您的集合中存在不需要的重复项时出现问题。更重要的是，查找(项目检索)是非常有效的-理想的 O(1)(为完美桶)而不是 O(n)时间-这是相当重要的在许多情况下。

小开

List<T>用于存储有序的信息集。如果知道列表元素的相对顺序，就可以在常量时间内访问它们。但是，要确定元素在列表中的位置或检查它是否存在于列表中，查找时间是线性的。另一方面，HashedSet<T>不保证存储数据的顺序，因此为其元素提供常量访问时间。

顾名思义，HashedSet<T>是实现 设置语义的数据结构。数据结构被优化以实现集合操作(即联合、差异、交叉) ，而传统的 List 实现不能有效地完成这些操作。

因此，选择使用哪种数据类型实际上取决于您试图对应用程序做什么。如果不关心元素在集合中的排序方式，只想枚举或检查是否存在，请使用 HashSet<T>。否则，考虑使用 List<T>或其他合适的数据结构。

小开

哈希集最常见的用途可能是查看它们是否包含某个元素，这个元素对它们来说接近于 O (1)操作(假设有一个足够强大的哈希函数) ，而不是检查包含是 O (n)的列表(以及检查包含是 O (log n)的排序集)。因此，如果进行大量检查，确定某个项是否包含在某个列表中，那么哈希集可能是性能改进。如果只对它们进行迭代，则不会有太大区别(对整个集进行迭代是 O (n) ，与添加项时列表和哈希集的开销相同)。

不，你不能索引一个集合，这是没有任何意义的，因为集合不是有序的。如果你添加了一些项目，集合不会记得哪个是第一个，哪个是第二个等等。

小开

简而言之，任何时候你想使用一个字典(或者字典中 S 是 T 的属性) ，那么你应该考虑一个 HashSet (或者 HashSet + 在 T 上实现等价于 S 的 IEqutable)

小开
最佳答案

关于 HashSet<T>最重要的一点就在于它的名字: 它是一个 准备好了。对于单个集合，您唯一可以做的事情就是确定其成员是什么，并检查某个项是否为成员。

询问是否可以检索单个元素(例如 set[45])是对集合概念的误解。根本没有第45个元素这回事。集合中的项没有顺序。集合{1,2,3}和{2,3,1}在每个方面都是相同的，因为它们具有相同的成员资格，而成员资格是最重要的。

在 HashSet<T>上迭代有些危险，因为这样做会对集合中的项强加一个顺序。该顺序实际上不是集合的属性。你不应该依赖它。如果集合中的项的顺序对您很重要，则该集合不是集合。

集合是非常有限的，并且有唯一的成员。另一方面，它们真的很快。

小开

下面是我使用 HashSet<string>的一个实际例子:

我的 UnrealScript 文件语法高亮显示器的一部分是 突出 Doxy- 风格的评论的一个新特性。我需要能够告诉如果 @或 \命令是有效的，以确定是否显示为灰色(有效)或红色(无效)。我拥有所有有效命令的 HashSet<string>，因此每当我在 lexer 中命中一个 @xxx令牌时，我都使用 validCommands.Contains(tokenText)作为 O (1)有效性检查。除了有效命令 准备好了中命令的 存在之外，我真的不关心其他任何事情。让我们看看我面临的选择:

  • Dictionary<string, ?>: 值使用什么类型？这个值是没有意义的，因为我将使用 ContainsKey。注:。NET 3.0这是 O (1)查找的唯一选择-HashSet<T>是为3.0添加的，并扩展到为4.0实现 ISet<T>。
  • List<string>: 如果我保持列表排序，我可以使用 BinarySearch，它是 O (logn)(没有看到上面提到的这个事实)。但是，由于我的有效命令列表是一个永远不会更改的固定列表，因此这将永远不会比简单地..。
  • string[]: 同样，Array.BinarySearch提供 O (log n)性能。如果列表很短，这可能是性能最好的选项。它总是比 HashSet、 Dictionary或 List的空间开销小。即使使用 BinarySearch，对于大型机来说它也不会更快，但是对于小型机来说它值得一试。我的有几百个项目，所以我把这个。
小开

HashSet<T>实现 ICollection<T>接口:

public interface ICollection<T> : IEnumerable<T>, IEnumerable
{
// Methods
void Add(T item);
void Clear();
bool Contains(T item);
void CopyTo(T[] array, int arrayIndex);
bool Remove(T item);


// Properties
int Count { get; }
bool IsReadOnly { get; }
}

List<T>实现 IList<T>，它扩展了 ICollection<T>

public interface IList<T> : ICollection<T>
{
// Methods
int IndexOf(T item);
void Insert(int index, T item);
void RemoveAt(int index);


// Properties
T this[int index] { get; set; }
}

HashSet 设置了语义，通过内部的散列表实现:

集合是一个集合，其中不包含 重复的元素，以及它们的元素 没有特别的顺序。

如果丢失了索引/位置/列表行为，HashSet 会得到什么？

从 HashSet 中添加和检索项总是由对象本身完成，而不是通过索引器，并且接近 O (1)操作(List 是 O (1) add，O (1)通过索引检索，O (n) find/delete)。

HashSet 的行为可以与使用 Dictionary<TKey,TValue>进行比较，只添加/删除键作为值，忽略字典值本身。您希望字典中的键没有重复的值，这就是“设置”部分的要点。

小开

HashSet 将用于删除 IEnumable 集合中的重复元素,

List<string> duplicatedEnumrableStrings = new List<string> {"abc", "ghjr", "abc", "abc", "yre", "obm", "ghir", "qwrt", "abc", "vyeu"};
HashSet<string> uniqueStrings = new HashSet(duplicatedEnumrableStrings);

在这些代码运行之后，uniqueStrings 保存{“ abc”、“ ghjr”、“ yre”、“ obm”、“ qwrt”、“ vyeu”} ;

小开

在基本的预期场景中，当您希望对两个集合进行比 LINQ 提供的更具体的集合操作时，应该使用 HashSet<T>。在大多数情况下，像 Distinct、 Union、 Intersect和 Except这样的 LINQ 方法就足够了，但有时可能需要更细粒度的操作，而 HashSet<T>提供:

  • UnionWith
  • IntersectWith
  • ExceptWith
  • SymmetricExceptWith
  • Overlaps
  • IsSubsetOf
  • IsProperSubsetOf
  • IsSupersetOf
  • IsProperSubsetOf
  • SetEquals

LINQ 和 HashSet<T>“重叠”方法的另一个区别是，LINQ 总是返回一个新的 IEnumerable<T>，而 HashSet<T>方法修改源集合。


提交答案