3

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!

luanped
  • 3,178
  • 2
  • 26
  • 40
  • Yes, of course they use hashing. And because you cannot specify your own equality, you don't need to implement your own hashing function either. They just use to the object identity. – Bergi Jun 13 '17 at 18:25
  • 1
    Possible duplicate of [es6 Map and Set complexity, v8 implementation](https://stackoverflow.com/q/33611509/1048572)? I'll close if that answers your question. – Bergi Jun 13 '17 at 18:26
  • Ah I see, so I understand that they use object identity to check for equality. But how do they get the hashing location? some sort of memoryAddress % keySpace ? – luanped Jun 13 '17 at 18:35
  • I don't know, but yes, that sounds like a suitable simple one. – Bergi Jun 13 '17 at 20:39

1 Answers1

6

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.

jmrk
  • 34,271
  • 7
  • 59
  • 74
  • hi, thanks for your explain. I'm searching the implementabtion for some time and didn't find any. Do you have some reference about it? – Yao Zhao Apr 24 '21 at 06:11
  • 1
    Most of the implementation is in https://source.chromium.org/chromium/chromium/src/+/master:v8/src/builtins/builtins-collections-gen.cc currently; look for e.g. `MapPrototypeSet` (in that file) for one of the entry points. – jmrk Apr 24 '21 at 15:12