何时应该使用 HashSet<T> 类型？

Question

何时应该使用 HashSet<T> 类型？

c#.netdata-structureshashset

148

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

是否可以用它来替换List<T>？我想象一个HashSet<T>的性能会更好，但我看不到访问其元素的方式。

它只能用于枚举吗？

- Joan Venge

11个回答

117

这是我使用HashSet<string>的一个真实例子：

我的UnrealScript文件语法高亮器的一项新功能是突出显示Doxygen风格的注释。我需要能够判断@或\命令是否有效，以确定是否将其显示为灰色（有效）或红色（无效）。我有一个包含所有有效命令的HashSet<string>，因此每当我在词法分析器中遇到@xxx令牌时，我使用validCommands.Contains(tokenText)作为O(1)有效性检查。我真的只关心命令在有效命令的集合中的存在与否。让我们看看我面临的其他选择：

Dictionary<string, ?>: 我应该使用什么类型作为值？这个值是无意义的，因为我只会使用ContainsKey。注意：在.NET 3.0之前，这是O(1)查找的唯一选择 - HashSet<T>是在3.0中添加的，并扩展为实现ISet<T>用于4.0。
List<string>: 如果我保持列表排序，我可以使用BinarySearch，这是O(log n)(上面没有提到这个事实)。然而，由于我的有效命令列表是一个固定的列表，永远不会更改，这永远不会比简单地......更合适。
string[]: 再次，Array.BinarySearch提供O(log n)的性能。如果列表很短，这可能是最佳的性能选项。它总是比HashSet，Dictionary或List具有更少的空间开销。即使使用了BinarySearch，它也不会比大型集合更快，但对于小型集合来说，值得尝试。我的有几百个项目，所以我放弃了这个选项。

- Sam Harwell

26

一个 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) 添加，O(1) 通过索引检索，O(n) 查找/删除）。

可以将 HashSet 的行为与仅将键作为值添加/删除并忽略字典值本身的 Dictionary<TKey,TValue> 进行比较。您预期字典中的键不具有重复值，这就是“Set”部分的重点。

- Kenan E. K.

17

性能不是选择 HashSet 而非 List 的好理由。相反，更好地捕捉您的意图的是什么？如果顺序很重要，则 Set（或 HashSet）不适用。如果允许重复项，则同样如此。但有很多情况我们不关心顺序，并且宁愿没有重复 - 这就是您需要集合的时候。

- Carl Manaster

22

“以性能为理由选择 HashSet 而不是 List 是一个不好的选择”，我不同意你的看法。这就好像说选择 Dictionary 而不是两个 Lists 并不能提高性能一样。请参考以下文章。 - Oscar Mederos

11

@Oscar：我没有说集合不快 - 我说这不是选择它们的好基础。如果你想要表示一个有序集合，使用集合就行不通，试图强制塞入会是一个错误；如果你想要一个没有顺序的集合，那么集合是完美的 - 也很快。但重要的是首先回答第一个问题：你想要表示什么？ - Carl Manaster

2

但是想一想。如果你想不断检查给定的字符串是否是某个包含10,000个字符串的集合的成员，从技术上讲，string[].Contains和HashSet<string>.Contains同样能够表达你的意图；选择HashSet的原因是它运行速度更快。 - Casey

12

HashSet会用于删除IEnumerable集合中的重复元素。例如，

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"}。

- Thomas.Benz

12

HashSet 是一种使用哈希实现的集合，它是一个不包含重复元素的值的集合。集合中的元素通常也是无序的。所以，除非您应该使用集合，否则不能用集合来替换列表。

如果你想知道什么时候使用集合比较好：任何你想要去掉重复元素的地方都可以使用集合。举个稍微牵强的例子，假设你有一个包含 10,000 个软件项目修订版本的列表，你想知道有多少人贡献了这个项目。你可以使用一个 Set<string> 遍历这个修订版本的列表，并将每个修订版本的作者添加到集合中。遍历完成后，集合的大小就是你要找的答案。

- earl

但是Set不允许检索单个元素吗？比如set[45]？ - Joan Venge

2

为此，您需要迭代集合中的成员。其他典型操作包括检查集合是否包含元素或获取集合的大小。 - earl

6

可能最常用的哈希集合用途是查看它们是否包含某个元素，对于哈希集合来说，这是接近O(1)的操作（假设哈希函数足够强大），而对于列表来说，包含检查是O(n)（对于排序集合则为O(log n)）。因此，如果您经常进行检查，以确定某个项目是否包含在某个列表中，则哈希集合可能会提高性能。如果您只是遍历整个集合，差别不大（遍历整个集合的时间复杂度为O(n)，与列表相同，但哈希集合在添加项目时具有更多的开销）。

另外，不能索引集合，这也没有意义，因为集合没有顺序。如果添加了一些项目，集合将不会记住哪一个是第一个，哪一个是第二个等等。

- sepp2k

如果你只是遍历它们，那么与List相比，HashSet方法会增加相当多的内存使用量。 - SamuelWarren

5

HashSet<T>是.NET框架中的一种数据结构，可以将数学集合表示为一个对象。在这种情况下，它使用哈希码（每个项的GetHashCode结果）来比较集合元素的相等性。

与列表不同，集合只允许包含相同元素的一个实例。如果您尝试添加第二个相同的元素，HashSet<T>将只返回false。实际上，由于内部数据结构只是一个哈希表，因此查找元素非常快（O(1)时间）。

如果您想知道应该使用哪个，请注意，使用List<T>而适当使用HashSet<T>并不是最大的错误，尽管它可能会导致不希望在集合中出现的重复项问题。更重要的是，查找（项检索）效率更高 - 理想情况下为O(1)（对于完美分桶），而不是O(n)时间 - 这在许多场景中非常重要。

- Noldorin

1

将现有项目添加到集合中不会引发异常。Add方法只会返回false。另外：从技术上讲，哈希查找的时间复杂度是O(n)，而不是O(1)，除非你有一个完美的哈希函数。当然，在实践中，除非哈希函数真的很糟糕，否则你可以假设它是O(1)。 - sepp2k

1

@sepp2k：是的，它返回一个布尔值...关键是，它会通知你。如果你的桶分配糟糕，哈希查找的最坏情况复杂度是O(n)，但一般情况下更接近于O(1)。 - Noldorin

4

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

正如名称所示，HashedSet<T>是实现集合语义的数据结构。该数据结构被优化以实现集合操作（即联合、差异、交集），这些操作不能像传统的List实现那样高效地完成。

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

- Steve Guidi

2

另一个注意点：集合通常只允许包含一个元素的出现。 - Steve Guidi

2

在基本的预期场景中，HashSet<T>应该用于当您希望执行两个集合的更具体的集合操作而LINQ提供的方法像Distinct，Union，Intersect和Except在大多数情况下已经足够了。但是有时候你可能需要更细粒度的操作，HashSet<T>提供以下方法：

UnionWith
IntersectWith
ExceptWith
SymmetricExceptWith
Overlaps
IsSubsetOf
IsProperSubsetOf
IsSupersetOf
IsProperSubsetOf
SetEquals

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

- c_buk

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Robert Rossney · Accepted Answer

HashSet<T>的重要之处就在于它的名字：它是一个集合。使用单个集合，您只能确定它的成员，并检查某个项是否是成员。

询问是否可以检索单个元素（例如set[45]）会误解了集合的概念。集合中不存在第45个元素。集合中的项没有顺序。集合{1, 2, 3}和{2, 3, 1}在每个方面都是相同的，因为它们具有相同的成员资格，而成员身份是唯一重要的。

在HashSet<T>上进行迭代有些危险，因为这样做会对集合中的项进行排序。该排序实际上并不是集合的属性，您不应该依赖它。如果一个集合中项的排序对您很重要，那么该集合就不是一个集合。

集合非常受限且其成员都是唯一的。另一方面，它们非常快速。