To counter your question, why do you believe that storing a value is likely to be slower than checking the existing values to see if you need to store it?
Just to be complete, I modified your code to include Arrays, too.
x = {};
y = new Set();
z = [];
console.time('Insert into Object');
for (var i = 0; i < 1000000; i++) {
x[i] = 0;
}
console.timeEnd('Insert into Object');
console.time('Insert into Set');
for (i = 0; i < 1000000; i++) {
y.add(i);
}
console.timeEnd('Insert into Set');
console.time('Insert into Array');
for (i = 0; i < 1000000; i++) {
z[i] = 0;
}
console.timeEnd('Insert into Array');
var t = 0;
console.time('Retrieve from Object');
for (i = 0; i < 1000000; i++) {
t = x[i];
}
console.timeEnd('Retrieve from Object');
console.time('Retrieve from Set');
for (i = 0; i < 1000000; i++) {
t = y.has(i);
}
console.timeEnd('Retrieve from Set');
console.time('Retrieve from Array');
for (i = 0; i < 1000000; i++) {
t = z[i];
}
console.timeEnd('Retrieve from Array');
console.log(t);
Ordinarily, one would expect that storing into an object is O(1) time complexity while checking the existing values in a set should be no more than O(n) (where n is the number of items in the set), so we should expect that the set may become slower as it becomes larger. This performance may even be implementation-dependent, i.e. different javascript runtimes may behave differently.
And in fact, that's exactly what we see: (Running on my machine)
(your code)
Insert into Object: 67.558ms
Insert into Set: 259.841ms
Insert into Array: 64.297ms
Retrieve from Object: 19.337ms
Retrieve from Set: 149.968ms
Retrieve from Array: 3.981ms
But if we change your insertion tests to continually re-add the same values...
We see this:
Insert into Object: 19.103ms
Insert into Set: 40.645ms
Insert into Array: 16.384ms
Retrieve from Object: 40.116ms
Retrieve from Set: 30.672ms
Retrieve from Array: 70.050ms
Which tells us a couple of things. First, different types are differently sensitive to the size of the collection. Secondly, retrieving non-existent keys from either an array or an object is slower than checking a set for the same value (at least on this particular implementation).
As a final note
I think it's important to note here that we're discussing the relative performance of things that take well under a second for a million iterations (or about a second-and-a-half on your test). That's pretty fast already. For those reading this in the future, remember to choose the data structure that's semantically the one you want. Any of these three is a perfectly good choice from a performance perspective. Choose the one that makes your program the most understandable.
