🤜🏿 🙃 👩🏽‍🎤 V8でのマップデータ構造の実装について 👲🏿 📴 🤞🏽

標準のECMAScript 2015 ES6として知られているが、そこのような多くの新しいJavaScriptの-コレクションがありMap、Set、WeakMapとWeakSet。これらは、標準のJavaScript機能への優れた追加機能のようです。これらは、Node.jsのコアで、さまざまなライブラリ、アプリケーションで広く使用されています。今日はコレクションについて話しMap、V8での実装の詳細を理解し、得られた知識に基づいていくつかの実用的な結論を導き出します。

ES6標準は、データ構造サポートを実装するために取るべきアプローチを明確に示していませんMap。それはそれを実装するための可能な方法に関するいくつかのヒントを与えるだけです。また、期待されるからの情報が含まれていますMapパフォーマンスメトリック：

Mapオブジェクトは、ハッシュテーブル、または平均してコレクションの要素へのサブリニアアクセスを提供するその他のメカニズムを使用して実装する必要があります。 Map仕様で使用されるデータ構造は、Mapオブジェクトの観察可能なセマンティクスを説明することのみを目的としています。これらは、これらのオブジェクトを実装するための実際のモデルとしては考えられていませんでした。

ご覧のとおり、この仕様により、JSエンジンを作成する人に多くの自由が与えられます。しかし同時に、実装Mapに使用される特定のアプローチ、そのパフォーマンス、およびメモリ消費特性に関する特定のガイドラインはありません。アプリケーションの重要な部分でデータ構造が使用されている場合Mapそして、そのようなデータ構造に大量の情報を書き込む場合、実装に関するMap確かな知識は確かにあなたにとって大きな利益になります。

私はJava開発の経験があり、Javaコレクションに慣れています。ここでは、インターフェイスのさまざまな実装から選択できMap、対応するクラスがサポートしている場合は、選択した実装を微調整することもできます。さらに、Javaでは、標準ライブラリの任意のクラスのオープンソースコードをいつでも読み取って、その実装に慣れることができます（もちろん、新しいバージョンで変更される可能性がありますが、効率を上げる方向にのみ変更されます）。そのためMap、V8でオブジェクトがどのように機能するかを学ぶことに抵抗できませんでした。

始める前に、以下で説明するのは、Node.jsの新しい開発バージョンに組み込まれているV8 8.4エンジンを指していることに注意してください（より正確には、commit238104cについて話します）。）。仕様外のものを期待する必要はありません。

マップ実装の基礎となるアルゴリズム

まず、データ構造はMapハッシュテーブルに基づいていると言います。以下では、ハッシュテーブルがどのように機能するかを知っていることを前提としています。ハッシュテーブルに慣れていない場合は、最初にハッシュテーブル（たとえば、ここ）について読んでから、この記事を読み続ける必要があります。

オブジェクトに関する重要な経験があるMap場合は、すでに矛盾に気付いている可能性があります。つまり、ハッシュテーブルは、アイテムを反復処理するときに一定の順序でアイテムを返すことが保証されていません。また、ES6仕様では、オブジェクトを実装するには、オブジェクトMapをトラバースするときに、要素が追加された順序で要素を返す必要があると規定されています。結果として、実装のための「古典的な」アルゴリズムMap合っていない。ただ、多少の変更はありますが、まだまだ使える気がします。

V8は、TylerCloseによって提案されたいわゆる「決定論的ハッシュテーブル」を使用します。 TypeScriptに基づく次の疑似コードは、このようなハッシュテーブルの実装に使用される基本的なデータ構造を示しています。

interface Entry {
    key: any;
    value: any;
    chain: number;
}
 
interface CloseTable {
    hashTable: number[];
    dataTable: Entry[];
    nextSlot: number;
    size: number;
}

ここで、インターフェースCloseTableはハッシュテーブルを表します。これには、hashTableハッシュコンテナの数と同じサイズの配列が含まれています。インデックスを持つ配列要素は、-番目のハッシュコンテナにN対応し、配列にNあるそのヘッド要素のインデックスを格納しますdataTable。また、この配列には、テーブルのレコードが挿入された順序で含まれています。エントリはインターフェイスによって表示されますEntry。最後に、各エントリには、chainハッシュコンテナエントリのチェーン内（より正確には、単一リンクリスト内）の次のエントリを指すプロパティがあります。

新しいレコードがテーブルに挿入されるたびに、dataTableインデックス付きの配列要素に格納されますnextSlot..。このプロセスでは、対応するハッシュコンテナのデータを更新する必要もあります。これにより、挿入されたレコードが、単一リンクリストの新しい最後の要素になります。

レコードがテーブルから削除されると、dataTable（たとえば、そのプロパティkeyとvalue値に書き込むことによって）から削除されますundefined。次に、その前のエントリとそれに続くエントリが直接リンクされます。お気づきかもしれませんが、これは、削除されたすべてのエントリが引き続きdataTable。内のスペースを占有することを意味します。

さて、パズルの最後のピースです。テーブルが（現在のレコードと削除されたレコードの両方の）レコードでいっぱいの場合、サイズを大きくして再ハッシュ（再構築）する必要があります。テーブルのサイズは下向きに変更できます。

このアプローチでは、データ構造をトラバースすることは、Map配列をトラバースすることと同じdataTableです。これにより、レコードがテーブルに挿入される順序が保持され、標準が満たされることが保証されます。これを念頭に置いて、ほとんどの（すべてではないにしても）JSエンジンが、基盤となる実装メカニズムの1つとして決定論的ハッシュテーブルを使用することを期待しますMap。

アルゴリズムの実践的研究

実際のアルゴリズムを調べるのに役立ついくつかの例を見てみましょう。我々が持っていると仮定CloseTable2個のハッシュコンテナ（hastTable.length）、4つの要素（これの全容量をdataTable.length）。このテーブルには、次の内容が含まれています。

// ,    -, 
// ,     ,   function hashCode(n) { return n; }
table.set(0, 'a'); // => - 0 (0 % 2)
table.set(1, 'b'); // => - 1 (1 % 2)
table.set(2, 'c'); // => - 0 (2 % 2)

この例で取得したテーブルの内部表現は、次のようになります。

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: 0,
            value: 'a',
            chain: 2 //  <2, 'c'>
        },
        {
            key: 1,
            value: 'b',
            chain: -1 // -1    
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3, //    
    size: 3
}

メソッドを使用してレコードを削除するtable.delete(0)と、ハッシュテーブルは次のようになります。

const tableInternals = {
    hashTable: [0, 1],
    dataTable: [
        {
            key: undefined, //  
            value: undefined,
            chain: 2 
        },
        {
            key: 1,
            value: 'b',
            chain: -1
        },
        {
            key: 2,
            value: 'c',
            chain: -1
        },
        //  
    ],
    nextSlot: 3,
    size: 2 //  
}

テーブルにさらにいくつかのレコードを追加する場合は、ハッシュする必要があります。このプロセスについては、以下で詳しく説明します。

データ構造を実装するときにも同じアプローチを適用できますSet。唯一の違いは、これらのデータ構造にはプロパティが必要ないことですvalue。V8

のオブジェクトの背後にあるものがわかったので、次にMap進む準備ができました。

実装の詳細

MapV8でのデータ構造の実装はC ++で記述され、その後JSコードに対応するメカニズムへのアクセスが許可されます。に関連するコードのほとんどは、およびMapクラスにOrderedHashTableありますOrderedHashMap。これらのクラスがどのように機能するかはすでにわかっています。あなたは自分のコードで自分を見てみたい場合、あなたはそれを見つけることができ、ここで、こことここ。V8

での実装の実際的な詳細に特に関心があるためMap、最初にテーブルの容量がどのように設定されているかを理解する必要があります。

テーブル容量

V8では、ハッシュテーブル（データ構造Map）の容量は常に2の累乗です。ハッシュコンテナの使用率について言えば、常に数値2で表されます。つまり、テーブルの最大容量2 * number_of_bucketsはハッシュコンテナの数の2倍です。空のオブジェクトを作成する場合Map、その内部ハッシュテーブルには2つのハッシュコンテナがあります。結果として、そのようなオブジェクトの容量は4レコードに等しくなります。

オブジェクトの最大容量には制限がありますMap。 64ビットシステムでは、これは約1,670万レコードになります。この制限はMap、ヒープ内のデータ構造を表現する際の特殊性によるものです。後で話します。

そして最後に、テーブルの増減の要因は、常にいくつかの数値に2を掛けることで表されます。つまり、記述されたテーブルに4つのレコードが追加された後、次の挿入操作でテーブルを再洗浄する必要があり、その間にテーブルのサイズが2つ増加します。回。したがって、テーブルのサイズを小さくすると、テーブルは2分の1になります。

私はそれを理解されているように私は、ソースコードで見たことは、正確に動作することを確実にするために、私はそれを作ること、Node.jsのに組み込まれたV8エンジンのコードを変更しMap、新たなプロパティがbuckets含まハッシュコンテナの数に関する情報。この変更の結果はここにあります..。Node.jsのこの特別なアセンブリでは、次のスクリプトを実行できます。

const map = new Map();
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${i}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
  map.set({}, {});
}

このスクリプトは、Map100レコードをデータ構造に挿入するだけです。これは、起動後にコンソールに表示されるものです。

$ ./node /home/puzpuzpuz/map-grow-capacity.js
size: 0, buckets: 2, capacity: 4
size: 5, buckets: 4, capacity: 8
size: 9, buckets: 8, capacity: 16
size: 17, buckets: 16, capacity: 32
size: 33, buckets: 32, capacity: 64
size: 65, buckets: 64, capacity: 128

ご覧のとおり、テーブルがいっぱいになると、サイズが変わるたびに2倍になります。それでは、テーブルから要素を削除して、テーブルを減らしてみましょう。

const map = new Map();
for (let i = 0; i < 100; i++) {
  map.set(i, i);
}
console.log(`initial size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
 
let prevBuckets = 0;
for (let i = 0; i < 100; i++) {
  map.delete(i);
  if (prevBuckets !== map.buckets) {
    console.log(`size: ${map.size}, buckets: ${map.buckets}, capacity: ${map.buckets * 2}`);
    prevBuckets = map.buckets;
  }
}

これは、このスクリプトが出力するものです。

$ ./node /home/puzpuzpuz/map-shrink-capacity.js
initial size: 100, buckets: 64, capacity: 128
size: 99, buckets: 64, capacity: 128
size: 31, buckets: 32, capacity: 64
size: 15, buckets: 16, capacity: 32
size: 7, buckets: 8, capacity: 16
size: 3, buckets: 4, capacity: 8
size: 1, buckets: 2, capacity: 4

ここでも、number_of_buckets / 2要素が少なくなるたびにテーブルのサイズが小さくなることがわかります。

ハッシュ機能

これまで、V8がオブジェクトに格納されているキーのハッシュコードをどのように計算するかについては触れていませんMap。そして、これは重要な質問です。

数値として分類できる値については、衝突の可能性が低いいくつかのよく知られたハッシュ関数が使用されます。

文字列値の場合、ハッシュコードは値自体に基づいて計算されます。その後、このコードは内部ヘッダーにキャッシュされます。

そして最後に、オブジェクトの場合、ハッシュはランダムな数値に基づいて計算され、発生した内容は内部ヘッダーにキャッシュされます。

Mapオブジェクトを使用した操作の時間の複雑さ

またはMapなどのデータ構造に対して実行される操作のほとんどは、これらのデータ構造を検索する必要があります。「クラシック」ハッシュテーブルの場合と同様に、この場合の検索の時間の複雑さはです。最悪のシナリオを想像してみてください。テーブルがいっぱいになったとき、つまり、テーブルが座席から占有されたときです。この場合、すべてのレコードは単一のハッシュコンテナに属し、必要なレコードはレコードチェーンの最後にあります。このようなシナリオでは、このエントリを見つけるための手順を実行する必要があります。一方、最良のシナリオでは、テーブルがいっぱいで、各ハッシュコンテナにレコードが2つしかない場合、レコードを見つけるのに必要な手順は2つだけです。setdeleteO(1)

NNN

ハッシュテーブルの特定の操作は非常に高速ですが、ハッシュ操作の場合はそうではありません。ハッシュ操作の時間の複雑さはO(N)です。ヒープに新しいハッシュテーブルを割り当てる必要があります。さらに、テーブルから要素を挿入または削除する操作の一部として、必要に応じて再ハッシュが実行されます。したがって、たとえば、通話map.set()は予想よりもはるかに「高額」になる可能性があります。幸い、ハッシュ操作が実行されることはめったにありません。

メモリ消費

もちろん、基礎となるハッシュテーブルMapは何らかの方法でヒープに格納する必要があります。いわゆる「補助ストレージ」に格納されます。そして、ここに別の興味深い事実があります。テーブル全体（したがって、に配置されるすべてのものMap）は、固定長の単一の配列に格納されます。このアレイの構造を次の図に示します。

マップデータ構造をメモリに格納するために使用される

配列配列の個々の部分には、次の目的があります。

ヘッダー：ハッシュコンテナの数やから削除されMapたアイテムの数などの一般的な情報が含まれます。
ハッシュコンテナの詳細：ここにhashTable、例の配列に対応するコンテナに関するデータを保存します。
ハッシュテーブルエントリ：これは、配列に対応するデータが格納される場所dataTableです。つまり、ハッシュテーブルエントリに関する情報が含まれています。各レコードは、アレイ内の3つのセルを占有します。1つはキーを格納し、2つ目は値を格納し、3つ目はチェーン内の次のレコードへの「ポインター」を格納します。

配列のサイズについて言えば、大まかにはと見積もることができますN * 3,5。これNがテーブルの容量です。これがメモリ消費の観点から何を意味するかを理解するために、64ビットシステムがあり、V8のポインタ圧縮機能が無効になっていると想像してみましょう。この場合、配列の各要素を格納するために8バイトが必要です。その結果Map、約100万レコードを含むデータ構造を格納するには、29MBのヒープメモリが必要になります。

結果

この記事ではMap、JavaScriptのデータ構造に関連する多くのことを取り上げました。要約しましょう：

V8Mapは、実装に決定論的ハッシュテーブルを使用します。このデータ構造は、他のJSエンジンにも実装されている可能性が非常に高いです。
作業をサポートするメカニズムMapはC ++で実装され、その後、JavaScriptからアクセス可能なAPIの形式で提示されます。
オブジェクトを使用して実行される操作の時間の複雑さについて説明すると、オブジェクトはMap、「クラシック」ハッシュテーブルを操作する場合と同様に、複雑になりO(1)ます。この場合、ハッシュ操作の時間の複雑さはO(N)です。
64- Map 1 29 , .
, , Set.

Map JavaScript-?

V8でのマップデータ構造の実装について