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

Question

ES6规范为键集合（Set，Map，WeakSet和WeakMap）提供什么时间复杂度（大O表示）？

我的期望，我期望的大多数开发人员，是规范和实现将使用被广泛接受的高性能算法，在这种情况下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

对于任何好奇的人，我做了一个非常快速的基准测试：const benchmarkMap = size => {&nbsp; console.time('benchmarkMap');&nbsp; var map = new Map();&nbsp; for (var i = 0; i < size; i++) map.set(i, i);&nbsp; for (var i = 0; i < size; i++) var x = map.get(i);&nbsp; console.timeEnd('benchmarkMap');}const benchmarkObj = size => {&nbsp; console.time('benchmarkObj');&nbsp; var obj = {};&nbsp; for (var i = 0; i < size; i++) obj[i] = i;&nbsp; for (var i = 0; i < size; i++) var x = obj[i];&nbsp; console.timeEnd('benchmarkObj');}var size = 1000000;benchmarkMap(size);benchmarkObj(size);我运行了几次，结果如下：（2017 MacBook Pro，2.5 GHz i7带16G RAM）benchmarkMap: 189.120msbenchmarkObj: 44.214msbenchmarkMap: 200.817msbenchmarkObj: 38.963msbenchmarkMap: 187.968msbenchmarkObj: 41.633msbenchmarkMap: 186.533msbenchmarkObj: 35.850msbenchmarkMap: 187.339msbenchmarkObj: 44.515ms

Answer 2

所有O（1）算法也都是O（n），因此让性能较低的规范实现不会造成任何危害。性能较差的实现可能在资源受限的系统中可能会引起一些关注，因为它们很可能需要更少的代码/空间。