How are ES6 maps implemented under the hood?

Question

I was asked during an interview to implement a data structure of key/value pairs where keys can be an object, I know this is possible using ES6 maps but how do they work under the hood in Javascript where keys are strictly stringified and yet achieve the same constant lookup time of a hash table / object?

Thank you.

Yeah that makes sense but if that reference is altered, the hash index that was already generated would be invalid? — Khalid Khalil, Oct 24 '19 at 14:32
How can an object’s reference be altered? If an object has a different reference, it’s a different object. — Sebastian Simon, Oct 24 '19 at 14:33
@t.niese JS stringifies any key that's given inside any object by default, so is there anything other than objects that ES6 Map utilize? — Khalid Khalil, Oct 24 '19 at 14:35
Yes, but the keys used in the `Map` with `get`/`set` are not the same as the keys referencing a property of an object. And those map keys are not stringified. — t.niese, Oct 24 '19 at 14:38
@t.niese indeed. This is a bit of terminology clash - in JS *usually* "key" refers to the *property* of an object. When talking about maps in general, then "key" would just be the item that is used to lookup an associated value. This gets muddled because plain JS objects *do* use keys in the same fashion, so key became somewhat synonymous with "property name" in JS which is *correct* since they work the same way for fetching a value under the good but also incorrect since maps don't usually fetch values in a map via its property. So, there was an abstraction leakage. — VLAZ, Oct 24 '19 at 14:43

score 2 · Answer 1 · answered Oct 24 '19 at 14:30

2

The keys of Map are not keys of the Map object. They are arguments to the .get and .set methods.

 const map = new Map;
 const key = {};
 map.set(key, "stuff"); // key is passed as an argument, not stringified
 map[key] // key would get stringified here according to language semantics, but even then it would be undefined as maps keys aren't keys of the map object

What these methods do under the hood is implementation secific.

answered Oct 24 '19 at 14:30

Jonas Wilms

132,000
20
149
151

That's indeed right I realize that, my question was kind of vague, is there any resources which I can dig into to see how .get/.set work? – Khalid Khalil Oct 24 '19 at 14:33
It’s more accurate to say that a Map’s keys are not _properties_ of the Map object. They can still be called “keys”. – Sebastian Simon Oct 24 '19 at 14:34
You can dig into the spec to find the rules these methods have to fullfill, or the sourcecode of one of the implementations – Jonas Wilms Oct 24 '19 at 14:34

Cole · Answer 2 · 2021-12-21T03:26:04.113

I was asked this on an interview, and I can't vouch for how Map is actually implemented under the hood (ended up here looking for myself). However, this is the approach I worked out with my interviewer (note, the requirement was only for DOM node keys, but I do think objects are the trickiest key to handle, and the rest could be handled trivially with additional code), and I think it is at least insightful:

class Map {
  constructor() {
    this.map = {}; // internal key/value object
    this.trackerKey = Symbol();
  }

  set(key, value) {
    let lookupKey = key[this.trackerKey];
    if (!lookupKey) {
      lookupKey = Symbol();
      key[this.trackerKey] = lookupKey;
    }
    this.map[lookupKey] = value;
  }

  has(key) {
    return key.hasOwnProperty(this.trackerKey);
  }

  get(key) {
    const lookupKey = key[this.trackerKey];
    return this.map[lookupKey];
  }

  delete(key) {
    const lookupKey = key[this.trackerKey];
    delete key[this.trackerKey];
    delete this.map[lookupKey];
  }
}

Basically, the idea is to use Symbols under the hood to keep track of the objects. trackerKey is a (Symbol) property we add to all keys that are coming in. Since it's a symbol defined inside the instance, nothing else will be able to reference it.

So when we go to set, we check if the trackerKey property exists on the object. If not, we set it to a new symbol. We then set the value of that key in our internal map to the value coming in.

has and get are fairly straightforward lookups now. We check if our tracker key exists on the key to see if it is included in our Map. For get we can simply grab our internal lookup key for the object from its trackerKey property.

For delete, we just need to delete the trackerKey property from the key object, and then delete the property in our internal map object. Fun and insightful exercise! Hope this helps :)

"*nothing else will be able to reference it*" -- `trackerKey` could be retrieved from the outside via `Object.getOwnPropertySymbols` or `Reflect.ownKeys`, but you're right in that no code would normally do that. — FZs, Dec 21 '21 at 00:49
@FZs good callout. That's a good point, the symbol key could be retrieved using those methods. But we are at least guaranteed that the only way for external code to access the `trackerKey` is through the reflection you mentioned, and we are otherwise guaranteed uniqueness in the `trackerKey`, such that no external code can *accidentally* override or collide with it. — Cole, Dec 21 '21 at 03:23
Note, this also won't work if the object has been sealed or frozen. Not sure how we could handle that use case — Cole, Dec 23 '21 at 00:35

How are ES6 maps implemented under the hood?

2 Answers2