TL;DR

babel-polyfillでMapのpolyfillを使う場合、2点注意することがある。

ES5環境では、Object.freezeなど、オブジェクトにプロパティを生やせなくする操作をしたオブジェクトをキーに持つマップを作ると、getなどの操作がO(1)でなくO(n)になってしまう。
ES3環境では、オブジェクトをキーに持つマップを作成すると、キーに使用したオブジェクトに勝手に列挙可能なプロパティを生やされるので、for-inしているコードがバグる可能性がある。

前提知識

Mapといえば、ES2015の新機能である。
ES5以前は辞書型に相当するものを使いたい場合、オブジェクトを代用品として騙し騙し使うことが多かったが、ES2015でMapが提供されたことで、これからはオブジェクトにあった制約を気にせずに辞書型を使うことができるようになった。
オブジェクトを辞書型の代用品として使う場合に制約となっていたのは、文字列しかキーにできないということであった。

// うまく動かない
var pseudoMap = Object.create(null);
var key1 = {a: 5};
var key2 = {b: 6};
pseudoMap[key1] = "A";
pseudoMap[key2] = "B";
console.log(pseudoMap[key1]); // "B"

Mapが現れたことで、あらゆる要素をキーにできるようになり、オブジェクトにあった制約を気にしなくてもよくなった。¹

// うまく動く
const map = new Map();
const key1 = {a: 5};
const key2 = {b: 6};
map.set(key1, "A");
map.set(key2, "B");
console.log(map.get(key1)); // "A"

そこで、Mapを使って生産性を上げていきたいわけだが、ブラウザ環境でMapを使う場合、IE10以前などのMapが未実装のブラウザがネックとなる。
これを解決してくれるのがbabel-polyfillである。
babel-polyfillはMapが未実装な環境でも、Mapをエミュレートしたものを用意してくれるので、Mapを使うコードが動くようになる。
以下のコードをBabelとBrowserifyに食わせると、Mapが未実装な環境でも動くコードが出力される。

// うまく動く
import "babel-polyfill";

const map = new Map();
const key1 = {a: 5};
const key2 = {b: 6};
map.set(key1, "A");
map.set(key2, "B");
console.log(map.get(key1)); // "A"

問題

babel-polyfillは、ES5以前の環境においてES2015のMapをエミュレートしたものを用意してくれる。
しかし、ES5以前では文字列以外をキーにする辞書型を作ることは難しかったはずである。
babel-polyfillはES5以前の環境でどのようにしてMapの挙動を再現しているのだろうか？

コードリーディング

本記事執筆時点の最新版であるbabel-polyfill@6.5.0は、本記事執筆時点ではcore-js@1.2.6を呼び出す。
core-js@1.2.6のes6.map.jsがMapをエミュレートしたものを定義している場所であり、これを読んでいけばbabel-polyfillが（より正確にはcore-jsが）どのようにしてMapの挙動を再現しているか分かるはずである。

重要な部分を抜粋する。
以下はMapのコンストラクタに相当する部分。
$.collection-strong.js 46〜53行目より。

    var C = wrapper(function(that, iterable){
      strictNew(that, C, NAME);
      that._i = $.create(null); // index
      that._f = undefined;      // first entry
      that._l = undefined;      // last entry
      that[SIZE] = 0;           // size
      if(iterable != undefined)forOf(iterable, IS_MAP, that[ADDER], that);
    });

いろいろとモジュール化のために頑張っていてこれ単体だと読みにくいが、簡略化すると次のようなことを行っている。

function Map(iterable) {
    // ES3でもiframeを利用したハック（闇）により、Object.create(null)相当のことができる
    this._i = Object.create(null); // index
    this._f = undefined;           // first entry
    this._l = undefined;           // last entry
    this._s = 0;                   // size
    if (iterable != undefined) {
        // forOf関数はこのfor-of文に相当することをES5以前の範囲で行っている
        for (let [key, value] of iterable) {
            this.set(key, value);
        }
    }
}

以下はMap.prototype.setに相当する部分。
es6.map.js 14〜16行目と$.collection-strong.js 107〜129行目より。

  set: function set(key, value){
    return strong.def(this, key === 0 ? 0 : key, value);
  }

  def: function(that, key, value){
    var entry = getEntry(that, key)
      , prev, index;
    // change existing entry
    if(entry){
      entry.v = value;
    // create new entry
    } else {
      that._l = entry = {
        i: index = fastKey(key, true), // <- index
        k: key,                        // <- key
        v: value,                      // <- value
        p: prev = that._l,             // <- previous entry
        n: undefined,                  // <- next entry
        r: false                       // <- removed
      };
      if(!that._f)that._f = entry;
      if(prev)prev.n = entry;
      that[SIZE]++;
      // add to index
      if(index !== 'F')that._i[index] = entry;
    } return that;
  },

簡略化すると次のようなことを行っている。
つまりlinked listを作っている。

Map.prototype.set = function (key, value) {
    // ES2015の仕様では-0を+0として扱うのでその調整
    key = key === 0 ? 0 : key;
    // getEntry関数は後述
    // prevとindexはプロパティアクセスの数を減らして処理を高速化するための変数
    var entry = getEntry(this, key), prev, index;
    if (entry) {
        entry.v = value;
    } else {
        // linked listを作るための種々の処理
        this._l = entry = {
            // fastKey関数は後で詳しく見るが、keyに対応するユニークな文字列を取得する関数。
            // ただしユニークな文字列を取得できない場合があり、その場合は"F"を返す。
            i: index = fastKey(key, true), // <- index
            k: key,                        // <- key
            v: value,                      // <- value
            p: prev = this._l,             // <- previous entry
            n: undefined,                  // <- next entry
            r: false                       // <- removed
        };
        if (!this._f) this._f = entry;
        if (prev) prev.n = entry;
        this._s++;
        // fastKey(key)でkeyに対応するユニークな文字列を取得できない場合を除き、
        // this._i[fastKey(key)]でkeyに対応するentryを引っ張ってこれるようにする。
        if (index !== "F") this._i[index] = entry;
    }
    return this;
};

見れば分かるが、単純なlinked listではなく、インデックス（this._i）付きのlinked listである。
インデックスを作っているので、Map.prototype.getは、fastKey(key)がkeyに対応するユニークな文字列を取得できる場合に、O(1)になる。
それが分かるMap.prototype.getの実装は以下。
es6.map.js 9〜12行目、$.collection-strong.js 34〜42行目、$.collection-strong.js 18〜32行目、$.hide.js 3〜8行目より。

  get: function get(key){
    var entry = strong.getEntry(this, key);
    return entry && entry.v;
  },

var getEntry = function(that, key){
  // fast case
  var index = fastKey(key), entry;
  if(index !== 'F')return that._i[index];
  // frozen object case
  for(entry = that._f; entry; entry = entry.n){
    if(entry.k == key)return entry;
  }
};

  , id = 0;

var fastKey = function(it, create){
  // return primitive with prefix
  if(!isObject(it))return typeof it == 'symbol' ? it : (typeof it == 'string' ? 'S' : 'P') + it;
  if(!$has(it, ID)){
    // can't set id to frozen object
    if(!isExtensible(it))return 'F';
    // not necessary to add id
    if(!create)return 'E';
    // add missing object id
    hide(it, ID, ++id);
  // return object id with prefix
  } return 'O' + it[ID];
};

module.exports = require('./$.descriptors') ? function(object, key, value){
  return $.setDesc(object, key, createDesc(1, value));
} : function(object, key, value){
  object[key] = value;
  return object;
};

簡略化するとそれぞれこうである。（3つ目と4つ目はまとめてある）

Map.prototype.get = function (key) {
    var entry = getEntry(this, key);
    if (entry) {
        return entry.v;
    } else {
        return undefined;
    }
};

function getEntry(that, key) {
    var index = fastKey(key);
    // O(1)でkeyに対応するentryを返す
    if (index !== 'F') return that._i[index];
    // それができない場合はしょうがないのでO(n)で全entryを舐める
    for (var entry = that._f; entry; entry = entry.n) {
        if (entry.k === key) return entry;
    }
}

// 説明のために仮想的な変数IS_ES5をコード中に入れている。
// ES5のときIS_ES5はtrue、ES3のときIS_ES5はfalseとする。
var id = 0;
function fastKey(it, create) {
    // プリミティブ値の場合
    if(!((typeof(it) === "object" && it !== null) || typeof(it) === "function")) {
        if (typeof(it) === "symbol") return it;
        return (typeof(it) === "string" ? "S" : "P") + it;
    }
    // IDは定数で、具体的には"Symbol(id)_g.kdx26466ypb"のような文字列である。
    // この文字列はウィンドウの起動毎に変化する。
    if (!Object.prototype.hasOwnProperty.call(it, ID)) {
        // Object.freezeなどでオブジェクトにプロパティを生やせない場合、"F"を返す
        if (IS_ES5 && !Object.isExtensible(it)) return "F";
        // 今回のコードリーディングの範囲ではこのコードは無視していい
        // if (!create) return "E";
        // オブジェクトにオブジェクト固有のユニークなIDを記録するプロパティを生やす
        if (IS_ES5) {
            Object.defineProperty(it, ID, {
                enumerable: false,
                configurable: true,
                writable: true,
                value: ++id
            });
        } else {
            it[ID] = ++id;
        }
    }
    return "O" + it[ID];
}

つまりまとめると、次のようなコードは概ねどのような処理をしているかというと、

var map = new Map();
var key1 = {a: 5};
var key2 = {b: 6};
map.set(key1, "A");
map.set(key2, "B");
console.log(map.get(key1)); // "A"

ES5ではこのような処理を、

var map = {
    _i: Object.create(null)
};
var key1 = {a: 5};
var key2 = {b: 6};
Object.defineProperty(key1, "Symbol(id)_g.05o43rwmu7p", {
    enumerable: false,
    configurable: true,
    writable: true,
    value: 1
});
map._i["O" + key1["Symbol(id)_g.05o43rwmu7p"]] = {v: key1};
Object.defineProperty(key2, "Symbol(id)_g.05o43rwmu7p", {
    enumerable: false,
    configurable: true,
    writable: true,
    value: 2
});
map._i["O" + key2["Symbol(id)_g.05o43rwmu7p"]] = {v: key2};
console.log(map._i["O" + key1["Symbol(id)_g.05o43rwmu7p"]].v); // "A"

ES3ではこのような処理をしている。

var map = {
    _i: (function () {
        // Object.create(null)相当のオブジェクトを返す闇のハック
    })()
};
var key1 = {a: 5};
var key2 = {b: 6};
key1["Symbol(id)_g.y81m4r51d0u"] = 1;
map._i["O" + key1["Symbol(id)_g.y81m4r51d0u"]] = {v: key1};
key2["Symbol(id)_g.y81m4r51d0u"] = 2;
map._i["O" + key2["Symbol(id)_g.y81m4r51d0u"]] = {v: key2};
console.log(map._i["O" + key1["Symbol(id)_g.y81m4r51d0u"]].v); // "A"

そしてこの処理は、キーがObject.freezeなどされていてオブジェクトにプロパティを生やせない場合にはうまくいかないので、フォールバック用にlinked listを用意しているわけである。

注意点

TL;DRにも書いたが、ここまでコードを読んでくるとbabel-polyfillが提供するMapには2つ注意点があることが分かる。

ES5環境での注意点

ES5環境では、Object.freezeなど、オブジェクトにプロパティを生やせなくする操作をしたオブジェクトをキーに持つマップを作ると、getなどの操作がO(1)でなくO(n)になってしまう。

var map = new Map();
var keys = [];
for (var i = 0; i < 100000; i++) {
    keys.push(Object.freeze({}));
}
for (var i = 0; i < 100000; i++) {
    map.set(keys[i], i);
}
console.log(map.get(keys[99999])); // O(n)かかる

ES3環境での注意点

ES3環境では、オブジェクトをキーに持つマップを作成すると、キーに使用したオブジェクトに勝手に列挙可能なプロパティを生やされるので、for-inしているコードがバグる可能性がある。

var map = new Map();
var key = {a: 5, b: 6};
map.set(key, "foo");
for (var i in key) {
    if (key.hasOwnProperty(i)) {
        console.log(i); // 意図していないプロパティ"Symbol(id)_g.nruj6vfbt60"がループに混入する
    }
}

まとめ

polyfillは便利だが限界もあるので、その特性を把握した上で正しく使おう。

本題からは外れるが、ES2015のMapはまだJavaのMapなどと比べると制約がある。それは、何をキーとして同じ値であると見なすかを独自に定義できないということである。現状は、基本的に===がtrueを返せばキーとして同じ値であると見なされ（例外はNaNと-0）、この等値性の定義をいじることはできない。つまりES2015時点ではconst map = new Map(); map.set({a: 5}, "A"); console.log(map.get({a: 5}));のようなコードは期待したようには動かない。このようなコードを動かせるようになるとしたらES2016以降になる。 ↩