ES6マップとセット：オブジェクトキーはどのように効率的に索引付けされますか？

Question

ES6では、マップとセットでオブジェクトをキーとして使用できます。しかし、ES6の仕様はこれらのデータ構造の基本的な実装を規定していないので、O（1）または少なくともsublinearの検索を保証するために現代のJSエンジンがキーをどのように格納しているのだろうか？

Javaのような言語では、プログラマは明示的に（良好な）hashCodeメソッドを提供することができます。このメソッドは、キースペース内でキーを均等にハッシュして、パフォーマンスを保証します。しかし、JSにはこのような機能がないため、MapsおよびSetsの実装で何らかのハッシュを使用していると見なすのはまだ公正ですか？

すべての情報をお待ちしております！

Answer 1

はい、実装はハッシュに基づいており、一定のアクセス時間があります（償却されます）。

「オブジェクトアイデンティティを使用しています」は単純化されています。 ES Maps and SetsではSameValueZeroアルゴリズムを使用して、同等性を判断しています。

V8の実装では、文字列と数字の「実際の」ハッシュを計算し、乱数をオブジェクトの「ハッシュ」として選択し、後でアクセスするためにこれらのオブジェクトに非公開のプロパティとして格納します。

memoryAddress % keySpaceを使用すると、ガベージコレクタはオブジェクトを移動させ、オブジェクトが移動した可能性があるたびにすべてのマップとセットを再ハッシュするため、機能しません（これは理想的ではなく、将来変更される可能性があります）。法外に複雑で高価になる。