29

有没有人知道一个很好的资源来简明地解释 C# 中可用的不同类型的列表以及何时使用它们是合适的？

例如，列表、哈希表、字典等。

我从不太确定什么时候应该使用什么。

4

10 回答 10

32

这些不是所有列表，尽管它们都是集合。这是一个快速的总结。

非泛型集合（API 是根据object. 值类型被装箱的。

这些主要在System.Collections命名空间中：

  • ArrayList：由数组支持的项目列表。快速随机读/写访问。如果缓冲区不需要调整大小，则快速添加到尾端。
  • Hashtable：从键映射到值。键是唯一的，值不必是唯一的。使用 GetHashCode 方法来实现接近 O(1) 的读/写访问（除了所有项目具有相同哈希或后备存储需要重建的恶劣情况）。遍历键/值对会产生不可预测的顺序。（嗯，实际上是不可预测的。）
  • SortedList：与 Hashtable 类似，但条目始终以按键排序的顺序返回。存储为键/值对列表。
  • Stack : 后进先出集合
  • 队列：先进先出集合
  • 数组：固定大小 O(1) 随机访问；非泛型，但也有强类型形式

通用集合。（强类型 API，不会装箱值类型（假设合适的 T）。

这些主要在System.Collections.Generic 命名空间中：

可能最重要的集合接口是IEnumerable（和IEnumerable<T>）。这表示一个项目序列，就像 Stream 表示一个字节序列一样。没有随机访问，只有前向阅读。LINQ to Objects 基于此，几乎所有集合类型都实现了它。

于 2008-10-13T16:13:09.733 回答
7

为了解释 tobsen 之前的回答，C5 Generic Collection Library 有大量的收藏。我将在这里描述其中的一些：

队列/堆栈

  • CircularQueue<T>：此类提供严格的队列和堆栈功能。同样，使用索引器可以有效地O (1) 访问堆栈/队列中的任何项目：（cq[0]其中 0 是最旧的项目，接下来要出列，最后要弹出）。

列表

注意：ArrayList也LinkedList可以用作队列/堆栈

  • ArrayList<T>: 与 , 中的对应物类似，它System.Collections.Generic (SCG)由List<T>数组支持，保证O (1) 索引，但最坏情况下O ( n ) 插入。O ( n ) 找到一个项目。
  • LinkedList<T>: 与其对应的类似SCG.LinkedList<T>。使用双向链表，保证O (1) 插入，但最坏情况O ( n ) 索引（在实践中，与列表头部或尾部的距离成正比）。还要O ( n ) 找到一个项目。排序使用稳定的合并排序。
  • HashedArrayList<T>: 与ArrayList<T>上面类似，但不允许重复。您获得的回报是查找项目及其索引的时间减少到O (1)。
  • HashedLinkedList<T>: 与LinkedList<T>上面类似，但不允许重复。和以前一样，找到一个项目的时间减少到O (1)，但找到它的索引的时间仍然是O ( n )。
  • WrappedArray<T>: 与 非常相似ArrayList<T>，它充当实现 的数组的包装器C5.IList<T>，但如果尝试修改集合 (IsFixedSize为 true 并且Add,不工作; ,Remove和做，但是，因为它们是就地操作）。InsertSortShuffleReverse

列表还提供了一个“查看”功能，它表示底层列表的一部分，允许执行本地操作。使用 C5 书中提供的模式，可以使用对数组和链表都有效的视图来执行操作。任何列表操作也可以在视图上执行，将它们的效果限制在底层列表的子集上。

排序集合

  • SortedArray<T>: 与 an 类似，ArrayList<T>不同之处在于它保持其项目排序并且不允许重复。请注意，此集合上的随机插入和删除速度很慢。如果项目数量很少或很少修改但经常通过项目索引或值访问，则此集合是最好的。
  • TreeSet<T>：使用红黑树结构来保持项目排序。作为一个集合，它不允许重复。通过索引或项目值访问以及插入/删除需要O ( log n )。
  • TreeBag<T>：使用红黑树，保持项目排序。作为一个包，它确实允许重复，但不会在树中存储重复，而是通过计数来保持重复。

两者都TreeSet<T>提供TreeBag<T>了在O (1) 中有效地制作“快照”或树的持久副本的能力，允许在修改底层树的同时对快照进行迭代。请注意，树上的每个快照都会对树的更新增加性能损失，但这些影响会在释放快照后消失。

哈希集合

  • HashSet<T>：使用简单哈希表进行存储的集合。按项目值访问需要O (1)。作为一个集合，它不允许重复。提供一个函数BucketCostDistribution()，可以帮助您确定项目的哈希码函数的效率。
  • HashBag<T>: 与 类似HashSet<T>，但有包语义，表示允许重复，但重复只通过计数存储。

优先队列

  • IntervalHeap<T>：提供优先队列。求最大值和最小值是O (1) 次运算，删除最大值、最小值、添加和更新是O ( logn ) 次运算。通过显式存储它们（而不是通过计数）来允许重复。

字典

  • HashDictionary<H,K>: 类似于, 提供O (1)SCG.Dictionary<H,K>中的条目访问、插入和删除。还提供了如上的功能。不保证任何特定的枚举顺序。BucketCostDistribution()HashSet<T>
  • TreeDictionary<H,K>: 类似于 ,SCG.SortedDictionary<H,K>使用红黑树提供一个持久排序的字典。条目访问、插入和删除需要O ( log n )。保证字典的枚举遵循键比较器指定的顺序。

受保护的集合

同样，C5 还提供“受保护”集合，它有效地充当只读包装器，防止集合被修改。集合中的项目仍然可以修改，但不能添加、删除或插入集合中的项目。

一个很长的答案，但对 C5 库的各种集合供您使用是彻底的。我发现 C5 库很棒，并且经常在我自己的代码中使用它，将常见的 C# 标头替换为：

using C5;
using SCG = System.Collections.Generic;
于 2008-10-16T17:42:11.817 回答
6

你应该拿起一本关于基本数据结构的书。无论语言如何，都是相同的理论。

一个简短的解释：

  • Array: (如在 eg 中int[] myArray) - 可以在集合永不更改时使用的静态数组（您不能添加或删除其中的项目，但您可以更改单个项目的值）
  • ArrayList：通用数组/列表，允许相对快速的枚举以及直接访问。该列表可以在您添加项目时自动增长，但由于它只存储Object，因此由于性能和类型安全问题，您应该很少使用它。
  • List<T>: 上述 ArrayList 的通用版本。它在性能和灵活性之间提供了一个很好的平衡，几乎总是应该在你有一个动态的平面项目列表时使用。（.NET 2.0 中的新功能）
  • Hashtable: 像平面列表一样工作，但不是用整数索引它，而是可以使用任何对象索引。值得注意的是，哈希表中没有“顺序”。
  • Dictionary<T>：哈希表的通用版本。在 .NET 2.0 和更高版本中使用它而不是 Hashtable，原因与上面的 ArrayList 与 List 相同。
  • Stack<T>：提供先进后出类型的列表。您最后添加的物品将是您挑选物品时首先收到的物品。
  • Queue<T>：提供先进先出列表。把它想象成一个管子，你在一端插入物品，从另一端取出它们。通常用于在例如线程之间传递消息。

通常，您应该对在 .NET 2.0 及更高版本中所做的几乎所有事情使用泛型集合。您将获得完整的类型安全性（与例如 ArrayList 和 HashTable 相比），并且与非泛型一次相比，它们对于值类型（整数、结构、浮点数等）要快得多。

如果您有一个永远不会改变的项目列表，或者您不需要/不想要灵活性，List<T>那么您当然可以使用数组，因为它的开销最少。

从公共方法或属性返回集合时，建议将其转换为不太灵活的接口。因此，如果您有一个要返回的 List，您可以将其转换为 an IEnumerable<int>，这意味着您的消费者无法向其中添加项目（当然，除非它将其转换回，但它仍然是对用户的指示）。转换它还可以让您在以后灵活地更改底层数据结构，同时保持 API 稳定性。您还可以选择ICollection<int>或IList<int>公开更多功能，但隐藏实际数据结构。

于 2008-10-13T16:11:58.940 回答
5

哈希图

  • 字典
  • 哈希表（非泛型）

这是一种允许您保留键值对的数据结构。给定具有某种排序方式的键，您可以插入一个值。一个简单的示例可以是学生列表，其中键是学生 ID，值是学生姓名。

随机访问列表

  • 列表
  • ArrayList（非泛型）

随机访问列表用于存储要随机访问的一长串对象（即您想在 O(1) 时间内访问第 n 个元素）。如果您想在列表的中间插入/删除元素，那就不好了，因为这需要整个列表被打乱，这可能需要一些时间。

链表和类似的

  • 链表
  • 队列
  • 堆

如果您不想访问中间的元素，则链接列表非常有用，因为这将花费 O(N) 时间。如果您想在中间插入/删除元素，那就太好了，因为它只涉及更改几个指针。

队列和堆栈稍微专业化，因为它们针对 FIFO 和 FILO 行为（分别为先进先出和先进先出）进行了优化。

于 2008-10-13T16:11:29.877 回答
2

如果您从System.Collections 的 MSDN 文档开始，您可以深入了解各个集合类型，以获取有关这些“列表”以及如何使用它们的更多详细信息。例如，doco forHashtable说：“表示基于键的哈希码组织的键/值对的集合。”

在理解泛型中也有一个很好的 System.Collections.Generic 讨论。

于 2008-10-13T15:59:44.940 回答
2

List<T> 是可排序的，但不建议公开。

Collection<T> 是一个基本的、没有多余装饰的集合。

Dictionary<T> 是键值对的集合（很像旧的哈希表，但现在是通用的）。

KeyedCollection<T> 是一个字典，可以从值中确定键（这是一个抽象，所以你必须继承它并支持GetKey函数）

ReadOnlyCollection<T> 是一个不能修改内容的特殊集合。

从 .NET 2.0 开始，ArrayList 和 HashTable 基本上已经过时。

于 2008-10-13T16:05:56.817 回答
2

除了到目前为止的出色答案之外，还有一些可以通过C5 Generic Collection Library获得的 Collections 。在根据您的要求决定使用什么时，文档（也在他们的网站上）可能会有所帮助。

于 2008-10-13T19:07:34.967 回答
1

MSDN 有一篇名为Selecting a Collection Class的文章，我发现在尝试找出在给定情况下使用哪种集合时非常有用。

于 2009-05-04T14:59:41.813 回答
0

这些是各种类型的通用数据结构的示例。这些数据结构在软件工程中无处不在。

于 2008-10-13T16:00:59.230 回答
-3

System.collections.Generic.如果您只是在代码窗口中键入，Intellisense 会向您显示每个的简短描述。不要忘记尾随句点。哦，还有System.Collections.ObjectModel.。从那里您应该能够从 MSDN 获得有关任何看起来很有希望的信息的更多信息。

于 2008-10-13T16:00:10.620 回答