Is Set A Hashed Collection In Javascript?

I was asking myself this question. Is Set a hashed collection in JavaScript? For example, Set.prototype.has will iterate the entire Set or do its implementations use an internal ha

Solution 1:

The ECMAScript 2015 specification says that:

Set objects must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements in the collection.

Obviously they can't force a particular JS engine to actually do that, but in practice JS engines will do the right thing.

Solution 2:

The ES6 specification does not require a specific implementation, but it does indicate that it should be better than O(n) (so better than a linear lookup). And, since the purpose of the Set object is to be efficient at looking up items in the Set, it most surely uses some sort of efficient lookup system like a hash.

If you want to know for sure how it works, you'd have to look at the open source code for the Firefox or Chrome implementations.

You could also benchmark it to prove that the lookup speed is not O(n), but something more efficient than that.