地图的时间复杂性包含键并包含DART中的值
map.containskey和map.containsvalue的时间复杂性是什么？我想知道以下实现：
- linkedhashmap
- hashmap
- splaytReemap
我假设Hash Map实现containsKey containskey 是摊销的常数时间，containsValue可能是线性时间。对于splaytreemap，containskey可能是对数时间，而containsValue可能仍然是线性的。但是，文档在这个问题上。我能找到的最好的是linkedhashmap，说：
带有预期恒定时间查找的插入订单[MAP]。
这没有指定您是在查找密钥还是值，但大概是指键。
docs for set> set set set < /code>（另一方面，如果导航到实现），则不是静音。他们给予时间复杂。
我认为这是文档中的监督，但也许它们是沉默的，因为没有保证的时间复杂性。 （但是，这很奇怪，因为它违背了开发人员的期望。）
What is the time complexity of Map.containsKey and Map.containsValue in Dart? I'd like to know for the following implementations:
- LinkedHashMap
- HashMap
- SplayTreeMap
I assume for the hash map implementations containsKey is amortized constant time and containsValue is probably linear time. For SplayTreeMap, containsKey is probably logarithmic time while containsValue is probably still linear time. However, the 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.
This doesn't specify if you are looking up the key or the value, but presumably this is referring to the key.
The docs for Set (if you navigate to the implementations), on the other hand, are not silent. They give the time complexity.
I assume this is an oversight in the documentation, but perhaps they are silent because there is no guaranteed time complexity. (That's would be strange, though, because it goes against developer expectations.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
对于
包含，这与进行查找同时。hashmap和linkedhashmap：预期的持续时间，deNeneratehashcode的最差线性时间s。splaytreemap，弹药对数时间。对于
包含value，它在元素数量（至少）中是线性的。它只是执行map.values.contains（...）的等效。没有有效的方法可以在地图中找到一个值，因此没有比以某种顺序浏览所有值更好的方法了。某些潜在的
hashmap实现可能会非常昂贵，因为它们穿越了整个背景商店，如果地图先生长了大，然后删除了很多元素，那么它可能会有一个备用商店明显大于其元素数量。其他实现自动撕裂，或将元素保存在连续的区域，并且不会遇到这个问题。非常依赖实施。飞镖使用哪种实施的承诺。
For
containsKey, it's the same time as doing a lookup.HashMapandLinkedHashMap: Expected constant time, worst-case linear time for degeneratehashCodes.SplayTreeMap, ammortized logarithmic time.For
containsValue, it's linear in the number of elements (at least). It simply does the equivalent ofmap.values.contains(...). There is no efficient way to find a single value in a map, so there is no better way than looking through all of them in some order.Some potential
HashMapimplementations can be extra expensive because they traverse the entire backing store, and if the map had been grown big first, then had a lot of elements removed, then it might have a backing store which is significantly larger than its number of elements. Other implementations auto-shrink, or keep elements in a contiguous area, and won't have that problem.Very implementation dependent. No promises which implementation Dart uses.