C#中集合数据类型的比较
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/995766/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Comparison of collection datatypes in C#
提问by Joel in G?
Does anyone know of a good overview of the different C# collection types? I am looking for something showing which basic operations such as Add, Remove, RemoveLastetc. are supported, and giving the relative performance.
有谁知道对不同 C# 集合类型的一个很好的概述？我在寻找的东西显示这如基本的操作Add，Remove，RemoveLast等的支持，并给予相对性能。
It would be particularly interesting for the various generic classes - and even better if it showed eg. if there is a difference in performance between a List<T>where Tis a class and one where Tis a struct.
对于各种泛型类，它会特别有趣 - 如果它显示例如。如果List<T>whereT是一个类和一个 whereT是结构之间的性能存在差异。
A start would be a nice cheat-sheet for the abstract data structures, comparing Linked Lists, Hash Tables etc. etc. Thanks!
对于抽象数据结构，比较链表，哈希表等等，开始将是一个不错的备忘单。谢谢！
采纳答案by Benjamin Dobell
The following content was originally taken from MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc(but the link has since died).
以下内容最初取自 MSDN http://xbox.create.msdn.com/downloads/?id=123&filename=DataStructures_CheatSheet.doc（但该链接已失效）。
As in the image above, the content was originally provided as a table (which StackOverflow doesn't support).
如上图所示，内容最初以表格形式提供（StackOverflow 不支持）。
Given an image isn't easily indexed below is a somewhat crude programmatic conversion of the information to lists:
鉴于图像不容易在下面编入索引，这是信息到列表的某种粗略的编程转换：
Array
大批
- add to end:
O(n) - remove from end:
O(n) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes:Most efficient use of memory; use in cases where data size is fixed.
- 添加到结尾：
O(n) - 从末尾删除：
O(n) - 在中间插入：
O(n) - 从中间删除：
O(n) - 随机访问：
O(1) - 按顺序访问：
O(1) - 搜索特定元素：
O(n) - 注意：最有效地使用内存；在数据大小固定的情况下使用。
List
列表
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes:Implementation is optimized for speed. In many cases, List will be the best choice.
- 添加到结尾：
best case O(1); worst case O(n) - 从末尾删除：
O(1) - 在中间插入：
O(n) - 从中间删除：
O(n) - 随机访问：
O(1) - 按顺序访问：
O(1) - 搜索特定元素：
O(n) - 注意：实现是针对速度进行了优化。在许多情况下，List 将是最佳选择。
Collection
收藏
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
O(n) - remove from middle:
O(n) - Random Access:
O(1) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes:List is a better choice, unless publicly exposed as API.
- 添加到结尾：
best case O(1); worst case O(n) - 从末尾删除：
O(1) - 在中间插入：
O(n) - 从中间删除：
O(n) - 随机访问：
O(1) - 按顺序访问：
O(1) - 搜索特定元素：
O(n) - 注意：List 是更好的选择，除非公开公开为 API。
LinkedList
链表
- add to end:
O(1) - remove from end:
O(1) - insert at middle:
O(1) - remove from middle:
O(1) - Random Access:
O(n) - In-order Access:
O(1) - Search for specific element:
O(n) - Notes:Many operations are fast, but watch out for cache coherency.
- 添加到结尾：
O(1) - 从末尾删除：
O(1) - 在中间插入：
O(1) - 从中间删除：
O(1) - 随机访问：
O(n) - 按顺序访问：
O(1) - 搜索特定元素：
O(n) - 注意：许多操作很快，但要注意缓存一致性。
Stack
堆
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
N/A - remove from middle:
N/A - Random Access:
N/A - In-order Access:
N/A - Search for specific element:
N/A - Notes:Shouldn't be selected for performance reasons, but algorithmic ones.
- 添加到结尾：
best case O(1); worst case O(n) - 从末尾删除：
O(1) - 在中间插入：
N/A - 从中间删除：
N/A - 随机访问：
N/A - 按顺序访问：
N/A - 搜索特定元素：
N/A - 注意：不应出于性能原因选择，而是出于算法原因选择。
Queue
队列
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
N/A - remove from middle:
N/A - Random Access:
N/A - In-order Access:
N/A - Search for specific element:
N/A - Notes:Shouldn't be selected for performance reasons, but algorithmic ones.
- 添加到结尾：
best case O(1); worst case O(n) - 从末尾删除：
O(1) - 在中间插入：
N/A - 从中间删除：
N/A - 随机访问：
N/A - 按顺序访问：
N/A - 搜索特定元素：
N/A - 注意：不应出于性能原因选择，而是出于算法原因选择。
Dictionary
字典
- add to end:
best case O(1); worst case O(n) - remove from end:
O(1) - insert at middle:
best case O(1); worst case O(n) - remove from middle:
O(1) - Random Access:
O(1)* - In-order Access:
O(1)* - Search for specific element:
O(1) - Notes:Although in-order access time is constant time, it is usually slower than other structures due to the over-head of looking up the key.
- 添加到结尾：
best case O(1); worst case O(n) - 从末尾删除：
O(1) - 在中间插入：
best case O(1); worst case O(n) - 从中间删除：
O(1) - 随机访问：
O(1)* - 按顺序访问：
O(1)* - 搜索特定元素：
O(1) - 注意：虽然顺序访问时间是常数时间，但由于查找密钥的开销，它通常比其他结构慢。
回答by Andrew Hare
This isn't a cheat sheet but it is a good place to start learning: Collection Classes (C# Programming Guide).
这不是备忘单，但它是开始学习的好地方： 集合类（C# 编程指南）。
Edit:I would look specifically at this related section: Selecting a Collection Class .
编辑：我会专门看这个相关部分：选择一个集合类 。
Be sure to choose your System.Collections class carefully. Using the wrong type can restrict your use of the collection.
请务必仔细选择您的 System.Collections 类。使用错误的类型会限制您对集合的使用。
