Javascriptのハッシュテーブルデータ構造

ハッシュテーブルは、データを関連付けて格納するデータ構造です。ハッシュテーブルでは、データは配列形式で格納され、各データ値には独自のインデックス値があります。目的のデータのインデックスがわかっている場合、データへのアクセスは非常に高速になります。

したがって、データのサイズに関係なく、挿入および検索操作が非常に高速なデータ構造になります。ハッシュテーブルは、ストレージメディアとして配列を使用し、ハッシュ手法を使用して、要素が挿入される場所または要素が配置される場所のインデックスを生成します。

ハッシュ

ハッシュは、キー値の範囲を配列のインデックスの範囲に変換する手法です。モジュロ演算子を使用して、キー値の範囲を取得します。サイズ20のハッシュテーブルの例を考えてみましょう。次のアイテムが保存されます。アイテムは（キー、値）形式です。

ここに、キーを受け取り、テーブルのインデックスを生成するハッシュ関数があります。これらのインデックスは、値が格納されている場所を示します。これで、キーに関連付けられた値を検索するときはいつでも、キーに対してハッシュ関数を再度実行して、ほぼ一定の時間で値を取得する必要があります。

ただし、ハッシュ関数の設計はかなり困難です。例を見てみましょう-

次のハッシュ関数があるとしましょう-

例

function modBy11(key) {
   return key % 11;
}

そして、保存したいキーと値のペアでこれを実行し始めます。たとえば、-

• （15、20）-ハッシュコード：4
• （25、39）-ハッシュコード：3
• （8、55）-ハッシュコード：8
• （26、84）-ハッシュコード：4

ここで、衝突が発生していることがわかります。つまり、最初に15を格納してから、このハッシュ関数でキー26に遭遇した場合、同じホールでこのエントリを修正しようとします。これは衝突と呼ばれます。そして、そのような状況を処理するには、衝突処理メカニズムを定義する必要があります。明確に定義された単純な衝突解決アルゴリズムがいくつかあります。例-

• 線形プロービング：このアルゴリズムでは、空のセルが見つかるまで次のセルを調べることで、配列内の次の空の場所を検索できます。この例では、4の穴が取られているので、5を埋めることができます。
個別の連鎖：この実装では：ハッシュテーブル内の各場所をリストに関連付けます。衝突が発生するたびに、このリストの最後にキーと値のペアを追加します。チェーンが長くなり続けると、検索時間が大幅に長くなる可能性があります。

ハッシュテーブルがどのように機能し、衝突解決をどのように使用できるかを理解したので、HashTableクラスを実装しましょう。

実装するメソッド

これらのメソッドを実装に実装します-

• put（key、value）：新しいキーと値のペアをハッシュテーブルに追加します
• get（key）：キーに関連付けられた値を取得します
• remove（key）：テーブルからキーと値のペアを削除します
• forEach（）：すべてのキーと値のペアを反復処理できます
• static join（）：2つのハッシュテーブルを新しいものに結合する静的メソッド