Help us understand the problem. What is going on with this article?

連想配列はMapを使うべきは本当か?

More than 1 year has passed since last update.

ES2015が出るまではJavaScriptで連想配列を扱う場合はObjectを使用するのが通常でした。ES2015からMapが登場し、こちらを使用すべきと言われています。それは果たして本当なのでしょうか?

連想配列とは何か?

単純な配列は単なる値の順列と考えられます。値が一つ一つ順番に並んでおり、入っている値の数(同じオブジェクトが重複して入っている場合もある)がその配列の長さであり、0または1から始まるインデックスでアクセスできるというものです。複数のオブジェクトをひとまとめに扱う場合、この単純な配列であってもそれなりに使用できますが、インデックスは整数しか使えず、飛び飛びに使うことはできず1、ある値を探すには順番に見に行くしか無いなど、色々と不便なところがあります。そこで、インデックスに任意の名前をつけて、目的の値をすばやく取得できるようにしたのが連想配列です。

連想配列の基本要件

連想配列はkeyとvalueのペアの配列とも考えられます。しかし、keyとvalueのペアの配列で単純に置き換えられるかというとそうでもありません。より有用に使うには連想配列が満たすべき要件があります。

  • keyには配列のように整数のみと言った制限は無く、任意の名前を付けることができます。ただし、keyに任意の型を使用できるという必須ではなく、任意の文字列程度でも十分です。
  • valueには任意の値を入れることができます。型の制限は設けるべきではありません。また、複数の値を入れることができる場合もありますが、必須ではありません。
  • 追加、変更、削除ができます。2
  • 任意のkeyで定数時間O(1)の計算量でvalueを検索できます。
  • 全てのkeyを順番に取得できます。ただし、keyの順序が固定である必要はありません。
  • メモリ容量や実装上の制限を除けば、登録できる数に制限はありません。

単純なペアの配列との一番の違いは、keyを検索してvalueを取得する計算量が定数時間O(1)であるということです。単純なペアの配列ではO(n)の計算量が必要になります。

Objectは連想配列用に用意されたわけでは無い

ObjectはJavaScriptの初期からある機能です。プロパティとその値と組合せは単純ではありますが、強力です。プロトタイプベースオブジェクト指向の根幹をなすばかりか、環境レコードもObjectの考えで作られています。連想配列に使う目的で用意されたわけではありませんが、連想配列としても使えないことは無かったため、古くからObjectを連想配列として使うコードが存在していました。

Objectは連想配列の要件を満たすのか?

Objectを連想配列として見るとどうなのでしょうか?プロパティ名とプロパティ値をkeyとvalueのペアと見なせますが、次のような性質があります。

  • keyには文字列(String)とシンボル(Symbol)のみです。文字列とシンボル以外をkeyに使用する場合は、自動的に文字列に変換されます。3
  • keyによる検索にハッシュテーブルを使わなければならないという要件はありません。
  • 検索時にkeyが見つからない場合は、親のプロトタイプからkeyを検索します。(プロトタイプチェーン)

Objectリテラルを使用した場合、Object.prototypeが親になります。Object.prototypeにはビルトインでいくつかのプロパティが入っているため、それらを参照した場合は、自分自身に設定されていなくても取得されてしまいます。

ハッシュテーブルという要件が無いため、keyからvalueを取得する場合、O(1)であるという保証はありません。しかし、頻繁に使用される機能であるため、O(1)になるように実装されているとみなしても問題ないでしょう。Objectリテラルから生成した場合は、親のプロトタイプは高々一つですので、極端に遅くなると言うことは想定しなくても良いでしょう。

さて、一見すると問題ないようにも見えます。ですが、本当にそうでしょうか?たとえば、toStringというkeyを付けた場合はどうなるでしょうか?

const x = {
    toString: "hoge"
};
const y = `x is ${x}`;

このプログラムはエラーになります。toStringに限らずObject.prototypeのビルトインプロパティを上書きした場合、なんらかしらの予期せぬ動作を引き起こす可能性が0ではありません。となると、任意の名前をkeyに割り当てられると言うことは無いのかも知れません。

さらには次のコードを見てください。

const x = {
    __proto__: {
        a: 42
    }
};
console.log(x["a"]);

__proto__自体は環境依存ではあるのですが、ほとんどの環境において、42と出力されることでしょう。これは親のプロパティを見に行くという性質の応用に過ぎませんが、連想配列としてみた場合は余計なことをしていると言わざるを得ません。親のプロトタイプをnullとする。つまり、Object.create(null)で生成するとプロトタイプ関係はある程度緩和してくれますが、便利なはずのObjectリテラルでは親が設定されたままです。

他にもObject.defineProperty()等を使うと順列操作にあらわれない特殊なkeyを作ったり、取得は出来るが変更できないkeyを作ったり出来ます。そのObject全体に対して一切の変更を出来なくすることは出来ますが、それら特殊な操作だけを制限することはできません。

連想配列のためのMap

Objectは連想配列として使うには欠点があり、また、余計な機能が付いています。そこで本当の連想配列としてES2015から用意されたのがMapです。Mapは連想配列の要件を満たすだけでなく、任意のオブジェクトをkeyにできるという利点もあります。数値と文字列は厳密に区別され、1"1"は同じではありません。

では、Mapは何も問題が無いかというとそうでもありません。

Mapには専用のリテラルが存在しない

Mapを作成するには次のように書く必要があります。

const map = new Map([
    ['a', 42],
    [0, 'hoge'],
]);

Objectリテラルと比べると冗長です。なれれば問題ないのかも知れませんが、可読性が高いとも言い難いです。

MapをそのままJSONに変換できない

JavaScriptでデータのやり取りや保存を行う場合はJSONが便利ですが、JSONはJavaScriptのリテラル表記から作られたと言うこともあり、Map専用のJSONの表記はありません。JSON.stringifyJSON.parseで変換やパースを行う場合は一工夫必要になります。

const obj = {
    data: new Map([
        ['a', 42],
        [0, 'hoge'],
        [{ name: 'taro', age: 18 }, [6, 12, 15, 18]],
    ]),
    list: [
        new Map([
            ['b', 8],
            ['c', 10],
        ]),
        10,
        new Map([
            [new Map([]), new Map([
                [true, 1],
                [false, 0],
            ])],
        ]),
    ],
};

const jsonStr = JSON.stringify(obj, function (key, val) {
    if (val instanceof Map) {
        return {
            __type__: 'Map',
            __value__: [...val]
        };
    }
    return val;
});

const newObj = JSON.parse(jsonStr, function(key, val) {
    if (val != null && val.__type__ === 'Map') {
        return new Map(val.__value__);
    }
    return val;
});


console.log(jsonStr);
console.log(obj);
console.log(newObj);

変換方法は色々ありますが、JSON.stringifyJSON.parseで対になる形でなければなりません。また、ある形式のObjectやStringを特殊な形式とする必要がある(上のコードではObjectで実現している)ため、その形式と同じObjectやStringを区別できないという欠点があります。

最大の間違いはObjectリテラルをMapに変換しようとする事です。Objectリテラルではkeyが文字列の場合しか表現できないため、相互変換では意味が失われることになります。

Mapのデータをやり取りしたいのであればYAMLを使えば良いのでは?

JSONではなくYAMLであれば、情報の損失なくMapをシリアライズ化することが出来ます。YAMLのマップではキーに対して文字列であるという制限がなく、また、独自のタイプを追加することも可能だからです。主なライブラリの対応状況を調べました。

残念ながら全滅です。すぐには対応は難しいと思われます。

keyの区別はカスタマイズできない

連想配列にとって重要なのはkeyの区別です。どのkeyが同じであり、どのkeyが異なるかというのは重要です。Mapではkeyが同じであるかどうかを調べるのに==とも===とも異なる特殊な動作になります。

  1. NaN同士は同じと判定されます。(本来NaN === NaNです)
  2. +0-0は同じと判定されます。(===と同じ動作ですが、+0-0は厳密には異なる値です)
  3. 同じ型かつ同じ値のプリミティブ値同士は同じと判定されされます。(===と同じ動作です)
  4. 同じオブジェクト同士は同じと判定されます。(===と同じ動作です)
  5. それ以外はすべて異なると判定されます。(===と同じ動作です)

NaN同士以外は===と同じですが、問題はオブジェクト同士です。オブジェクトが同じというのは、中身が同じでは無く、オブジェクトそのものが同じで無ければなりません。

const map = new Map([
    [{name: 'taro'}, 'I am Taro!'],
    [{name: 'hanako'}, 'I am Hanako!'],
]);
console.log(map.get({name: 'taro'}));
console.log(map.get([...map.keys()].filter(k => k.name === 'taro')[0]));

1回目のgetはうまくいかず、2回目のgetのようにしなくては取り出せません。オブジェクトをkeyにした場合、同じ内容のオブジェクトを指定しても取り出し出来ません。キーの一覧から目的のオブジェクトを取り出して使う等の工夫が必要です。これでは、せっかくのO(1)検索がその前のkey取得でO(n)必要になってしまいます。

つまり、Mapは任意のオブジェクトが指定できるようになったと言っても、プリミティブ値でないと使うのが難しいと言うことです。同値かどうかをカスタマイズできれば良かったのですが、そのようには作られていません。

連想配列にはMapを使うべきか?

Mapは連想配列としては完全なはずですが、リテラル、JSON、keyの同値について不満がある結果になってしまいました。Java等の一部の言語でも同じことが言えると言うこともあり、そこまで不満とは思わないという人がいるかと思います。しかし、PythonやRubyのような最初から連想配列が完備されていた他のスクリプト言語に比べると、やはり不満点は大きく見えます。

では、使わない方が良いのかというと、そうではないと思います。Objectは任意に増加していくkeyを扱うにはいささか作りが悪すぎます。TypeScriptやFlowでの型定義の仕方も考えるとkeyであるプロパティ名が固定されたレコードや構造体として扱いたいところです。任意のkeyを扱うなら、どのような値がkeyになるかわからないなら、ObjectよりMapを積極的に使っていった方が、Object固有の動作で躓くと言うことも無くなるのでは無いでしょうか?


  1. インデックスを飛び飛び使うことができる言語もありますが、暗黙的にその間にも意味が無い値が入っているとみなされます。JavaScriptもその一つです。 

  2. Immutableの場合は、追加、変更、削除がされた新しい連想配列を生成できることが要件になります。 

  3. Array(配列)もObjectの一種であるため、仕様的にはインデックスの整数値は文字列として扱われます。つまり、arr[1]arr["1"]常に同じです。ただし、+0以上$2^{53}-1$以下は整数インデックス(integer index)、+0以上$2^{32}-1$は配列インデクス(array index)として定義され、エキゾティックObjectであるArrayでは特別な動作が定義されており、実装上は整数値で管理されている可能性が高いです。 

raccy
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした