Dictionary<TKey,TValue>.Values - 是否会分配新的内存，时间复杂度是多少？

Question

我是新手C#程序员，想了解使用Dictionary.Values 属性的内存和时间开销。我在这里找不到算法时间复杂度规范或内存复杂度有关的任何信息？我是看错了地方还是在C#规范中未定义？

P.S. 我来自C++背景。

- Narek Aghekyan

---

.NET Framework 库是开源的，因此您可以在这里阅读到它们：https://github.com/Microsoft/referencesource/blob/master/mscorlib/system/collections/generic/dictionary.cs#L157-L163 或者 https://referencesource.microsoft.com/#mscorlib/system/collections/generic/dictionary.cs,157。 - ProgrammingLlama

Answer 1

这不是C#的特性，而是框架实现细节，因此在C#规范中未定义。当第一次请求时，.Values会被延迟实例化；之后，现有值将被分发。因此，当第一次使用时可能会分配一些内存，但它不包含值的快照副本，因此这不是昂贵的分配。它只包含对父词典实例的引用。

private Dictionary<TKey, TValue> dictionary;

ValueCollection<TKey, TValue>中实际上只有一个字段。它本质上是一个门面，为相同的数据提供了以值为中心的视图。

- Marc Gravell

Answer 2

关于时间复杂度：字典（Dictionary）与哈希表（Hashmap）基本等价。因此，读取一个项目的时间复杂度可以期望为O(1)。 对于插入一个项目，它取决于情况（由于可能需要内存分配）。它可以是O(1)或O(n)。

- user82593