TypeScript 実践アルゴリズムシリーズ (XII): Map と HashMap の実装

この記事では、辞書とハッシュテーブルの実装のアイデアを詳しく説明し、TypeScript を使用して実装します。興味のあるフロントエンド開発者は、ぜひこの記事を読んでください。

[[342361]]

実装のアイデア
辞書とハッシュ テーブルはキーと値のペアの形式でデータを保存するため、JavaScript のオブジェクトを使用して実装できます。

辞書の実装
辞書は、キーと値のペアの形式でデータを格納します。そのキーは文字列型であり、呼び出し元が渡すキーになります。

完全な辞書クラスには、キーが辞書内にあるかどうかを判断する、辞書に要素を追加する、キーに従って辞書に格納されている要素を削除する、キーに従って辞書内の要素を検索する、辞書に格納されているすべての要素を取得するなどのメソッドが必要です。次に、これらのメソッドの実装アイデアを分析しましょう。

辞書（セット）に要素を追加する

setメソッドは、キーと値の2つのパラメータを受け入れます。
パラメータの有効性を判断します。キーと値が null | undefined でない場合は、要素を辞書に追加し、それ以外の場合は直接 false を返します。
パラメータが有効な場合、パラメータキーを文字列に変換し、文字列に変換されたキーを辞書のキーとして使用し、キーと値をオブジェクトに格納し、文字列に変換されたキーにオブジェクトを格納します。
上記の操作の後、辞書に要素が正常に追加され、true が返されました。
キーが辞書内に存在するかどうかを判定する (hasKey)

hasKeyメソッドは1つのパラメータを受け入れます: key
辞書内のデータはオブジェクトの形式で保存されているため、キーを直接文字列に変換し、辞書オブジェクトの属性として渡すことができます。返された結果が undefined | null であるかどうかを判断することで、キーが辞書内にあるかどうかを知ることができます。
キーに応じて辞書に格納されている値を取得する (get)

getメソッドは1つのパラメータを受け入れます: key
キーを文字列に変換し、それを辞書オブジェクトの属性として渡し、変数を使用してその戻り値を受け取ります。
戻り値が null かどうかを判定します | undefined
戻り値が null | undefined でない場合はオブジェクト内の値を返し、それ以外の場合は undefined を返します。
キーに基づいて辞書から要素を削除します (削除)

削除メソッドは1つのパラメータを受け入れます: key
対象パラメータが辞書オブジェクトに存在するかどうかを判断し（hasKeyメソッドを呼び出し）、存在しない場合は直接falseを返します。
辞書オブジェクト内に対象要素が存在する場合は、キーを文字列に変換し、辞書オブジェクトにパラメータとして渡します。最後に、オブジェクトの delete メソッドを呼び出して対象キーを削除し、true を返します。
辞書に保存されているすべてのオブジェクトを取得します (keyValues)

keyValues メソッドはパラメータを一切受け取らず、オブジェクトの配列を返します。まず、取得したオブジェクトを格納するための配列変数 (valuePairs) を宣言します。辞書オブジェクト内のすべてのキーを取得します。
取得したキーを走査し、走査したキーをパラメーターとして辞書オブジェクトに渡します。
辞書オブジェクトから返された値を valuePairs に入れて返します。
辞書に格納されているすべてのキー（keys）を取得する & 辞書に格納されているすべての値（value）を取得する

keys メソッドは、取得したキーを格納するための配列変数 (keys) を宣言するための任意のパラメータを受け入れます | 取得した値を格納するための配列変数 (values) を宣言します
辞書に格納されているすべてのオブジェクトを取得します（keyValuesメソッドを呼び出します）
トラバースして取得したオブジェクト配列のキーを取得したい場合は、現在トラバースしている要素のキー値を keys 配列に格納し、それ以外の場合は values 配列に値の値を格納します。
戻りキー | 値
辞書内のデータの反復処理 (forEach)

forEachメソッドはコールバック関数をパラメータとして受け取り、そのコールバック関数にはキーと値の2つのパラメータがあります。
辞書内のすべてのデータを取得します。取得したデータをトラバースし、コールバック関数のパラメータを呼び出して、現在トラバースしているオブジェクトのキーと値をコールバック関数に渡し、変数 (result) を使用して結果を保存します。 result が false の場合、辞書内の要素がトラバースされたことを意味します。ループを終了して辞書のサイズ (size) を取得し、keyValues メソッドを呼び出して、その配列の長さを返します。

辞書が空かどうか (isEmpty) を判断し、size メソッドを呼び出して 0 かどうかを判断して、結果を返します。

辞書をクリア（クリア）し、辞書オブジェクトを空のオブジェクトに初期化するだけです

辞書内のデータを文字列に変換する (toString)

toString メソッドはパラメータを受け取りません。辞書が空の場合は、空の文字列を直接返します。
辞書が空でない場合は、辞書内のすべてのデータを取得します。
辞書内の各オブジェクトを格納する変数 (objString) を宣言します。その初期値は、辞書オブジェクト配列のトラバース番号 0 で取得したオブジェクトです。トラバースしたデータと objString を連結し、objString を返します。
ハッシュテーブルの実装
ハッシュ テーブル (ハッシュ テーブルとも呼ばれる) は、辞書の別の実装です。ハッシュ テーブルと辞書の違いは、キー値の格納方法です。

辞書は要素を格納するときに、要素を格納する前にキーを文字列に変換します。

ハッシュ テーブルに要素を格納する場合、キーをハッシュし、ハッシュ値を取得した後に要素を格納します。

要素を検索する場合、辞書はデータ構造全体を反復処理して対象要素を見つける必要がありますが、ハッシュ テーブルはハッシュ値によって格納されます。対象要素の場所をすばやく見つけるには、対象要素のハッシュ値を計算するだけで済みます。したがって、ハッシュ テーブルは辞書よりも効率的です。

ハッシュテーブルはハッシュテーブルと多くの類似点がありますが、異なるキーにデータを格納するため、使用するメソッドをインターフェースに記述し、それぞれの特性に応じてこのインターフェースを実装する必要があります。次に、辞書とは異なるハッシュテーブルでのメソッドの実装を分析しましょう。

ハッシュテーブルに要素を追加する (put)

辞書の実装と同様に、有効かどうかを判断するための 2 つのパラメーターを受け取ります。キーがパラメーターとして使用され、hashCode 関数が呼び出され (独自に実装)、そのハッシュ値が計算されます。取得されたハッシュ値はハッシュ テーブルにキーとして保存され、その値は辞書と一致します。
ハッシュ値を計算する（hashCode）

ハッシュ値を生成するためのソリューションは多数あります。この記事では、最も一般的に使用される 2 つのソリューションのみを紹介します。
使用したいハッシュ関数を呼び出します (loseloseHashCode | djb2HashCode)
loseloseHashCodeはハッシュ値を計算します

まず、キーが数字かどうかを判断します。数字の場合は、実行せずにそのまま返します。キーを文字列に変換するためのハッシュ演算は行いません。ハッシュ値のトラバーサルから文字列に変換されたキーを格納する変数 (ハッシュ) を宣言します。js charCodeAt 関数を呼び出して、各文字の Unicode エンコーディングを見つけます。トラバーサルが完了すると、取得した Unicode コードがハッシュに追加されます。値が大きくなりすぎないように、ハッシュ値を 37 で割って余りを取り、ハッシュを返します。
djb2HashCodeはハッシュ値を計算します

loseloseHashCode メソッドと同じように、キーが数値かどうかをチェックし、それを文字列に変換します。違いは、ハッシュの初期値が 5381 であることです。
キーを文字列に変換してからトラバースし、トラバースした各文字の Unicode コードを取得し、ハッシュ値に 33 を掛けて、取得した Unicode コードを加算します。トラバースが完了したら、ハッシュ値を 1013 で割って余りを取り、ハッシュを返します。
キーに従ってハッシュテーブル内の要素を取得する (get)

キーをハッシュして結果を取得し、それをハッシュ テーブル オブジェクトにパラメータとして渡し、ハッシュ テーブル内の対象キーの要素を取得して、結果が null | undefined かどうかを判断します。そうであれば undefined を返し、そうでない場合はその値を返します。
キーに基づいてハッシュテーブルから要素を削除します (削除)

キーをハッシュして、そのハッシュ値がハッシュ内にあるかどうかを判断します。ない場合は false を返します。
キーはハッシュテーブルにあり、計算されたハッシュ値はハッシュテーブルに属性として渡され、deleteメソッドが呼び出されて対象要素のキーが削除され、trueが返されます。
他のメソッドは辞書と同じ方法で実装されますが、唯一の違いはキーの処理方法です。

ハッシュ テーブルでのハッシュ値の競合の処理<br /> HashMap を使用する場合、loseloseHashCode メソッドを呼び出してハッシュ値を計算すると、競合率が非常に高くなります。ここでは、ハッシュ衝突の問題に対処するためによく使用される 2 つの方法を紹介します。

別リンク
個別リンク方式では、ハッシュ テーブル内の各位置に対してリンク リストが作成され、その中に要素が格納されます。これは競合を解決する最も簡単な方法ですが、追加のストレージスペースを占有します。

分離リンク方式はHashMapのストレージ構造を変更するだけなので、HashMapを継承してHashMapと異なるメソッドを書き換えることができます。

プライベート属性テーブルの変数名を変更します。分離リンク方式の値はリンクリスト型であり、HashMapはValuePair型を使用しているため、jsには実際のプライベート属性はなく、そのテーブル属性の型は継承中に変更できないため、変数名（tableLink）を変更する必要があります。

putメソッドをオーバーライドする

HashMap と同様に、キーと値の有効性を判断し、キーのハッシュ値を計算し、それを変数 (位置) に格納し、位置をパラメーターとして tableLink に渡して、null | undefined かどうかを判断します。
null | undefined でない場合は、tableLink の位置にリンク リストを作成し、Key & value オブジェクトを tableLink の位置のリンク リストに追加し、追加が成功した場合は true を返します。
get メソッドを書き直す (リンクリストから要素を取得する必要があります)

キーのハッシュ値を計算し、変数（位置）に格納します。位置に格納されているリンクリスト構造の要素を取得します。リンクリストが空でない場合は、リンクリストの先頭から、現在トラバースされているリンクリスト要素のキーがターゲットパラメータのキーと同じになるまでトラバースし、対応する値を返します。リンクリストが空の場合は、undefined を返します。
削除メソッドを書き直す（リンクリストから要素を削除する必要があります）

キーのハッシュ値を計算し、変数（位置）に格納します。その位置にあるリンクリスト構造の要素を取得します。リンクリストが空でない場合は、リンクリストの先頭から走査を開始します。
現在走査されているリンク リスト要素がターゲット パラメーター キーと同じ場合、現在のリンク リスト内の要素はリンク リストから削除されます。
削除後、リンクリストが空の場合は、tableLinkの位置要素を直接削除します。リンクリストが空の場合は、undefinedを返します。
clearメソッドを書き直し、tableLinkを空のオブジェクトにポイントします。

keyValuesメソッドを書き換えます。HashMapはリンクリストを格納しており、格納されたオブジェクト（valuePair）をリンクリストから取得する必要があります。

取得したValuePairオブジェクトを格納するための配列変数（valuePairs）を宣言します。tableLink内のすべてのキーを取得し、int型に変換して変数（keys）に格納します。
キーをトラバースし、現在トラバースしているリンク リスト構造内の要素のデータを取得し、変数 (linkedList) に格納します。linkedList が空でない場合は、リンク リストの先頭からリンク リスト内のデータをトラバースし、現在トラバースしているリンク リスト内の要素を取得し、valuePairs に格納します。
戻り値ペア
リニアプローブ
競合を解決するもう 1 つの方法は線形探索です。これは、別のデータ構造ではなくテーブルに要素を直接格納することで競合を処理するため、線形と呼ばれます。

テーブル内の特定の位置に新しい要素を追加する場合、インデックス位置がすでに占有されているときは、位置 + 1 を試します。位置 + 1 も占有されている場合は、位置 + 2 を試し、ハッシュ テーブルで空いている位置が見つかるまでこれを繰り返します。

次に、線形プローブを使用して競合を解決するためにどのメソッドを書き直す必要があるかを見てみましょう。

putメソッドをオーバーライドする

HashMapと同様に、パラメータの有効性と渡されたパラメータの数を判断してキーのハッシュ値を計算し、それを変数（位置）に格納する必要があります。
テーブルの位置が占有されているかどうかを判断します。占有されていない場合は、その位置に新しいオブジェクトを作成し、キーと値をその中に格納します。占有されている場合は、変数 (インデックス) を使用して、位置 + 1 の値を受け取ります。テーブルのインデックス位置の値をトラバースします。空でない場合、インデックスは増加し続けます。
テーブル内に空の位置が見つかった場合、テーブルのインデックス位置にキーと値を格納するための新しいオブジェクトが作成され、true が返されます。
getメソッドをオーバーライドする

キーのハッシュ値を計算し、変数（位置）に格納します。
テーブルの位置にある要素が null | undefined かどうかを判定し、そうでない場合は undefined を返します。
テーブルの位置にある要素のキーがターゲット パラメータのキーと等しいかどうかを判断します。等しい場合は、位置にある値を直接返します。等しくない場合は、変数 (インデックス) を使用して位置 + 1 にある値を格納します。テーブルのインデックスにある値を走査します。インデックスにある値が空でなく、インデックスにあるキーがターゲット パラメータのキーと等しくない場合は、インデックスが増分されます。ループが終了したら、現在のテーブルのインデックスにある要素のキーがターゲット パラメータのキーと等しいかどうかを判断します。等しい場合は、インデックスにある値を返します。
削除メソッドをオーバーライドする

キーのハッシュ値を計算し、変数（位置）に格納します。
テーブルの位置が null かどうかを判断します。null の場合は、直接 false を返します。
テーブルの位置のキーがターゲットパラメータのキーと等しい場合は、その位置の要素を削除し、この削除に副作用があるかどうかを確認し、要素の位置を調整してtrueを返します。
等しくない場合は、位置の後の値を見つけるための変数 (インデックス) を宣言する必要があります。デフォルト値は位置 + 1 です。
テーブルのインデックス位置の要素をトラバースします。それが null でなく、そのキーがターゲット キーと等しくない場合、インデックスが増分されます。トラバース手法の後、インデックス位置の要素が null でなく、インデックス位置の要素のキーがターゲット パラメータのキーと等しい場合、テーブルのインデックス位置の要素を削除し、この削除に副作用があるかどうかを確認し、要素の位置を調整して、true を返します。
削除操作に副作用があるかどうかを検証するための新しいメソッド (verifyRemoveSideEffect) が追加されました。要素の削除後に競合が発生した場合は、空の位置が生成されないように、競合する要素を前の位置に移動する必要があります。

verifyRemoveSideEffect メソッドは、削除するキーとテーブル内の削除されたキーの位置 (removedPosition) というパラメータを受け取ります。
キーのハッシュ値を計算し、変数（ハッシュ）に格納する
削除されたキー位置の次の位置（インデックス）を受け取る変数を使用します。デフォルトは removedPosition+1 です。
テーブルを走査し、インデックス位置の要素が null でない場合は、現在のインデックス位置のキーのハッシュ値を取得し、それを変数 (posHash) に格納します。
posHash が hash 以下、または posHash が removedPosition 以下である場合、テーブル内のインデックスの要素を removedPosition に割り当てます。テーブル内のインデックスの要素を削除し、インデックスを removedPosition に割り当てます。
次のサイクル判定に進む
実装コード
分析後、実装のアイデアが得られました。次に、上記のアイデアをコードに変換します。

マップインターフェースの作成
辞書とハッシュ テーブルには多くの共通メソッドがあるため、共通メソッドをインターフェイスに分離し、さまざまなニーズに応じて異なるインターフェイスを実装する必要があります。

新しいMap.tsファイルを作成します。新しいdictionary-list-models.tsファイルを作成します。dictionary-list-modelsにValuePairクラスを追加してエクスポートします。このクラスは辞書に値を格納するために使用されます。

 // オブジェクトを生成する
エクスポートクラスValuePair<K,V>{
    コンストラクタ(パブリック キー: K、公開値: V) {} 
 
    文字列(){
 `[#${this.key } : ${this.value}]`を返します。
    }
 }

ValuePairクラスをMapにインポートし、後で必要になるメソッドを追加して定義し、戻り値の型を指定します。

 {ValuePair}をインポート  "../../utils/dictionary-list-models.ts" ; 
 
デフォルトインターフェースMap<K,V>をエクスポートします。
    hasKey(キー: K ): ブール値;
設定?(キー:K、値:V):ブール値;
    put?(キー: K、値: V ): ブール値;
    ハッシュコード?(キー: K ): 数値;
    削除(キー:K):ブール値;
    get(キー:K):V|未定義;
    キー値(): ValuePair<K, V>[];
    キー（）：K[];
値（）：V[];
    forEach(callbackFn: (キー: K、値: V) => any ): void;
サイズ(): 数値;
    空かどうかをチェックする
    クリア():void;
    toString():文字列;
 }

辞書クラスの実装
新しいDictionary.tsファイルを作成し、Mapインターフェースを実装するためのDictionaryクラスを追加します。

デフォルトのクラスDictionary<K, V>をエクスポートし、 Map<K, V>を実装します。 
 
 }

辞書保存用のプライベート属性テーブルを宣言する

プライベートテーブル: { [キー: 文字列]: ValuePair<K, V> };

コンストラクタでテーブルを初期化し、値から文字列への関数を宣言してデフォルト値を割り当てます。

 // toStrFn は値を文字列に変換するために使用されます。このロジックを自分で実装し、インスタンス化時に渡すことができます。
    コンストラクター(プライベートtoStrFn: (キー:K) =>文字列=defaultToString) {
        テーブルを次のように変更します。
    }

setメソッドの実装

// 辞書に要素を追加する
（キー：K、値：V）を設定します。
      if (キー!= null && 値 != null ) {
          //キーを文字列に変換します。辞書に必要なキーは文字列形式です。
          const tableKey = this.toStrFn(キー);
          this.table [tableKey] = 新しい ValuePair(キー、 値 );
戻る 真実;
      }
戻る 間違い;
  }

hasKeyメソッドの実装

hasKey(キー:K) {
 this.table [ this.toStrFn( key )]!= nullを返します。
 }

getメソッドの実装

get(キー:K) {
       const valuePair = this.table [this.toStrFn(キー)];
戻り値 valuePair == null ? 未定義: valuePair.value;
   }

削除メソッドの実装

削除(キー:K) {
    if (this.hasKey(キー)) {
 this.table [ this.toStrFn( key )]を削除します。
戻る 真実;
    }
戻る 間違い;
 }

keyValuesメソッドの実装

キー値(): 値のペア<K, V>[] {
    /* ES2017で導入されたObject.valuesメソッドを使用して、オブジェクトに格納されている対応するすべてのキーの値を直接取得し、配列に格納します */
    定数値のペア = [];
    const keys = Object.keys( this.table );
 ( i = 0 とします; i < keys.length; i++){
        valuePairs.push( this.table [keys[i]])
    }
 valuePairsを返します。
 }

キーメソッドの実装

キー（）{
      // マップを直接使用してオブジェクトのキーを取得できます 
      // this.keyValues().map(valuePair=> valuePair.key )を返します。
      定数キー = [];
      定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++) {
          キーをプッシュします(valuePairs[i] .key );
      }
リターンキー。
  }

値メソッドの実装

値（）{
     定数値= [];
     定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++) {
値​​.push(valuePairs[i].value);
     }
戻る 値​​;
 }

forEach メソッドの実装

forEach(コールバックFn: (キー: K, 値: V) =>任意) {
      定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++) {
          const result = callbackFn(valuePairs[i] .key , valuePairs[i].value);
          結果が偽の場合
              壊す;
          }
      }
  }

size、isEmpty、clearメソッドを実装する

サイズ（） {
 this.keyValues().lengthを返します。
 } 
 
 空です() {
 this.size () === 0を返します。
 } 
 
 クリア（） {
     テーブルを次のように変更します。
 }

toString メソッドの実装

文字列を渡す
      空の場合（）{
戻る  '' ;
      } 
 
      定数 valuePairs = this.keyValues();
      objString = `${valuePairs[0].toString()}` とします。
 ( i = 1 とします; i < valuePairs.length; i++) {
          objString = `${objString},${valuePairs[i].toString()}`;
      }
 objStringを返します。
  }

完全なコードについては、Dictionary.ts をご覧ください。

テストコードを書く
上記では辞書クラスを実装しました。次に、上記のコードが正常に実行されるかどうかをテストしてみましょう。

定数辞書 = 新しい辞書();
 dictionary.set ( "name" , "张三" );
 dictionary.set ( "年齢" ,20);
 dictionary.set ( "id" ,198);
 console.log( "名前が辞書にあるかどうかを判断します" , dictionary.hasKey( "name" ));
 // idという名前のキーを削除します 
 dictionary.remove( "id" );
 console.log( "idが辞書内にあるかどうかを判断します" , dictionary.hasKey( "id" ));
 console.log( "辞書に保存されているデータを文字列に変換します" , dictionary.toString())
 // 辞書内のnameという名前の値を取得します
console.log( "辞書内の name という名前の値" 、 dictionary.get( "name" ));
 // 辞書に格納されているすべての値を取得します
console.log( "辞書に保存されているすべての値" , dictionary.keyValues());
 // 辞書内のすべてのキーを取得します
console.log( "辞書に保存されているすべてのキー" , dictionary.keys());
 // 辞書内のすべての値を取得する
console.log("辞書に保存されているすべての値" , dictionary.values ());
 // 辞書内の各キーと値のペアを反復処理します
定数obj = {};
 dictionary.forEach(関数(キー, 値) {
    obj[キー] = 値;
 })
コンソールログ(obj)

完全なコードについては、DictionaryTest.js を参照してください。

ハッシュテーブルの実装
新しい HashMap クラスを作成し、Map インターフェースを実装します。

 HashMap<K,V>クラスをエクスポートし、Map<K, V>を実装します{ 
 
 }

テーブルを宣言し、そのタイプを指定する

保護されたテーブル:{[キー:数値]:ValuePair<K, V>};

コンストラクタでテーブルを初期化し、値から文字列への関数を指定して、呼び出し元が値文字列関数を渡せるようにします。

コンストラクター(保護されたtoStrFn: (キー: K) => 文字列 = defaultToString) {
    テーブルを次のように変更します。
 }

hashCode、loseLoseHashCode、djb2HashCodeメソッドを実装する

// ハッシュコードを生成する
 ハッシュコード(キー:K):数値{
 this.loseloseHashCode(キー)を返します。
 } 
 
 // loseloseはハッシュ関数を実装します
 loseloseHashCode(キー: K ): 数値 {
     if (typeof key === "number" ){
戻る 鍵;
     }
     const tableKey = this.toStrFn(キー);
     ハッシュを 0 にします。
 ( i = 0 とします; i < tableKey.length; i++){
         // 各文字のASCIIコードを取得し、それをハッシュに連結します
         ハッシュ += tableKey.charCodeAt(i);
     }
ハッシュ%37を返します。
 } 
 
 // djb2 はハッシュ関数を実装します
 djb2HashCode(キー: K ): 数値 {
     if (typeof key === "number" ){
戻る 鍵;
     } 
 
     // パラメータを文字列に変換する
     const tableKey = this.toStrFn(キー);
     ハッシュ = 5381;
 ( i = 0 とします; i < tableKey.length; i++){
         ハッシュ = (ハッシュ * 33) + tableKey.charCodeAt(i);
     }
ハッシュ%1013を返します。
 }

putメソッドの実装

put(キー:K、値:V):ブール値{
      if (キー!= null && 値 != null ) {
          const 位置 = this.hashCode(キー);
          this.table [位置] = new ValuePair(キー、値 );
戻る 真実;
      }
戻る 間違い;
  }

getメソッドの実装

get(キー:K):V|未定義{
       const valuePair = this.table [this.hashCode(キー)];
戻り値 valuePair == null ? 未定義: valuePair.value;
   }

hasKeyメソッドの実装

hasKey(キー:K):ブール値{
 this.table [ this.hashCode( key )]!= nullを返します。
  }

削除メソッドの実装

削除(キー:K):ブール値{
       if (this.hasKey (キー)) {
 this.table [ this.hashCode( key )]を削除します。
戻る 真実;
       }
戻る 間違い;
   }

keyValues、キー、値のメソッドを実装する

キー値(): 値のペア<K, V>[] {
      定数値のペア = [];
      // オブジェクト内のすべてのキーを取得し、 int型の配列に変換します
      const keys = Object.keys( this.table ).map(item => parseInt(item));
 ( i = 0 とします; i < keys.length; i++){
          valuePairs.push( this.table [keys[i]]);
      }
 valuePairsを返します。
  } 
 
  キー（）：K[] {
      定数キー = [];
      定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++){
          キーをプッシュします(valuePairs[i] .key );
      }
リターンキー。
  } 
   
値（）：V[] {
      定数値= [];
      定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++){
値​​.push(valuePairs[i].value);
      }
戻る 値​​;
  }

isEmpty、size、clearメソッドを実装する

isEmpty():ブール値 {
 this.values ().length === 0を返します。
  } 
   
サイズ（）：数値{
 this.keyValues().lengthを返します。
  } 
   
  クリア(): void {
      テーブルを次のように変更します。
  }

forEach メソッドの実装

forEach(callbackFn: (キー: K, 値: V) =>任意): void {
     定数 valuePairs = this.keyValues();
 ( i = 0 とします; i < valuePairs.length; i++){
         const result = callbackFn(valuePairs[i] .key ,valuePairs[i].value);
         結果が偽の場合
             壊す;
         }
     }
 }

toString メソッドの実装

toString(): 文字列 {
      （これが空の場合）{
戻り値``
      } 
 
      定数 valuePairs = this.keyValues();
      objString = `${valuePairs[0].toString()}` とします。
 ( i = 1 とします; i < valuePairs.length; i++){
          objString = `${objString},${valuePairs[i].toString()}`;
      }
 objStringを返します。
  }

完全なコードについては、HashMap.ts をご覧ください。

テストコードを書く

上記のコードが正常に実行されるかどうかをテストしてみましょう。

定数hashMap = 新しいHashMap();
 hashMap.put( "name" , "张三" );
ハッシュマップにidを代入します。
 hashMap.put( "クラス" , "製品" );
 console.log( "HashMapにクラスが存在するかどうかを判断します" 、 hashMap.hasKey( "class" ));
ハッシュマップを削除します( "id" );
 console.log( "HashMap に id が存在するかどうかを確認します" 、 hashMap.hasKey( "id" ))
 console.log(hashMap.get( "名前" ));
 hashMap.forEach(((キー、値) => {
    console.log(キー+ "=" + 値);
 }))
 console.log( "HashMap 内のデータが空かどうかを判断します" , hashMap.isEmpty());
 console.log( "HashMap内のすべてのキーに対応する値を出力します" , hashMap.keyValues());
 console.log( "HashMap内のすべてのキー値を取得します" , hashMap.keys());
 console.log(" HashMap内のすべてのValue値を取得します" , hashMap.values ());
 console.log( "HashMapのサイズを取得します" , hashMap.size ());
 console.log( "HashMap 内のデータを文字列出力に変換します" , hashMap.toString());
 console.log( "HashMap 内のデータをクリアします" );
ハッシュマップをクリアします。
 // ハッシュ値の競合問題をテストする
hashMap.put( 'Ygritte' , '[email protected]' );
 hashMap.put( 'Jonathan' , '[email protected]' );
 hashMap.put( 'Jamie' , '[email protected]' );
 hashMap.put( 'Jack' , '[email protected]' );
 hashMap.put( 'Jasmine' , '[email protected]' );
 hashMap.put( 'Jake' , '[email protected]' );
 hashMap.put( 'Nathan' , '[email protected]' );
 hashMap.put( 'Athelstan' , '[email protected]' );
 hashMap.put( 'スー' , '[email protected]' );
 hashMap.put( 'Aethelwulf' , '[email protected]' );
 hashMap.put( 'Sargeras' , '[email protected]' );
コンソールにログ出力します。

完全なコードについては、HashMapTest.js を参照してください。

ハッシュ競合問題を解決するためにリンクリストを分離する方法<br /> 上記のテストコードを実行したところ、一部の値が競合して置き換えられ、データが失われていることがわかりました。

リンクリストと組み合わせて競合の問題を解決する方法を見てみましょう。

新しいHashMapSeparateChaining.tsファイルを作成し、HashMapから継承したHashMapSeparateChainingクラスを追加します。

エクスポートデフォルトクラスHashMapSeparateChaining<K,V>はHashMap<K, V>を拡張します{ 
 
 }

プライベート プロパティ tableLink を宣言し、テーブル ストレージの型を定義します。

プライベート tableLink:{ [キー: 数値]: LinkedList<ValuePair<K, V>> };

コンストラクタでtoStrFnメソッドを宣言し、デフォルト値を割り当てて親クラスとテーブルを初期化します。

コンストラクター(保護されたtoStrFn: (キー: K) => 文字列 = defaultToString) {
      スーパー(toStrFn);
      this.tableLink = {};
  }

putメソッドをオーバーライドする

put(キー:K、値:V):ブール値{
      if (キー!= null && 値 != null ) {
          const 位置 = this.hashCode(キー);
          if (this.tableLink[位置] == null ){
              // 要素を追加する位置が空の場合は、リンクリストを作成します
              this.tableLink[位置] = 新しいLinkedList<ValuePair<K, V>>();
          }
          // 現在の要素を、その要素が現在追加されているリンクリストに追加します
          this.tableLink[位置].push(新しいValuePair(キー、値));
戻る 真実;
      }
戻る 間違い;
  }

getメソッドをオーバーライドする

get(キー:K):V | 未定義{
       // パラメータのハッシュ値を取得する
       const 位置 = this.hashCode(キー);
       // ターゲット要素の位置に格納されているリンクリスト構造の要素を取得します
       const linkedList = this.tableLink[位置];
       リンクリストがnullの場合、linkedList.isEmpty() は空です。
           // リンクリストのヘッダーデータを取得する
           現在のものをlinkedList.getHead()とします。
           while (現在値!= null ) {
               // リンクリストを走査し、リンクリスト内でターゲットパラメータと同じデータを検索します
               if (現在の.element . key === key ) {
                   // ターゲットキーに対応する値を返す
戻る 現在の.element.value;
               }
 current =現在の. next ;
           }
       }
未定義を返します。
   }

削除メソッドをオーバーライドする

削除(キー:K):ブール値{
     const 位置 = this.hashCode(キー);
     // ターゲット要素の位置に格納されているリンクリスト構造の要素を取得します
     const linkedList = this.tableLink[位置];
     リンクリストがnullの場合、linkedList.isEmpty() は空です。
         // リンクリストの先頭要素を取得する
         現在のものをlinkedList.getHead()とします。
         while (現在値!= null ) {
             // リンクリストを走査し、ターゲット要素と同じデータを検索します
             if (現在の.element . key === key ) {
                 // リンクリストから現在リンクリストにある要素を削除します
                 linkedList.remove(現在の要素);
                 リンクリストが空の場合（）{
                     // リンクリストが空の場合、ターゲット位置の要素を削除します
this.tableLink[位置]を削除します。
                 }
戻る 真実;
             }
 current =現在の. next ;
         }
     }
戻る 間違い;
 }

clearメソッドをオーバーライドする

クリア（） {
    this.tableLink = {};
 }

keyValuesメソッドをオーバーライドする

キー値(): 値のペア<K, V>[] {
      定数値のペア = [];
      // tableLink 内のすべてのキーを取得し、 int型に変換します
      const keys = Object.keys(this.tableLink).map(item=>parseInt(item));
 ( i = 0 とします; i < keys.length; i++){
          const linkedList = this.tableLink[keys[i]];
          リンクリストがnullの場合、linkedList.isEmpty() は空です。
              // リンクリスト内のデータを走査し、リンクリスト内のデータを valuePairs に格納します
              現在のものをlinkedList.getHead()とします。
              while (現在値!= null ) {
                  valuePairs.push(現在の.element);
 current =現在の. next ;
              }
          }
      }
 valuePairsを返します。
  }

完全なコードについては、HashMapSeparateChaining.ts をご覧ください。

テストコードを書く
上記の方法が正常に実行できるかテストしてみましょう。

定数hashMapSC = 新しいHashMapSeparateChaining();
 hashMapSC.put( "name" , "张三" );
 hashMapSC.put( "id" 、11);
 hashMapSC.put( "年齢" ,22);
 hashMapSC.put( "電話番号" , "09871588" );
 hashMapSC.remove( "id" );
 console.log(hashMapSC.get( "名前" ));
 console.log( "hashMap 内のデータが空かどうかを判断します" , hashMapSC.isEmpty());
コンソールにログ出力します。
 console.log( "forEach を使用して hashMap 内のデータを走査します" );
 hashMapSC.forEach((キー,値)=>{
    console.log(`${キー} = ${値}`);
 })
 console.log( "hashMap に格納されているすべてのキーを取得します" , hashMapSC.keys());
 console.log(" hashMapに格納されているすべての値を取得します" , hashMapSC.values ());
 console.log( "idがhashMap内にあるかどうかを判断します" , hashMapSC.hasKey( "id" ));
 console.log( "HashMap 内のデータをクリアします" );
ハッシュマップSC.clear();
 console.log( "HashMap 内のデータが空かどうかを判断します" , hashMapSC.isEmpty());
 console.log( "競合テスト" )
 hashMapSC.put( 'Ygritte' , '[email protected]' );
 hashMapSC.put( 'ジョナサン' , '[email protected]' );
 hashMapSC.put( 'Jamie' , '[email protected]' );
 hashMapSC.put( 'Jack' , '[email protected]' );
 hashMapSC.put( 'Jasmine' , '[email protected]' );
 hashMapSC.put( 'Jake' , '[email protected]' );
 hashMapSC.put( 'Nathan' , '[email protected]' );
 hashMapSC.put( 'Athelstan' , '[email protected]' );
 hashMapSC.put( 'スー' , '[email protected]' );
 hashMapSC.put( 'Aethelwulf' , '[email protected]' );
 hashMapSC.put( 'Sargeras' , '[email protected]' );
コンソールにログ出力します。

完全なコードについては、HashmapsParateChainingTest.jsにアクセスしてください

リニアプロービングは、ハッシュ衝突の問題を解決します
新しいHashmaplinearProbing.tsファイルを作成し、Hashmapから継承されたHashmaplinearProbingクラスを追加します

デフォルトクラスのhashmaplinearprobing <k、v> extends hashmap <k、v> { 
 
 }

コンストラクターの親クラスを初期化します

コンストラクタ() {
    素晴らしい（）;
 }

PUTメソッドをオーバーライドします

put（ key ：k、value：v）：boolean {
      if（ key ！= null && value！= null ）{
          const position = this.hashcode（ key ）;
          //挿入される現在の位置がテーブルに占有されているかどうかを判断します
          if（ this.table [position] == null ）{
              //現在の位置が占有されていません。キーと値をValuePairに入れて、現在のテーブルに挿入する要素に割り当てます
              this.table [position] = new ValuePair（ key 、value）;
          }それ以外{
              //位置が占有されており、空いている位置が見つかるまでインデックスを増やします
              index = position + 1とします。
              while（ this.table [ index ]！= null ）{
インデックス++;
              }
              //空いている位置を見つけ、キーと値をValuePairに入れて、挿入する位置の現在のテーブルの要素に割り当てます
              this.table [ index ] = new ValuePair（ key 、value）;
          }
戻る 真実;
      }
戻る 間違い;
  }

GETメソッドをオーバーライドします

get（ key ：k）：v |。
      const position = this.hashcode（ key ）;
      if（ this.table [position]！= null ）{
          //現在の位置の要素のキーがターゲット要素のキーに等しい場合、現在の位置の要素の値を直接返します
          if（ this.table [position] .key === key ） {
 this.table [ position ] .valueを返します。
          }
          //探している要素を見つけるか、空の位置を見つけるまで位置が増加します
          index = position + 1とします。
          while（ this.table [ index ]！= null && this.table [ index ] .key ！== key ）{
インデックス++;
          }
          //増分が完了したら、現在のテーブルのインデックスのキーがターゲットキーに等しいかどうかを判断します 
          if（ this.table [ index ]！= null && this.table [ index ] .key == key ） {
 this.table [ index ] .valueを返します。
          }
      }
未定義を返す;
  }

削除メソッドをオーバーライドします

削除（ key ：k）：boolean {
    const position = this.hashcode（ key ）;
    if（ this.table [position]！= null ）{
        if（ this.table [position] .key === key ） {
 this.table [position]を削除します。
            //削除した後、この削除に副作用があるかどうかを確認し、要素の位置を調整します
            this.verifyRemovesideEffect（ key 、position）;
戻る 真実;
        }
        index = position + 1とします。
        while（ this.table [ index ]！= null && this.table [ index ] .key ！== key ）{
インデックス++;
        }
        if（ this.table [ index ]！= null && this.table [ index ] .key == key ） {
 this.table [ index ] ;​
            this.verifyRemovesIdeEffect（ key 、 index ）;
戻る 真実;
        }
    }
戻る 間違い;
 }

verifyRemovesideEffectメソッドを実装します

//削除操作に副作用がないことを確認します
private verifyRemovesideEffect（ key ：k、removedposition：number）{
    //削除されたキーのハッシュ値を計算します
    const hash = this.hashcode（ key ）;
    //削除された要素の次の位置から開始し、空の位置が見つかるまでテーブルを横断します
    //空の位置が見つかった場合、それは要素が適切な位置にあり、移動する必要がないことを意味します
    index = removedposition + 1とします。
    while（ this.table [ index ]！= null ）{
        //現在トラバースされている要素キーのハッシュ値を計算します
        const poshash = this.hashcode（ this.table [ index ] .key ）;
        console.log（ `現在トラバースエレメントのハッシュ= $ {poshash}、最後に削除されたkey = $ {removedposition}`）のハッシュ
        if（poshash <= hash || poshash <= removedposition）{
            //現在トラバースされている要素のハッシュ値が、削除された要素のハッシュ値以下、または最後に削除されたキーのハッシュ値以下の場合（削除ポジション）
            //現在の要素を削除ポジション位置に移動する必要があります
            this.table [removedposition] = this.table [ index ] ;
            //移動が完了したら、現在のインデックス位置で要素を削除します
this.table [ index ] ;​
            //削除ポジションの値をインデックスに更新します 
            removedposition = index ;
        }
インデックス++;
    }
 }

完全なコードについては、hashmaplinearprobing.tsにアクセスしてください

テストコードの作成
上記の方法が正常に実行されるかどうかをテストします

const hashmaplp = new hashmaplinearprobing（）;
 console.log（ "競合する要素削除テスト" ）;
 hashmaplp.put（ 'ygritte' 、 '[email protected]' ）;
 Hashmaplp.put（ 'Jonathan' 、 '[email protected]' ）;
 hashmaplp.put（ 'jamie' 、 '[email protected]' ）;
 hashmaplp.put（ 'jack' 、 '[email protected]' ）;
 hashmaplp.put（ 'jasmine' 、 '[email protected]' ）;
 hashmaplp.put（ 'jake' 、 '[email protected]' ）;
 hashmaplp.put（ 'nathan' 、 '[email protected]' ）;
 hashmaplp.put（ 'athelstan' 、 '[email protected]' ）;
 hashmaplp.put（ 'sue' 、 '[email protected]' ）;
 hashmaplp.put（ 'aethelwulf' 、 '[email protected]' ）;
 hashmaplp.put（ 'sargeras' 、 '[email protected]' ）;
 // hashmaplp.remove（ "ygritte" ）;
 Hashmaplp.Remove（ "Jonathan" ）;
 console.log（hashmaplp.toString（））;

完全なコードについては、hashmaplinearprobing.tsにアクセスしてください

より良いハッシュ関数
コードでは、Hash値を生成するためにLoseloseHashCodeを使用します。そのため、競合が多くのパフォーマンスを消費するため、推奨されません。

上記のコードにDJB2HashCodeメソッドを実装しました。この方法は非常に小さく、次にHashCodeで使用されるメソッドを使用してHasHMAPの実行結果をテストする必要があります。

 HashCode（ key ：k）：number {
 this.djb2hashcode （ key ）;
 }

その結果、予想されたように、重複したハッシュ値を生成せず、すべての要素が保存されました。