Dotnet 算法与数据结构：Hashset, List 对比

哈希集 A 是存储唯一元素的集合。它通过在内部使用哈希表来实现这一点，该哈希表为基本操作（如添加、删除和包含）提供恒定时间平均复杂度 （O（1））。此外，不允许重复元素，使其成为唯一性至关重要的场景的理想选择。另一方面，表示按顺序存储元素的动态数组。它允许重复元素并提供对元素的索引访问，使其适用于需要具有重复项的有序集合的方案。但是，在 a 中添加、删除和包含等操作的时间复杂度为 O（n），其中 n 是列表中的元素数。性能注意事项会员资格检查和 之间的主要区别之一在于它们在成员资格检查方面的性能。

HashSet

A 是存储唯一元素的集合。它通过在内部使用哈希表来实现这一点，该哈希表为基本操作（如添加、删除和包含）提供恒定时间平均复杂度 （O（1））。此外，不允许重复元素，使其成为唯一性至关重要的场景的理想选择。

List

另一方面，表示按顺序存储元素的动态数组。它允许重复元素并提供对元素的索引访问，使其适用于需要具有重复项的有序集合的方案。但是，在 a 中添加、删除和包含等操作的时间复杂度为 O（n），其中 n 是列表中的元素数。

性能注意事项

会员资格检查

和 之间的主要区别之一在于它们在成员资格检查方面的性能。HashSetList

• HashSet：a 中的成员资格检查在恒定时间复杂度 （O（1）） 下非常有效。这使其成为需要频繁进行存在性检查时的首选。

HashSet<int> hashSet = new HashSet<int>(); hashSet.Add(1); bool contains = hashSet.Contains(1); // O(1) operation

• List

  ：相反，a 需要线性搜索运算 （O（n）） 来检查元素是否存在。这意味着，随着列表大小的增加，成员资格检查所需的时间也会成比例地增加。

List<int> list = new List<int>(); list.Add(1); bool contains = list.Contains(1); // O(n) operation

插入和删除

虽然两者都支持添加和删除元素，但它们的性能特征有很大不同。

• HashSet：在时间复杂度恒定的情况下，插入和删除通常很快 （O（1））。但是，在极少数情况下，当哈希冲突频繁发生时，性能可能会下降到 O（n）。

HashSet<int> hashSet = new HashSet<int>(); hashSet.Add(1); hashSet.Remove(1); // O(1) operation

• List

  ：在 中，列表末尾的插入和删除速度很快，时间复杂度恒定 （O（1））。但是，列表中间或开头的操作需要移动元素，从而导致线性时间复杂度 （O（n））。

List<int> list = new List<int>(); list.Add(1); list.Remove(1); // O(n) operation

内存开销

另一个需要考虑的方面是内存开销，尤其是在处理大量元素时。

• HashSet：在内部，a 使用哈希表来存储元素，这会产生哈希桶和哈希代码的额外内存开销。但是，与存储的元素相比，此开销通常可以忽略不计。

• List

  ：A 消耗的内存与存储的元素数成正比。由于它维护一个连续的内存块，因此当列表达到容量时调整列表的大小可能会导致内存重新分配和元素复制，从而导致额外的开销。

选择正确的数据结构

和 之间的选择取决于应用的具体要求：

• 在以下情况下使用：HashSet

• 元素的独特性至关重要。

• 需要快速会员资格检查。

• 需要有效地插入和删除元素。

• 在以下情况下使用：List<T>

• 有重复的有序收集是可以接受的。

• 对元素的索引访问是必要的。

• 元素的顺序遍历很常见。

文章转载自：Flamesky

原文链接：https://www.cnblogs.com/flamesky/p/18292639

体验地址：http://www.jnpfsoft.com/?from=infoq