ecmascript 6 - ES6 Maps and Sets: how are object keys indexed efficiently?

Question

In ES6, Maps and Sets can use Objects as keys. However since the ES6 specification does not dictate the underlying implementation of these datastructures, I was wondering how does the modern JS engines store the keys in order to guarantee O(1) or at least sublinear retrieval?

In a language like Java, the programmer can explicitly provide a (good) hashCode method which would hash the keys evenly in the key space in order to guarantee the performance. However since JS does not have such features, would it still be fair to still assume they use some sort of hashing in the Maps and Sets implementation?

Any information will be appreciated!

Answer 1

Yes, the implementation is based on hashing, and has (amortized) constant access times.

"they use object identity" is a simplification; the full story is that ES Maps and Sets use the SameValueZero algorithm for determining equality.

In line with this specification, V8's implementation computes "real" hashes for strings and numbers, and chooses a random number as "hash" for objects, which it stores as a private (hidden) property on these objects for later accesses. (That's not quite ideal and might change in the future, but for now that's what it is.)

Using memoryAddress % keySpace cannot work because the garbage collector moves objects around, and rehashing all Maps and Sets every time any object might have moved would be prohibitively complicated and expensive.