集合的 Javascript ES6 计算/时间复杂度

Question

ES6 规范为键控集合(Set、Map、WeakSet 和 WeakMap)提供了什么样的时间复杂度(以大 O 表示法表示)？

我和大多数开发人员的期望是，规范和实现将使用 widely accepted性能算法，在这种情况下，Set.prototype.has、add 和 delete 在平均情况下都是 O(1)。 Map 和 Weak– 等价物也是如此。

我并不完全清楚实现的时间复杂度是否是强制性的，例如在 ECMAScript 2015 Language Specification - 6th Edition — 23.2 Set Objects .

除非我误解了它(而且我确实很有可能这样做)，看起来 ECMA 规范要求实现(例如 Set.prototype.has )要使用线性时间 (O(n) ) 算法。如果规范不强制甚至不允许更高性能的算法，我会感到非常惊讶，我很想知道为什么会这样。

Answer 1

权利来自 that very paragraph你链接到:

Set objects must be implemented using [mechanisms] that, on average, provide access times that are sublinear on the number of elements in the collection.

你会发现 Maps 同样的句子, WeakMaps和 WeakSets .

It looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm.

否:

The data structures used in this Set objects specification is only intended to describe the required observable semantics of Set objects. It is not intended to be a viable implementation model.

可观察的语义主要与可预测的迭代顺序相关(仍然可以是 implemented efficient and fast )。规范确实期望实现使用哈希表或类似的具有恒定访问权限的东西，尽管树(具有对数访问复杂性)也是允许的。