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

StackOverflow https://stackoverflow.com/questions/1247442

题

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

可以用它来代替 List<T>？我想象一个的表现 HashSet<T> 变得更好，但我看不到个人对其元素的访问。

仅仅是为了枚举吗？

有帮助吗？

解决方案

重要的是关于 HashSet<T> 就在名字中：它是 放. 。您可以对单个集合执行的唯一操作是确定其成员是什么，并检查某个项目是否是成员。

询问是否可以检索单个元素（例如 set[45]）是对集合概念的误解。集合中不存在第 45 个元素。集合中的项目没有顺序。集合 {1, 2, 3} 和 {2, 3, 1} 在各个方面都是相同的，因为它们具有相同的隶属关系，而隶属关系才是最重要的。

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

套装数量非常有限，而且成员也很独特。另一方面，它们的速度确实很快。

其他提示

这是我使用的真实示例 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, ，对于大型集合来说它并不更快，但是对于小型集合来说值得尝试。不过我的有几百件，所以我就放弃了。

一个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>通过仅添加/移除的键作为值，并忽略字典值本身。你希望在一个字典键不要有重复的值，这是“设置”部分的点。

性能将是一个不好的理由去选择HashSet的名单上。相反，有什么更好的抓住你的意图是什么？如果顺序很重要，然后设置（或HashSet的）已经出来了。如果重复是允许的，也是这样。但也有很多的情况下，当我们不关心秩序，我们宁愿没有重复 - 这是当你想要一个集

。

HashSet的是设置通过散列来实现。一组是不包含重复的元素的值的集合。在设置的值通常也是无序的。所以，不，一组不能用来代替名单（除非你应该已经摆在首位使用一组）。

如果你想知道什么是集可能是很好的：任何你想摆脱重复的，很明显。作为一个稍微做作的例子，假设你有一个软件项目10.000修改的列表，并且你想找出有多少人促成了该项目。你可以使用一个Set<string>和迭代的版本列表和每个修订的作者添加到该集合。一旦你完成迭代，集合的大小是你要找的答案。

的HashSet将用于删除重复元素的集合IEnumerble英寸例如，

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

大概为hashsets最常见的用途是，看它们是否包含某个元素，这是接近的O（1）为它们的操作（假定足够强的散列函数），而不是用于其检查包含列表为O（n）（和排序集合为它是O（log n）的）。所以，如果你做了很多检查，项目是否被包含在某一列表，hahssets可能会提高性能。如果你永远只能在它们之间迭代，不会有太大的差别（在整套迭代是O（n），同样与列表和hashsets在添加项目时，有些更多的开销）。

不，你不能索引集，这是没有意义的，无论如何，因为集是没有顺序的。如果你添加一些项目，设置会不记得哪一个是第一，和第二等。

List<T>用于存储有序集的信息。如果你知道列表的元素的相对顺序，可以在固定时间访问它们。然而，以确定一个元素位于列表或检查它是否在列表，则查找时间是线性的。在另一方面，HashedSet<T>不作任何所存储的数据的顺序的保证，因此提供了一种用于其的元件常数的访问时间。

顾名思义，HashedSet<T>是实现设置语义的数据结构。该数据结构被优化，以实现一组操作（即联合，差异，相交），其不能与传统的目录实现作为有效地进行。

所以，要选择真正使用的数据类型取决于你正在尝试与你的应用程序执行。如果你不关心你的元素是如何集合中的排序，并只希望enumarate或检查存在，使用HashSet<T>。否则，考虑使用List<T>或另一合适的数据结构中。

HashSet<T>在.NET框架中的数据strucutre这是一个能表示数学设置作为对象。在这种情况下，它使用的散列码（每个项目的GetHashCode结果）来比较组元素平等。

一个组从列表不同之处在于它仅允许包含在其内的相同元件的一个发生。 HashSet<T>只返回false如果您尝试添加第二个相同的元素。实际上，元件的查找非常快（O(1)时间），由于内部数据结构仅仅是一个哈希表。

如果你想知道使用哪个，请注意，使用List<T>其中HashSet<T>是appropiate是不是最大的错误，虽然它可能会允许你在哪儿集合中的不良重复的项目问题。更重要的是，查找（项目检索）是大大更有效 - 理想O(1)（完美装桶），而不是O(n)时间 - 这是很重要的，很多情况下

在短 - 无论何时您倾向于使用词典（或一个字典，其中S是T的属性），则你应该考虑一个HashSet（或HashSet的+对T这相当于在S实施IEquatable）

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

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

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

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top