MegaHash - C++で開発されたNode.js向け高速ハッシュテーブル

• 1,600万個制限のES6 Mapsを置き換え: 10億個以上のキーを保存可能

• C++で開発され、Node.js向けラッパーを含む

→ 1秒あたり50万キーのRead/Writeが可能

→ メモリオーバーヘッドが少ない

→ V8 Heapに保存されない

→ Buffer、文字列、数値、ブール値、オブジェクトをサポート

• ES6 Map APIと基本互換: get, set, has, ddelete, clear, length

• 内部的にSeparate Chaining手法を使用: インデックス + 連結リスト方式

[kbumsik]

うわ、あんなに大きなMapを使う理由ってあるんでしょうか。

[xguru]

実際に Node.JS で 2^24 個を超えるキーを Map に入れると、ヒープエラーが発生します。

これはバグではなく実装上定義された制限で、これに関する V8 開発者の回答が StackOverflow にあります。

https://stackoverflow.com/a/54466812/166418

• Map を保存する FixedArray の最大サイズは 1GB

• 64ビットシステムでは 1GB / 8B = 2^30 / 2^3 = 2^27 ~= 134M なので、FixedArray は最大 1億3400万個の要素を保存可能

• Map はエントリごとに 3 つの要素（Key, value, next bucket link）が必要で、最大ロード数はバケット衝突を避けるため 50% に制限される。

→ 容量は 2 の累乗である必要があるため、2^27 / (3 * 2) の計算結果を次の下の累乗に切り下げると、2^24 が最大値