Javascript ES6 computational/time complexity of collections

Question

What time complexity (in big-O notation) is provided by the ES6 specification for the Keyed Collections (Set, Map, WeakSet, and WeakMap)?

My expectation, and I expect that of most developers, is that the specifications and implementations would use widely accepted performant algorithms, in which case Set.prototype.has, add and delete to all be O(1) in the average case. The same for the Map and Weak– equivalents.

It is not entirely apparent to me whether the time complexity of the implementations was mandated e.g. in ECMAScript 2015 Language Specification - 6th Edition — 23.2 Set Objects.

Unless I misunderstand it (and it's certainly very possible I do), it looks the ECMA spec mandates that the implementations (e.g. Set.prototype.has) are to use a linear time (O(n)) algorithm. It would strike me as exceedingly surprising that more performant algorithms would not be mandated or even permitted by the spec, and I would be very interested in an explanation for why this is the case.

Answer 1

Right from that very paragraph your linked to:

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

You will find the same sentence for Maps, WeakMaps and WeakSets.

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

No:

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.

The observable semantics are mostly related to the predictable iteration order (which still can be implemented efficient and fast). It is indeed expected by the specification that an implementation uses a hash table or something similar with constant access, though trees (with logarithmic access complexity) are allowed as well.

Answer 2

For anyone who is curious, I did a very quick benchmark:

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);

I ran this a few times and yielded the following results:

(2017 MacBook Pro, 2.5 GHz i7 w/ 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 3

The question Is the Set.has() method O(1) and Array.indexOf O(n)? is listed as a duplicate of this one, which it isn't exactly (I've voted to re-open). I'll add these benchmarks here anyway, as the benchmarks on the replies to that question fail to show the full range of differences in performance between Set#has and Array#indexOf.

The following is all true for Chrome 93:

You find that for smaller datasets, Array#indexOf actually outperforms Set#has or Map#has; however, for larger datasets, Set#has and Map#has are multiple orders of magnitude faster. Which is pretty consistent with what you'd expect for O(n) vs O(1) operations.

Interestingly, despite both being O(n), Array#includes is way slower than Array#indexOf for a small dataset, but performs very similarly for large datasets. Presumably, Array#indexOf takes advantage of some optimization that Array#includes doesn't.

Meanwhile, Object#hasOwnProperty slightly outperforms Set#has and Map#has in all cases (at least in Chrome 93).

Benchmarking code

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)
    }
}

My results (Chrome 93)

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