c# - 什么是字典的时间和空间复杂度？

Question

假设我有大小为 N 的数据（即 N 个元素），并且字典是用容量 N 创建的。复杂性是什么：

• 空间——整个字典
• time -- 向字典中添加条目

MS 仅显示条目检索接近 O(1)。但是其余的呢？

Answer 1

空间的复杂性是什么——整个字典

字典使用具有 O(N) 空间复杂度的关联数组数据结构。

Msdn 说：“Dictionary 类是作为哈希表实现的”。哈希表依次使用关联数组。

时间的复杂性是什么——向字典中添加条目

单个添加需要分摊的 O(1) 时间。在大多数情况下它是 O(1)，当底层数据结构需要增长或收缩时它会变为 O(N)。由于后者很少发生，人们使用“摊销”一词。

Answer 2

添加新条目的时间复杂度记录在Dictionary<T>.Add()：

如果 Count 小于容量，则此方法接近 O(1) 操作。如果必须增加容量以容纳新元素，则此方法变为 O(n) 操作，其中 n 为 Count。

Answer 3

它没有正式记录，但广泛声明（并且通过反汇编可见）底层存储是一个名称-值对数组。因此空间复杂度为O(n)。

由于它不是规范的一部分，因此理论上可以更改；但实际上不太可能，因为它会改变可能可见的各种操作（例如枚举）的性能。