7

我想知道是否有任何好的参考资料（网站甚至更好的书），我可以在其中找到有关常用集合的内部实现的信息，例如

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

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

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

4

2 回答 2

3

关于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对于数组的元素当然是线性的，从to变化2n（或者，如果这有意义的话：Math.Pow(2, Math.Ceiling(Math.Log(n, 2))):)。

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

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

关于Dictionary<TKey, TValue>：

字典的工作方式不同，这里有很好的描述。

于 2013-04-01T22:55:37.180 回答
1

每一个的确切实现细节都需要很长的解释（对于每一个）。相反，我建议您参考 J. Albahari 的书 C# 5.0 In a Nutshell。

但是，我可以为您提供一个表格，用于Dictonary 类的常见操作的内存/时间考虑。这些性能时间以毫秒为单位，在 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

抱歉，我无法为您需要的其他人提供此服务。

我希望这有一些用处。

于 2012-09-06T10:27:03.607 回答