ES6 规范为 Keyed Collections（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)）算法。让我感到非常惊讶的是，规范不会强制要求甚至允许更高性能的算法，而且我对解释为什么会这样非常感兴趣。
对于任何好奇的人，我做了一个非常快速的基准测试：
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
问题是 Set.has() 方法 O(1) 和 Array.indexOf O(n) 吗？被列为此副本的副本，但并不完全正确（我已投票决定重新开放）。无论如何，我将在此处添加这些基准，因为对该问题的答复中的基准未能显示Set#has和之间的全部性能差异Array#indexOf。
以下内容适用于 Chrome 93：
您会发现对于较小的数据集，Array#indexOf实际上优于Set#has或Map#has; 然而，对于更大的数据集，Set#has并Map#has有多个数量级快。这与您对 O(n) 与 O(1) 操作的期望非常一致。
有趣的是，尽管两者都是 O(n)，Array#includes但比Array#indexOf小数据集慢得多，但对大数据集的表现非常相似。据推测，Array#indexOf利用了一些Array#includes没有的优化。
同时，Object#hasOwnProperty略微优于Set#has以及Map#has在所有情况下（至少在Chrome 93）。
const [small, medium, large] = [1e3, 1e5, 1e7]
const configs = [
{ size: small, iterations: large },
{ size: medium, iterations: medium },
{ size: large, iterations: small },
]
for (const { size, iterations } of configs) {
const arr = Array.from({ length: size }, (_, i) => String(i))
const obj = Object.fromEntries(arr.map(k => [k, true]))
const set = new Set(arr)
const map = new Map(Object.entries(obj))
const valsToTest = Array.from(
{ length: iterations },
(_, i) => String(Math.floor(Math.random() * size)),
)
const title = `dataset size: ${size.toLocaleString()}; iterations: ${iterations.toLocaleString()}`
console.log(`\n-> ${title}`)
for (const [target, method] of [
[arr, 'indexOf'],
[arr, 'includes'],
[set, 'has'],
[map, 'has'],
[obj, 'hasOwnProperty'],
]) {
const subtitle = `${target.constructor.name}#${method}`
console.time(subtitle)
for (const val of valsToTest) {
target[method](val)
}
console.timeEnd(subtitle)
}
}
-> dataset size: 1,000; iterations: 10,000,000
Array#indexOf: 185.100ms
Array#includes: 11302.700ms
Set#has: 367.400ms
Map#has: 375.000ms
Object#hasOwnProperty: 252.800ms
-> dataset size: 100,000; iterations: 100,000
Array#indexOf: 10794.100ms
Array#includes: 10476.800ms
Set#has: 6.600ms
Map#has: 6.800ms
Object#hasOwnProperty: 1.900ms
-> dataset size: 10,000,000; iterations: 1,000
Array#indexOf: 12798.900ms
Array#includes: 12435.400ms
Set#has: 0.800ms
Map#has: 0.800ms
Object#hasOwnProperty: 0.300ms