144

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

可以用它来代替aList<T>吗？我想 a 的性能HashSet<T>会更好，但我看不到个人访问它的元素。

是否仅用于枚举？

4

11 回答 11

234

重要的事情HashSet<T>就在名称中：它是一个set。您可以对单个集合做的唯一事情是确定其成员是什么，并检查项目是否是成员。

询问您是否可以检索单个元素（例如set[45]）是对集合的概念的误解。没有像集合的第 45 个元素这样的东西。集合中的项目没有排序。集合 {1, 2, 3} 和 {2, 3, 1} 在各个方面都是相同的，因为它们具有相同的成员资格，而成员资格才是最重要的。

迭代 a 有点危险，HashSet<T>因为这样做会对集合中的项目施加顺序。该顺序并不是该集合的真正属性。你不应该依赖它。如果集合中项目的排序对您很重要，则该集合不是集合。

集合非常有限，并且具有独特的成员。另一方面，他们真的很快。

于 2009-08-08T18:09:43.250 回答
113

这是我使用 a 的真实示例HashSet<string>：

我的 UnrealScript 文件语法高亮器的一部分是高亮 Doxygen 样式注释的新功能。我需要能够判断一个@or\命令是否有效，以确定是显示为灰色（有效）还是红色（无效）。我有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>：如果我保持列表排序，我可以使用BinarySearchO(log n) （没有看到上面提到的这个事实）。然而，由于我的有效命令列表是一个永远不会改变的固定列表，这永远不会比简单地更合适......
  • string[]: 同样，Array.BinarySearch给出 O(log n) 性能。如果列表很短，这可能是性能最佳的选择。它的空间开销总是比HashSet、Dictionary或少List。即使使用BinarySearch，它对于大型集也不是更快，但对于小型集，它值得尝试。我的有几百件物品，所以我把它传递了。
于 2009-08-08T18:32:57.507 回答
24

AHashSet<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) 操作（列表是 O(1) 添加，O(1) 通过索引检索，O(n) 查找/消除）。

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

于 2009-08-08T18:54:26.357 回答
15

性能将是选择 HashSet 而不是 List 的一个不好的理由。相反，有什么能更好地捕捉您的意图？如果顺序很重要，那么 Set（或 HashSet）就出局了。如果允许重复，同样如此。但是有很多情况下我们不关心顺序，我们宁愿没有重复 - 这就是你想要一个 Set 的时候。

于 2009-08-07T23:33:56.470 回答
12

HashSet 是通过散列实现的集合。集合是不包含重复元素的值的集合。集合中的值通常也是无序的。所以不，一个集合不能用来替换一个列表（除非你应该首先使用一个集合）。

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

于 2009-08-07T23:30:42.997 回答
11

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

于 2013-04-25T21:15:06.973 回答
6

哈希集最常见的用途可能是查看它们是否包含某个元素，这对它们来说接近 O(1) 操作（假设有足够强的哈希函数），而不是检查是否包含为 O( n) （以及它是 O(log n) 的排序集）。因此，如果您进行大量检查，某个项目是否包含在某个列表中，hahssets 可能会提高性能。如果您只迭代它们，则不会有太大区别（迭代整个集合是 O(n)，与列表相同，并且哈希集在添加项目时会产生更多开销）。

不，你不能索引一个集合，这无论如何都是没有意义的，因为集合不是有序的。如果您添加一些项目，该集合将不记得哪个是第一个，哪个是第二个等等。

于 2009-08-07T23:39:38.487 回答
5

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

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

如果您想知道使用哪个，请注意，使用List<T>where HashSet<T>is apppropiate 并不是最大的错误，尽管它可能会在您的集合中有不需要的重复项时出现问题。更重要的是，查找（项目检索）效率更高——理想情况下O(1)（用于完美的分桶）而不是O(n)时间——这在许多情况下都非常重要。

于 2009-08-07T23:36:54.327 回答
4

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

顾名思义，HashedSet<T>是一种实现集合语义的数据结构。对数据结构进行了优化，以实现集合操作（​​即 Union、Difference、Intersect），这是传统 List 实现无法高效完成的。

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

于 2009-08-07T23:37:46.260 回答
2

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

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

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

于 2018-11-20T13:16:12.747 回答
1

简而言之 - 每当您想使用字典（或 S 是 T 的属性的字典）时，您应该考虑使用 HashSet（或 HashSet + 在 T 上实现 IEquatable，它等同于 S）

于 2009-08-08T01:22:19.527 回答