c# - Dictionary, List 和其他集合实现/运行时

Question

我想知道是否有任何好的引用资料(网站或更好的书籍)，我可以在其中找到有关常用集合内部实现的信息，例如

• Dictionary<TKey, TValue>
• List<T>
• Queue<T>
• Stack<T>
• 等等

我所说的内部实现是指他们如何使用动态数组存储数据、调整数据大小的频率、常见操作的时间和空间复杂度。

当然，如果有人认为他可以在此线程中提供此信息，我们非常欢迎您!

Answer 1

关于List<T> :

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

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

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)(在内部，为Queue的头和尾元素保留索引)。因此，将元素入队或压入堆栈需要分摊的常数时间，出队/弹出需要常数时间。

关于Dictionary<TKey, TValue> :

字典的工作方式不同，并且描述得很好 here .