JavaScriptを使用したハッシュマップ

導入

• ハッシュ マップ (ハッシュ テーブルとも呼ばれる) は、連想配列の抽象データ型を実装するデータ構造であり、キーを値にマップできる構造です。

• ハッシュ関数を使用してバケットまたはスロットの配列へのインデックスを計算し、そこから目的の値を見つけることができます。

• ハッシュ マップの主な利点はその効率性です。新しいキーと値のペアの挿入、キーと値のペアの削除、キーを指定して値を検索するなどの操作はすべて非常に高速で、多くの場合、平均して一定の時間がかかります。

JavaScript での単純なハッシュ マップの実装

let hashMap = {};
hashMap['key1'] = 'value1';
hashMap['key2'] = 'value2';
console.log(hashMap['key1']); // Outputs: value1

衝突の処理

• 衝突の処理は、ハッシュ マップの実装の重要な側面です。 2 つの異なるキーが同じハッシュを生成すると、衝突が発生します。衝突を処理するにはいくつかの戦略がありますが、最も一般的な 2 つの戦略は、個別のチェーンと線形プローブです。

個別のチェーン: 個別のチェーンでは、ハッシュ テーブルの配列の各スロットにリンク リスト (または複数の項目を保持できる別のデータ構造) が含まれます。衝突が発生すると、新しいキーと値のペアが、リンクされたリストの対応するインデックスの末尾に追加されます。

JavaScript で個別のチェーンを使用したハッシュ マップの簡単な実装を次に示します。

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null).map(() => []);
  }

  put(key, value) {
    const index = this.hash(key);
    const chain = this.table[index];
    const existingPair = chain.find(([existingKey]) => existingKey === key);

    if (existingPair) {
      existingPair[1] = value;
    } else {
      chain.push([key, value]);
    }
  }

  get(key) {
    const index = this.hash(key);
    const chain = this.table[index];
    const pair = chain.find(([existingKey]) => existingKey === key);

    if (pair) {
      return pair[1];
    }

    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

線形プローブ: 線形プローブでは、衝突が発生すると、ハッシュ マップは配列内の次のスロットをチェックします (スロットがいっぱいであれば次のスロットに進み、以下同様)。新しいキーと値のペアを保存できる空のスロット。

JavaScript で線形プローブを使用したハッシュ マップの簡単な実装を次に示します。

class HashMap {
  constructor() {
    this.table = new Array(100).fill(null);
  }

  put(key, value) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      index = (index + 1) % this.table.length;
    }
    this.table[index] = [key, value];
  }

  get(key) {
    let index = this.hash(key);
    while (this.table[index] !== null) {
      if (this.table[index][0] === key) {
        return this.table[index][1];
      }
      index = (index + 1) % this.table.length;
    }
    return null;
  }

  hash(key) {
    let hash = 0;
    for (let i = 0; i < key.length; i++) {
      hash += key.charCodeAt(i);
    }
    return hash % this.table.length;
  }
}

どちらの例でも、ハッシュ メソッドは、キーを配列内のインデックスとして使用される整数に変換する単純なハッシュ関数です。実際のシナリオでは、衝突の可能性を減らすために、より複雑なハッシュ関数を使用することになるでしょう。

以上がJavaScriptを使用したハッシュマップの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。