JavaScript でのハッシュ化
ハッシュは、データをできるだけ高速に保存および取得するために使用される一般的な手法です。ハッシュを使用する主な理由は、挿入、削除、検索、その他の操作を実行することです。
なぜハッシュを使用するのでしょうか?
ハッシュでは、挿入、検索、削除などのすべての操作を O(1)、つまり一定時間で実行できます。ハッシュの最悪の場合の時間計算量は O(n) のままですが、平均的な場合の時間計算量は O(1) です。
ハッシュ表
新しいハッシュ テーブルを作成するために使用されます。
構文：
// function to delete a key from the hashtable delete (key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } } 構文による基本操作
得る：
ハッシュ テーブル内のキーを検索し、そのキーに関連付けられた値を返すために使用されます。
構文：
// function inside hashtable class to // access a value using its key get(key) { const target = this._setKey(key); return this.table[target]; } 入れる：
新しいキーと値のペアをハッシュ テーブル内に挿入するために使用されます。
構文：
// function to insert a value in the // hash table using setKey function insert(value) { const index = this._setKey(value); this.table[index] = value; this.size++; } 検索：
値を検索するために使用されます。
構文：
// search a value (by getting its // key using setKey function) search(value){ const index = this._setKey(value); if(this.table[index]==value) console.log('The value is found at index : ',index); else console.log('Not found'); } 消去：
ハッシュ テーブルから特定のキーと値のペアを削除するために使用されます。
構文：
// function to delete a key from the hashtable delete (key) { const index = this._setKey(key); if (this.table[index]) { this.table[index] = []; this.size--; return true; } else { return false; } } JavaScript におけるハッシュのコンポーネント
1. ハッシュテーブル: ハッシュ テーブルは配列を一般化したものです。これは、必要に応じて後でそれらの項目を簡単に見つけられるような方法でデータのコレクションを保存する機能を提供します。これにより、要素の検索が非常に効率的になります。
2. ハッシュ関数: ハッシュ関数は、特定のキーを特定のスロット インデックスに変換するために使用されます。これは、考えられるすべてのキーを一意のスロット インデックスにマッピングするために使用されます。すべてのキーが一意のスロット インデックスにマッピングされている場合、そのハッシュ関数は完全ハッシュ関数と呼ばれます。完璧なハッシュ関数を作成することは非常に困難ですが、プログラマーとしての私たちの仕事は、衝突の数ができるだけ少ないハッシュ関数を作成することです。
優れたハッシュ関数には次の特性が必要です。
- 効率的に計算可能。
- キーを均一に分散する必要があります (各テーブルの位置はそれぞれに等しい可能性があります)。
- 衝突を最小限に抑える必要があります。
- 負荷係数 (テーブル内の項目数をテーブルのサイズで割ったもの) が低い必要があります。
3. 衝突処理: ハッシュ関数は大きなキーに対して小さな数値を取得するため、2 つのキーが同じ値になる可能性があります。新しく挿入されたキーがハッシュ テーブル内の既に占有されているスロットにマップされる状況は衝突と呼ばれ、何らかの衝突処理技術を使用して処理する必要があります。衝突を処理する方法は次のとおりです。
- 連鎖: このアイデアは、ハッシュ テーブルの各セルが、同じハッシュ関数値を持つレコードのリンク リストを指すようにすることです。チェーンは簡単ですが、テーブルの外に追加のメモリが必要です。
- オープンアドレッシング: オープン アドレッシングでは、すべての要素がハッシュ テーブル自体に格納されます。各テーブル エントリには、レコードまたは NIL が含まれます。要素を検索するときは、目的の要素が見つかるまで、またはその要素がテーブルにないことが明らかになるまで、テーブル スロットを 1 つずつ調べます。
実装例:
ステップ1： テーブルとサイズの初期プロパティを使用して HashTable クラスを作成します。
ステップ2： キーをインデックスに変換するプライベート setKey(key) 関数を追加します。
ステップ 3: テーブルにキーと値のペアを追加してアクセスするための insert() 関数と get() 関数を追加します。
ステップ 4: ハッシュ テーブルからキーを削除するには、remove() 関数を追加します。
例 1: 5 つの数値 100、87、86、12、25、9 をハッシュテーブルに保存する必要があるとします。この場合、値を引数として受け取り、それをハッシュ テーブルのインデックスに変換する setKey 関数を作成します。以下は実装です。
JavaScript
// HashTable Implementation> class HashTable {> > constructor() {> > this> .table => new> Array(10);> > this> .size = 0;> > }> > // private function to convert key to index> > // _ shows that the function is private> > _setKey(key) {> > return> key % 10;> > }> > // insert value in the hashtable> > insert(value) {> > const index => this> ._setKey(value);> > this> .table[index] = value;> > this> .size++;> > }> > get(key) {> > const target => this> ._setKey(key);> > return> this> .table[target];> > }> > search(value) {> > const index => this> ._setKey(value);> > if> (> this> .table[index] == value)> > console.log(> 'The value is found at index : '> , index);> > else> > console.log(> 'Not found'> );> > }> > delete> (key) {> > const index => this> ._setKey(key);> > if> (> this> .table[index]) {> > this> .table[index] = [];> > this> .size--;> > return> true> ;> > }> else> {> > return> false> ;> > }> > }> }> const hashExample => new> HashTable();> // insert> hashExample.insert(100);> hashExample.insert(87);> hashExample.insert(86);> hashExample.insert(12);> hashExample.insert(9);> console.log(hashExample.table);> // ->ハッシュテーブルを示します>> |
