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

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)，因为它涉及将其余元素移动一个位置（分别向右或向左）。用于内部数组的空间当然与数组的元素成线性关系，从到变化（或者，如果这有意义的话：:) 。n2nMath.Pow(2, Math.Ceiling(Math.Log(n, 2)))

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

Queue 和 Stack 的内部数组的大小调整工作方式与 所描述的类似。List<T>常见操作的效率为O(1)（内部为 Queue 的头元素和尾元素保留索引）。因此，将元素入队或压入堆栈需要摊销常数时间，出队/弹出需要常数时间。

关于Dictionary<TKey, TValue>：

字典的工作方式有所不同，这里对其进行了很好的描述。