1

I'm curious about the internals of v8 and how Map is implemented under the hood. Contrasting Maps, javascript objects cannot have objects as keys. As far as I understand it Maps implement lookup in the classic hash map fashion. Some hashing function maps the input key to some output integer, which is used as an index in an array. Then there's some dynamic resizing when the array overflows and some linkedlist in each bin of the array. Probably the details of v8's maps are a little more intricate and they involve some optimizations for small Maps? Curious to know how much the actual implementation differs from my above sketch. Based on the assumption that Map works like this under the hood, how does it map from a plain object to a key in the array? I am guessing it modulos the pointer address into the array?

Curious to dig deeper.

david_adler
  • 9,690
  • 6
  • 57
  • 97
  • If you're so interested about the specific details, have you taken a look at the code? – Bergi May 09 '21 at 21:01
  • 1
    No, but fair point, I probably should . Am I right in saying this is the right file? https://github.com/v8/v8/blob/master/src/objects/map.cc Might try combing through it and writing up an answer to my own question – david_adler May 09 '21 at 21:11
  • 1
    Looks like this file is more relevant. The previous file I linked is more relevant to all objects afaics. https://github.com/v8/v8/blob/master/src/objects/ordered-hash-table.h – david_adler May 09 '21 at 22:56

1 Answers1

2

Short answer: ES6 Maps and Sets: how are object keys indexed efficiently? (with a minor update: four years later, the precise way how the random "hash" is stored on objects has indeed been improved; the principle remains the same).

Long answer: as Bergi suggested, read the source. Note that the details could change at any time (which is one reason why there isn't a whole lot of documentation about what the current implementation does).

jmrk
  • 34,271
  • 7
  • 59
  • 74
  • Awesome thanks @jmrk! I have done my best to read through the source. AFICS, `JsMap` extends `OrderedHashMap`. `OrderedHashMap::GetHash`, calls `Object::GetHash -> JSReceiver::GetIdentityHash -> GetIdentityHashHelper -> BaseNameDictionary::Hash` which gets the random hash which is stored at a fixed offset in the object `kObjectHashIndex`. https://github.com/v8/v8/blob/dc712da548c7fb433caed56af9a021d964952728/src/objects/dictionary-inl.h#L84 Does that sound about right? – david_adler May 10 '21 at 09:54
  • 1
    Sure, aside from skipping over a bunch of details, that summary sounds about right. The other way to summarize it is "an object's hash is stored on the object". – jmrk May 10 '21 at 10:18