ES6 规范为 Keyed Collections（Set、Map、WeakSet 和 WeakMap）提供了多少时间复杂度（以大 O 表示法表示）？
我的期望，以及大多数开发人员的期望，是规范和实现将使用被广泛接受 https://wiki.python.org/moin/TimeComplexity高性能算法，在这种情况下Set.prototype.has, add and delete在平均情况下都是 O(1)。对于Map and Weak–等价物。
我并不完全清楚实现的时间复杂度是否是强制的，例如在ECMAScript 2015 语言规范 - 第 6 版 - 23.2 设置对象 http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects.
除非我误解了它（而且我很可能会误解它），否则看起来 ECMA 规范要求实现（例如Set.prototype.has http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set.prototype.has）是使用线性时间（O(n)） 算法。让我感到非常惊讶的是，规范不会强制甚至允许更高性能的算法，而且我对解释为什么会出现这种情况非常感兴趣。
就从那一段 http://www.ecma-international.org/ecma-262/6.0/index.html#sec-set-objects您的链接到：
集合对象必须使用[机制]来实现，平均而言，该机制提供的访问时间与集合中元素的数量呈次线性关系。
你会发现同样的句子Maps http://www.ecma-international.org/ecma-262/6.0/index.html#sec-map-objects, WeakMaps http://www.ecma-international.org/ecma-262/6.0/index.html#sec-weakmap-objects and WeakSets http://www.ecma-international.org/ecma-262/6.0/index.html#sec-weakset-objects.
看起来 ECMA 规范要求实现（例如 Set.prototype.has）使用线性时间（O(n)） 算法。
No:
本文使用的数据结构Set对象规范仅用于描述 Set 对象所需的可观察语义。它并不是一个可行的实施模型。
可观察的语义主要与可预测的迭代顺序相关（仍然可以是高效、快速地实施 https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables）。规范确实期望实现使用哈希表或类似的具有恒定访问的东西，尽管也允许树（具有对数访问复杂性）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
