字典的时间复杂度和空间复杂度是多少？

Question

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

• 整个字典的空间
• time -- 将条目添加到字典中

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

Answer 1

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

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

Answer 2

整个字典的空间复杂度是多少

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

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

时间复杂度是多少——向字典添加条目

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