How do the ES6 Map shims work

Question

Based on my understanding of the docs (here and here) one would need a reference to the memory address for it to work:

const foo = {};
const map = new Map();
map.set(foo,'123');  // Can only be done if memory address of `foo` is known. Any other shimming would require stringification of foo

This is because JavaScript object {} keys can only be strings (at least in ES5).

Yet I see Map shim being available : https://github.com/zloirock/core-js#map. I tried reading the source but its too neatly abstracted (internally uses strong collection which then imports 10 more files)

Question

Answer any of the following please

• Is there a simple trick to it and can it truly even be done (without stringification)?
• Perhaps it mutates foo to store some string on it and then uses that as the key?
• Something else and maybe I am reading the docs wrong?

Answer 1

There are two ways that come to mind. First, obviously, you can have an array of keys, and search it linearly:

Map1 = {
    keys: [],
    values: [],
};

Map1.set = function(key, val) {
    var k = this.keys.indexOf(key);
    if(k < 0)
        this.keys[k = this.keys.length] = key;
    this.values[k] = val;
};

Map1.get = function(key) {
    return this.values[this.keys.indexOf(key)];
};


foo = {};
bar = {};

Map1.set(foo, 'xxx');
Map1.set(bar, 'yyy');

document.write(Map1.get(foo) + Map1.get(bar) + "<br>")

The second option is to add a special "key" marker to an object which is used as a key:

Map2 = {
    uid: 0,
    values: {}
};

Map2.set = function(key, val) {
    key = typeof key === 'object'
        ? (key.__uid = key.__uid || ++this.uid)
        : String(key);
    this.values[key] = val;
};

Map2.get = function(key) {
    key = typeof key === 'object'
        ? key.__uid
        : String(key);
    return this.values[key];
};


foo = {};
bar = {};

Map2.set(foo, 'xxx');
Map2.set(bar, 'yyy');

document.write(Map2.get(foo) + Map2.get(bar) + "<br>")

Unlike the 1st option, the second one is O(1). It can be done more accurately by making uid non-writable/enumerable. Also, each Map should have its own "uid" name (this can be easily set up in the Map constructor).

Answer 2

The trick is to store in an array and perform the lookup in O(n) time by iterating and using strict comparison—instead of using a true hash function which would be O(1) lookup. For example consider this:

var myObj = {};

var someArray = [{}, {}, myObj, {}];

console.log(someArray.indexOf(myObj)); // returns 2

Here is my implementation from another answer: Javascript HashTable use Object key

function Map() {
    var keys = [], values = [];

    return {
        put: function (key, value) {
            var index = keys.indexOf(key);
            if(index == -1) {
                keys.push(key);
                values.push(value);
            }
            else {
                values[index] = value;
            }
        },
        get: function (key) {
            return values[keys.indexOf(key)];
        }
    };
}

Answer 3

Have a look at my polyfill here. I am not advertising my polyfill, rather all I am saying is that it is the simplest and most straightforward I have yet to find, and thus it is the most suitable for learning and educational analysis. Basically, how it works is it uses a lookup table for the keys and a corresponding value table as visualized below.

var k = {}, j = [], m = document, z = NaN;
var m = new Map([
    [k, "foobar"], [j, -0xf], [m, true], [z, function(){}]
]);




Index      Key                 Value
##### ################    ################
0.    k ({})              "foobar"
1.    j ([])              -15
2.    m (Document)        true
3.    z (NaN)             function(){}

Internally, each item is stored at a different index, or at least that is the way I like to do it. This is also similar to the way the browser implements it internally. Unfortunately, I have seen some other polyfills that attempt to instead store the key on the object itself, and mess with all the internal methods to hide it, resulting in the entire webpage running 10000% slower and the maps being so slow that it takes nearly a full millisecond just to set and get new properties. Plus, I cannot fathom how many countless hours they waisted just trying to monkey-patch all the internal methods such as hasOwnProperty.

As for how and why my polyfill works, javascript objects are stored at a different place in memory. That is why [] !== [] and indexOf on an array of javascript objects works properly. It is because they are not the same array.