dart - Dart 中 Map containsKey 和 containsValue 的时间复杂度

Question

Dart 中Map.containsKey 和Map.containsValue 的时间复杂度是多少？我想了解以下实现:

• LinkedHashMap
• 哈希表
• SplayTreeMap

我假设对于 HashMap 实现，containsKey 是摊销常数时间，containsValue 可能是线性时间。对于SplayTreeMap，containsKey可能是对数时间，而containsValue可能仍然是线性时间。然而，documentation似乎对这个问题保持沉默。我能找到的最好的是 LinkedHashMap，says :

An insertion-ordered [Map] with expected constant-time lookup.

这没有指定您是在查找键还是值，但大概这是指键。

docs对于 Set(如果您导航到实现)，另一方面，它们并不沉默。他们给出了时间复杂度。

我认为这是文档中的一个疏忽，但也许他们是沉默的，因为没有保证的时间复杂度。 (不过，这会很奇怪，因为它违背了开发人员的期望。)

Answer 1

对于containsKey，与查找的时间相同。

• HashMap 和 LinkedHashMap:预期常数时间，退化 hashCodes 的最坏情况线性时间。
• SplayTreeMap，摊销对数时间。

对于 containsValue，它与元素数量成线性关系(至少)。它只是执行与 map.values.contains(...) 等效的操作。没有找到 map 中单个值的有效方法，因此没有比按某种顺序查看所有值更好的方法了。 一些潜在的 HashMap 实现可能会非常昂贵，因为它们遍历整个后备存储，如果 map 先变大，然后删除了很多元素，那么它可能有一个后备存储是明显大于它的元素数量。其他实现自动收缩，或将元素保留在连续区域中，不会有这个问题。 非常依赖于实现。没有 Dart 使用哪个实现的 promise 。