我正在探索这种HashSet<T>
类型,但我不明白它在集合中的位置。
可以用它来代替aList<T>
吗?我想 a 的性能HashSet<T>
会更好,但我看不到个人访问它的元素。
是否仅用于枚举?
我正在探索这种HashSet<T>
类型,但我不明白它在集合中的位置。
可以用它来代替aList<T>
吗?我想 a 的性能HashSet<T>
会更好,但我看不到个人访问它的元素。
是否仅用于枚举?
重要的事情HashSet<T>
就在名称中:它是一个set。您可以对单个集合做的唯一事情是确定其成员是什么,并检查项目是否是成员。
询问您是否可以检索单个元素(例如set[45]
)是对集合的概念的误解。没有像集合的第 45 个元素这样的东西。集合中的项目没有排序。集合 {1, 2, 3} 和 {2, 3, 1} 在各个方面都是相同的,因为它们具有相同的成员资格,而成员资格才是最重要的。
迭代 a 有点危险,HashSet<T>
因为这样做会对集合中的项目施加顺序。该顺序并不是该集合的真正属性。你不应该依赖它。如果集合中项目的排序对您很重要,则该集合不是集合。
集合非常有限,并且具有独特的成员。另一方面,他们真的很快。
这是我使用 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>
:如果我保持列表排序,我可以使用BinarySearch
O(log n) (没有看到上面提到的这个事实)。然而,由于我的有效命令列表是一个永远不会改变的固定列表,这永远不会比简单地更合适......string[]
: 同样,Array.BinarySearch
给出 O(log n) 性能。如果列表很短,这可能是性能最佳的选择。它的空间开销总是比HashSet
、Dictionary
或少List
。即使使用BinarySearch
,它对于大型集也不是更快,但对于小型集,它值得尝试。我的有几百件物品,所以我把它传递了。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>
仅添加/删除键作为值,并忽略字典值本身。您会期望字典中的键没有重复值,这就是“设置”部分的重点。
性能将是选择 HashSet 而不是 List 的一个不好的理由。相反,有什么能更好地捕捉您的意图?如果顺序很重要,那么 Set(或 HashSet)就出局了。如果允许重复,同样如此。但是有很多情况下我们不关心顺序,我们宁愿没有重复 - 这就是你想要一个 Set 的时候。
HashSet 是通过散列实现的集合。集合是不包含重复元素的值的集合。集合中的值通常也是无序的。所以不,一个集合不能用来替换一个列表(除非你应该首先使用一个集合)。
如果您想知道一个集合可能有什么好处:显然,您想摆脱重复的任何地方。作为一个稍微人为的例子,假设您有一个软件项目的 10.000 个修订的列表,并且您想找出有多少人为该项目做出了贡献。您可以使用 aSet<string>
并遍历修订列表并将每个修订的作者添加到集合中。完成迭代后,集合的大小就是您要寻找的答案。
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"};
哈希集最常见的用途可能是查看它们是否包含某个元素,这对它们来说接近 O(1) 操作(假设有足够强的哈希函数),而不是检查是否包含为 O( n) (以及它是 O(log n) 的排序集)。因此,如果您进行大量检查,某个项目是否包含在某个列表中,hahssets 可能会提高性能。如果您只迭代它们,则不会有太大区别(迭代整个集合是 O(n),与列表相同,并且哈希集在添加项目时会产生更多开销)。
不,你不能索引一个集合,这无论如何都是没有意义的,因为集合不是有序的。如果您添加一些项目,该集合将不记得哪个是第一个,哪个是第二个等等。
HashSet<T>
是 .NET 框架中的一种数据结构,能够将数学集表示为对象。在这种情况下,它使用哈希码(GetHashCode
每个项目的结果)来比较集合元素的相等性。
集合与列表的不同之处在于它只允许其中包含的相同元素出现一次。如果您尝试添加第二个相同的元素,HashSet<T>
它将返回。false
事实上,元素的查找非常快(O(1)
时间),因为内部数据结构只是一个哈希表。
如果您想知道使用哪个,请注意,使用List<T>
where HashSet<T>
is apppropiate 并不是最大的错误,尽管它可能会在您的集合中有不需要的重复项时出现问题。更重要的是,查找(项目检索)效率更高——理想情况下O(1)
(用于完美的分桶)而不是O(n)
时间——这在许多情况下都非常重要。
List<T>
用于存储有序的信息集。如果您知道列表元素的相对顺序,您可以在恒定时间内访问它们。但是,要确定元素在列表中的位置或检查它是否存在于列表中,查找时间是线性的。另一方面,HashedSet<T>
不保证存储数据的顺序,因此为其元素提供恒定的访问时间。
顾名思义,HashedSet<T>
是一种实现集合语义的数据结构。对数据结构进行了优化,以实现集合操作(即 Union、Difference、Intersect),这是传统 List 实现无法高效完成的。
因此,选择使用哪种数据类型实际上取决于您尝试对应用程序执行的操作。如果您不关心元素在集合中的排序方式,而只想枚举或检查是否存在,请使用HashSet<T>
. 否则,请考虑使用List<T>
或其他合适的数据结构。
HashSet<T>
当您希望对两个集合进行比 LINQ 提供的更具体的集合操作时,应在基本预期场景中使用。LINQ 方法,如,Distinct
和在大多数情况下就足够了,但有时您可能需要更细粒度的操作,并提供:Union
Intersect
Except
HashSet<T>
UnionWith
IntersectWith
ExceptWith
SymmetricExceptWith
Overlaps
IsSubsetOf
IsProperSubsetOf
IsSupersetOf
IsProperSubsetOf
SetEquals
LINQ 和“重叠”方法之间的另一个区别HashSet<T>
是 LINQ 总是返回一个 new IEnumerable<T>
,并且HashSet<T>
方法会修改源集合。
简而言之 - 每当您想使用字典(或 S 是 T 的属性的字典)时,您应该考虑使用 HashSet(或 HashSet + 在 T 上实现 IEquatable,它等同于 S)