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 => {

  console.time('benchmarkMap');

  var map = new Map();

  for (var i = 0; i < size; i++) map.set(i, i);

  for (var i = 0; i < size; i++) var x = map.get(i);

  console.timeEnd('benchmarkMap');

}

const benchmarkObj = size => {

  console.time('benchmarkObj');

  var obj = {};

  for (var i = 0; i < size; i++) obj[i] = i;

  for (var i = 0; i < size; i++) var x = obj[i];

  console.timeEnd('benchmarkObj');

}

var size = 1000000;

benchmarkMap(size);

benchmarkObj(size);

我运行了几次，结果如下：

（2017 MacBook Pro，2.5 GHz i7带16G RAM）

benchmarkMap: 189.120ms

benchmarkObj: 44.214ms

benchmarkMap: 200.817ms

benchmarkObj: 38.963ms

benchmarkMap: 187.968ms

benchmarkObj: 41.633ms

benchmarkMap: 186.533ms

benchmarkObj: 35.850ms

benchmarkMap: 187.339ms

benchmarkObj: 44.515ms

Answer 2

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