Dart 中 Map containsKey 和 containsValue 的时间复杂度
Time complexity of Map containsKey and containsValue in Dart
Dart 中 Map.containsKey 和 Map.containsValue 的时间复杂度是多少？我想知道以下实现：
- LinkedHashMap
- HashMap
- SplayTreeMap
我假设哈希映射实现 containsKey 是摊销常数时间，containsValue 可能是线性时间。对于 SplayTreeMap，containsKey 可能是对数时间，而 containsValue 可能仍然是线性时间。但是，documentation seems to be silent on the issue. The best I could find was for LinkedHashMap, which says:
An insertion-ordered [Map] with expected constant-time lookup.
这没有指定您是在查找键还是值，但大概这是指键。
另一方面，Set 的 docs（如果您导航到实现）并非无声。他们给出了时间复杂度。
我认为这是文档中的一个疏忽，但也许他们保持沉默是因为没有保证的时间复杂度。 （不过，这会很奇怪，因为它违背了开发人员的期望。）
对于containsKey，它与查找的时间相同。
HashMap 和 LinkedHashMap：预期恒定时间，worst-case 退化 hashCodes 的线性时间。SplayTreeMap，摊销对数时间。
对于containsValue，它与元素数量成线性关系（至少）。它只是相当于 map.values.contains(...)。没有找到地图中单个值的有效方法，因此没有比按某种顺序查看所有值更好的方法了。
一些潜在的 HashMap 实现可能会非常昂贵，因为它们遍历了整个后备存储，如果地图先变大，然后删除了很多元素，那么它的后备存储可能比它的元素数量。其他实现 auto-shrink，或将元素保持在连续区域中，不会出现该问题。
非常依赖于实现。没有承诺 Dart 使用哪个实现。
Dart 中 Map.containsKey 和 Map.containsValue 的时间复杂度是多少？我想知道以下实现：
- LinkedHashMap
- HashMap
- SplayTreeMap
我假设哈希映射实现 containsKey 是摊销常数时间，containsValue 可能是线性时间。对于 SplayTreeMap，containsKey 可能是对数时间，而 containsValue 可能仍然是线性时间。但是，documentation seems to be silent on the issue. The best I could find was for LinkedHashMap, which says:
An insertion-ordered [Map] with expected constant-time lookup.
这没有指定您是在查找键还是值，但大概这是指键。
另一方面，Set 的 docs（如果您导航到实现）并非无声。他们给出了时间复杂度。
我认为这是文档中的一个疏忽，但也许他们保持沉默是因为没有保证的时间复杂度。 （不过，这会很奇怪，因为它违背了开发人员的期望。）
对于containsKey，它与查找的时间相同。
HashMap和LinkedHashMap：预期恒定时间，worst-case 退化hashCodes 的线性时间。SplayTreeMap，摊销对数时间。
对于containsValue，它与元素数量成线性关系（至少）。它只是相当于 map.values.contains(...)。没有找到地图中单个值的有效方法，因此没有比按某种顺序查看所有值更好的方法了。
一些潜在的 HashMap 实现可能会非常昂贵，因为它们遍历了整个后备存储，如果地图先变大，然后删除了很多元素，那么它的后备存储可能比它的元素数量。其他实现 auto-shrink，或将元素保持在连续区域中，不会出现该问题。
非常依赖于实现。没有承诺 Dart 使用哪个实现。