我在哪里可以了解各种类型的.NET列表？

Question

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

例如,List,Hashtable,Dictionaries等.

我不知道什么时候应该使用什么.

Answer 1

这些都不是所有列表,尽管它们都是集合.这是一个快速摘要.

非泛型集合(API是根据object.值类型被加框.

这些主要位于System.Collections命名空间中:

• ArrayList:由数组支持的项列表.快速随机读/写访问.如果缓冲区不需要调整大小,请快速添加到尾端.
• Hashtable:从键到值的映射.键是唯一的,值不一定.使用GetHashCode方法实现近O(1)读/写访问(除了令人讨厌的情况,其中所有项具有相同的哈希,或者后备存储需要重建).迭代键/值对会产生不可预测的顺序.(好吧,实际上是不可预测的.)
• SortedList:与Hashtable类似,但条目始终按按键排序返回.存储为键/值对列表.
• Stack:后进先出的集合
• 队列:先进先出的集合
• 数组:固定大小的O(1)随机访问; 非通用的,但也有强类型的形式

通用集合.(强类型API,不会对框值类型(假设合适的T).

这些主要位于System.Collections.Generic命名空间中:

• List <T>:与ArrayList类似
• 字典<TKey,TValue>:喜欢Hashtable
• SortedList <TKey,TValue>:与SortedList一样
• SortedDictionary <TKey,TValue>:与SortedList类似,但存储为键/值对树,在许多情况下提供更好的性能.有关详细信息,请参阅文档.
• LinkedList <T>:双链表(快速访问头尾)
• Stack <T>:像Stack一样
• 队列<T>:像队列一样
• ReadOnlyCollection <T>:与List <T>类似,但提供只读视图

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

Answer 2

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

一个简短的解释:

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

通常,您应该将通用集合用于几乎所有在.NET 2.0及更高版本中执行的操作.您将获得完全的类型安全性(与例如ArrayList和HashTable相比),与非泛型onces相比,它们对于值类型(整数,结构,浮点数等)要快得多.

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

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

Answer 3

为了阐述tobsen的早期答案,C5通用馆藏图书馆拥有大量的收藏品.我将在这里描述一些:

队列/堆栈

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

清单

注意:ArrayList并且LinkedList还可以用作队列/堆栈

• ArrayList<T>:类似于其在对应System.Collections.Generic (SCG),List<T>这是由数组支持,以保证Ô(1)的索引,但最坏情况Ö(Ñ)插入.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的真实,Add,Remove,Insert,不工作Sort,Shuffle以及Reverse但是这样做,因为他们是就地运营).

列表还提供"视图"功能,该功能表示基础列表的一部分,允许执行本地操作.使用C5书中提供的模式,可以使用在阵列和链表上都高效的视图来执行操作.也可以对视图执行任何列表操作,将其效果限制为基础列表的子集.

排序集合

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

二者TreeSet<T>并TreeBag<T>提供有效地使"快照"的能力或在树的持久副本Ô(1),允许迭代在快照而修改基础树.请注意,树上的每个快照都会对树的更新添加性能损失,但在处理快照时这些影响会消失.

哈希集合

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

优先级队列

• IntervalHeap<T>:提供优先级队列.查找最大值和最小值是O(1)操作,删除最大值,最小值,添加和更新是O(log n)操作.通过显式存储它们(而不是通过计数)允许重复.

字典

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

守卫的收藏品

同样,C5还提供"防护"集合,它有效地充当只读包装器,防止集合被修改.仍可以修改集合中的项目,但不能添加,删除或插入项目.

一个很长的答案,但彻底的C5库各种收藏品随时可用.我发现C5库很棒并经常在我自己的代码中使用它,用以下代码替换常见的C#头:

using C5;
using SCG = System.Collections.Generic;

Answer 4

哈希地图

• 字典
• Hashtable(非泛型)

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

随机访问列表

• 名单
• ArrayList(非泛型)

随机访问列表用于存储要随机访问的长对象列表(即,您希望在O(1)时间内访问第n个元素).如果你想在列表中间插入/删除元素是不好的,因为这需要整个列表被洗牌,这可能需要一些时间.

链接列表和类似

• 链表
• 队列
• 堆

如果您不想访问中间的元素,链接列表是很好的,因为这将花费O(N)时间.如果你想在中间插入/删除元素,这很好,因为它只涉及改变一些指针.

队列和堆栈略微专业化,因为它们针对FIFO和FILO行为进行了优化(先进先出和先进先出).