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

Question

我正在探索这种HashSet<T>类型,但我不明白它在收藏中的位置.

可以用它来代替List<T>吗？我认为a的表现HashSet<T>会更好,但我看不到个人对其元素的访问.

它只用于枚举吗？

Answer 1

重要的HashSet<T>是在名称中:它是一组.您可以使用单个集合做的唯一事情是确定其成员是什么,并检查项目是否是成员.

询问你是否可以检索单个元素(例如set[45])是误解集合的概念.没有集合中的第45个元素.集合中的项目没有排序.集合{1,2,3}和{2,3,1}在各方面都是相同的,因为它们具有相同的成员资格,并且成员资格是最重要的.

迭代a有点危险,HashSet<T>因为这样做会对集合中的项目施加顺序.该订单实际上不是该集合的属性.你不应该依赖它.如果对集合中的项目进行排序对您很重要,则该集合不是一个集合.

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

Answer 2

这是我使用的地方的一个真实示例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,对于大型套装来说,它并不快,但对于小型套装来说,它值得尝试.我的有几百个项目,所以我传递了这个.

Answer 3

A 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 /去掉).

可以将HashSet的行为与Dictionary<TKey,TValue>仅使用添加/删除键作为值进行比较,并忽略字典值本身.您可能希望字典中的键不具有重复值,这就是"Set"部分的要点.

Answer 4

性能是选择HashSet over List的一个不好的理由.相反,有什么更好地捕捉你的意图？如果顺序很重要,那么Set(或HashSet)就会出局.如果允许重复,同样.但是在很多情况下我们不关心秩序,而且我们宁愿没有重复 - 那就是你想要一套.

Answer 5

HashSet是由散列实现的集合.集合是不包含重复元素的值的集合.集合中的值通常也是无序的.所以不,一个集合不能用于替换列表(除非你首先应该使用一个集合).

如果你想知道一个集合可能有什么用处:你想要摆脱重复的地方,显然.作为一个有点人为的例子,假设您有一个包含10,000个软件项目修订版的列表,并且您想知道有多少人为该项目做出了贡献.您可以使用a Set<string>并迭代修订列表,并将每个修订版的作者添加到集合中.完成迭代后,集合的大小就是您要寻找的答案.

Answer 6

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

Answer 7

对于散列集最常见的用途可能是看它们是否包含某个元素,它接近于它们的O(1)操作(假设具有足够强的散列函数),而不是检查包含为O的列表( n)(以及它为O(log n)的有序集合).因此,如果您进行了大量检查,某个项目是否包含在某个列表中,则hahssets可能会提高性能.如果你只是迭代它们,那就不会有太大的区别(整个集合的迭代是O(n),与列表和hashsets相同,在添加项目时会有更多的开销).

不,你不能索引一个集合,无论如何都没有意义,因为集合没有被排序.如果您添加一些项目,该集合将不会记住哪一个是第一个,哪个是第二个等.

Answer 8

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

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

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