Dictionary<Tkey, TValue>，List<T>和其他集合的实现/运行时

Question

我想知道是否有任何好的参考资料（网站或更好的是书籍），可以了解常用集合的内部实现，例如：

- Dictionary - List - Queue - Stack - 等等

通过内部实现，我指的是它们如何使用动态数组来存储数据，它们多久调整大小，常见操作的时间和空间复杂度是什么。

当然，如果有人觉得自己可以在这个帖子中提供这些信息，欢迎您！

- zafeiris.m

---

http://weblogs.asp.net/pawanmishra/archive/2010/01/14/collections-in-net.aspx - Oded

所有这些信息都在MSDN上。 - leppie

http://referencesource.microsoft.com/ - Arran

小提示：这些集合不是 C# 的一部分，它们是 .NET 的一部分。 - John Saunders

Answer 1

关于 List<T>:

List<T> 有两个属性，Capacity 和 Count，它们有助于澄清何时进行调整大小。 Capacity 是任何给定时间内内部数组的长度，而 Count 是添加到列表中的元素数。如果您估计要添加到列表中的元素数量，可以初始化 Capacity（通过选择适当的构造函数），这将导致较少或没有调整大小，从而实现更好的性能。

在调用 Add<T>() 方法且数组已满（Count == Capacity）时，会发生调整大小（即创建一个新的更大数组并逐一复制元素到新数组）。新数组的容量加倍（如果用户未设置，则最初从 0 开始，然后每次需要更多空间时都加倍）：

List<int> list = new List<int>();
//Capacity = 0, Count = 0

list.Add(52);
//Capacity = 4, Count = 1

list.Add(34);
list.Add(2);
list.Add(87);
//Capacity = 4, Count = 4

list.Add(56);
//Capacity = 8, Count = 5

对于大的n，添加新元素的时间复杂度是摊销常数 O(1)。按索引查找是常数 O(1)，在给定索引处插入或删除元素是线性的 O(n)，因为它涉及将其余元素向右或向左移动一个位置。内部数组使用的空间当然与数组的元素成线性关系，从n变化到2n（或者，如果有意义：Math.Pow(2, Math.Ceiling(Math.Log(n, 2))) :）。

关于Queue<T>和Stack<T>：

队列和堆栈内部数组的调整方式类似于List<T>中所描述的。常见操作是高效的 O(1)（在队列的头部和尾部元素保留索引）。因此，在队列中加入元素或在堆栈中推入元素需要摊销常数时间，出队/弹出需要常数时间。

关于 Dictionary<TKey, TValue>:

Dictionary 的工作方式有所不同，可以在这里了解。

- zafeiris.m

Answer 2

每个实现细节都需要长时间的解释（对于每个实现细节）。相反，我会推荐您阅读J. Albahari的书《C# 5.0 In a Nutshell》。

然而，我可以为您提供一个内存/时间考虑的表格，用于字典类的常见操作。这些性能时间以毫秒为单位，在1.5GHz PC上执行50,000次整数键和值的字典操作。

Type                Internal         Retrieve by     Memeory         Speed Random        Speed Seq        Speed Retrieval 
                    Structure        Index?          Overhead        Insertion           Insertion        by Key
Unsorted
Dictionary<T>       Hashtable        No              22              30                  30               20
Hashtable           Hashtable        No              38              50                  50               30
ListDictonary       Linked List      No              36              50,000              50,000           50,000
OrderedDictionary   Hashtable +      Yes             59              70                  70               40
                    Array
Sorted
SortedDictionary    Red-Black        No              20              130                 100              120 
<K, V>              Tree
SortedList <K, V>   2xArray          Yes             2               3,300               30               40
SortedList          2xArray          Yes             27              4,500               100              180

抱歉，我无法为您提供其他所需内容。

希望这对您有所帮助。

- MoonKnight