hash table c programs implement hash table
このチュートリアルでは、C ++ハッシュテーブルとハッシュマップについて説明します。また、C ++でのハッシュテーブルアプリケーションと実装についても学習します。
ハッシュは、「ハッシュ関数」を使用して、大量のデータをより小さなテーブルにマップできる手法です。
ハッシュ手法を使用すると、線形検索やバイナリ検索などの他の検索手法と比較して、データをより迅速かつ効率的に検索できます。
このチュートリアルの例を使用して、ハッシュ手法を理解しましょう。
=> Easy C ++トレーニングシリーズをお読みください。
学習内容：
C ++でのハッシュ
何千冊もの本を収容している大学図書館の例を見てみましょう。教科や学科などに応じて本を並べていますが、それでも各セクションにはたくさんの本があり、本を探すのは非常に困難です。
したがって、この困難を克服するために、各本に一意の番号またはキーを割り当てて、本の場所を即座に知ることができます。これは確かにハッシュによって実現されます。
ライブラリの例を続けると、非常に長い文字列になる可能性のある部門、主題、セクションなどに基づいて各本を識別する代わりに、一意の関数を使用してライブラリ内の各本の一意の整数値またはキーを計算します。これらのキーを別のテーブルに保存します。
上記の独自の関数を「ハッシュ関数」と呼び、別のテーブルを「ハッシュテーブル」と呼びます。ハッシュ関数は、指定された値をハッシュテーブル内の特定の一意のキーにマップするために使用されます。これにより、要素へのアクセスが高速になります。ハッシュ関数が効率的であるほど、各要素の一意のキーへのマッピングが効率的になります。
ハッシュ関数を考えてみましょう h（x） 値をマッピングします バツ 」で「 x％10 配列内の」。与えられたデータに対して、次の図に示すように、キーまたはハッシュコードまたはハッシュを含むハッシュテーブルを作成できます。
上の図では、ハッシュ関数を使用して、配列内のエントリがハッシュテーブル内の位置にマップされていることがわかります。
したがって、ハッシュは以下の2つのステップを使用して実装されていると言えます。
＃1） 値は、ハッシュ関数を使用して一意の整数キーまたはハッシュに変換されます。これは、ハッシュテーブルに分類される元の要素を格納するためのインデックスとして使用されます。
上の図では、ハッシュテーブルの値1は、図のLHSで指定されたデータ配列から要素1を格納するための一意のキーです。
＃二） データ配列の要素はハッシュテーブルに格納され、ハッシュキーを使用してすばやく取得できます。上の図では、ハッシュ関数を使用してそれぞれの場所を計算した後、すべての要素をハッシュテーブルに格納していることがわかりました。次の式を使用して、ハッシュ値とインデックスを取得できます。
hash = hash_func(key) index = hash % array_sizeハッシュ関数
マッピングの効率は、使用するハッシュ関数の効率に依存することはすでに説明しました。
ハッシュ関数は基本的に次の要件を満たす必要があります。
- 計算が簡単： ハッシュ関数は、一意のキーを簡単に計算できる必要があります。
- 衝突が少ない： 要素が同じキー値に等しい場合、衝突が発生します。使用するハッシュ関数では、可能な限り衝突を最小限に抑える必要があります。衝突は必ず発生するため、適切な衝突解決手法を使用して衝突を処理する必要があります。
- 一様分布： ハッシュ関数は、ハッシュテーブル全体にデータを均一に分散させ、それによってクラスタリングを防止する必要があります。
ハッシュテーブルC ++
ハッシュテーブルまたはハッシュマップは、元のデータ配列の要素へのポインタを格納するデータ構造です。
ライブラリの例では、ライブラリのハッシュテーブルに、ライブラリ内の各本へのポインタが含まれます。
ハッシュテーブルにエントリがあると、配列内の特定の要素を簡単に検索できます。
すでに見たように、ハッシュテーブルはハッシュ関数を使用して、目的の値を見つけることができるバケットまたはスロットの配列へのインデックスを計算します。
次のデータ配列を使用した別の例を検討してください。
以下に示すように、サイズ10のハッシュテーブルがあると仮定します。
次に、以下のハッシュ関数を使用してみましょう。
Hash_code = Key_value % size_of_hash_tableこれはHash_code =と同等になります Key_value％10
上記の関数を使用して、以下に示すように、キー値をハッシュテーブルの場所にマップします。
| データ項目 | ハッシュ関数 | ハッシュコード |
|---|---|---|
| 22 | 22％10 = 2 | 二 |
| 25 | 25％10 = 5 | 5 |
| 27 | 27％10 = 7 | 7 |
| 46 | 46％10 = 6 | 6 |
| 70 | 70％10 = 0 | 0 |
| 89 | 89％10 = 9 | 9 |
| 31 | 31％10 = 1 | 1 |
上記のテーブルを使用して、ハッシュテーブルを次のように表すことができます。
したがって、ハッシュテーブルから要素にアクセスする必要がある場合、検索を実行するのにO（1）時間かかります。
衝突
通常、ハッシュ関数を使用してハッシュコードを計算し、キー値をハッシュテーブルのハッシュコードにマッピングできるようにします。上記のデータ配列の例では、値12を挿入します。その場合、キー値12のhash_codeは2になります（12％10 = 2）。
最高のPCクリーナーは何ですか
しかし、ハッシュテーブルには、以下に示すように、hash_code2のキー値22へのマッピングがすでにあります。
上に示したように、12と22の2つの値、つまり2に対して同じハッシュコードがあります。1つ以上のキー値が同じ場所に等しい場合、衝突が発生します。したがって、ハッシュコードの場所はすでに1つのキー値で占められており、同じ場所に配置する必要のある別のキー値があります。
ハッシュの場合、非常に大きなサイズのハッシュテーブルがある場合でも、衝突は必ず発生します。これは、一般に大きなキーに対して小さな一意の値が見つかるためです。したがって、1つ以上の値がいつでも同じハッシュコードを持つ可能性があります。
ハッシュでは衝突が避けられないことを考えると、衝突を防止または解決する方法を常に探す必要があります。ハッシュ中に発生する衝突を解決するために使用できるさまざまな衝突解決手法があります。
衝突解決技術
以下は、ハッシュテーブルの衝突を解決するために使用できる手法です。
セパレートチェーン（オープンハッシュ）
これは、最も一般的な衝突解決手法です。これはオープンハッシュとも呼ばれ、リンクリストを使用して実装されます。
youtubeからmp3へのコンバーターウイルスなし
個別の連鎖手法では、ハッシュテーブルの各エントリはリンクリストです。キーがハッシュコードと一致すると、その特定のハッシュコードに対応するリストに入力されます。したがって、2つのキーのハッシュコードが同じである場合、両方のエントリがリンクリストに入力されます。
上記の例では、個別のチェーンを以下に示します。
上の図はチェーンを表しています。ここでは、mod（％）関数を使用します。 2つのキー値が同じハッシュコードに等しい場合、リンクリストを使用してこれらの要素をそのハッシュコードにリンクすることがわかります。
キーがハッシュテーブル全体に均一に分散されている場合、特定のキーを検索する平均コストは、そのリンクリスト内のキーの平均数によって異なります。したがって、スロットよりもエントリの数が増えた場合でも、個別のチェーンは引き続き有効です。
個別のチェーンの最悪のケースは、すべてのキーが同じハッシュコードに等しく、したがって1つのリンクリストにのみ挿入される場合です。したがって、ハッシュテーブル内のすべてのエントリと、テーブル内のキーの数に比例するコストを検索する必要があります。
線形プロービング（オープンアドレッシング/クローズドハッシング）
オープンアドレッシングまたは線形プロービング技術では、すべてのエントリレコードがハッシュテーブル自体に格納されます。 Key-Valueがハッシュコードにマップされ、ハッシュコードが指す位置が占有されていない場合、Key-Valueはその場所に挿入されます。
位置がすでに占有されている場合は、プロービングシーケンスを使用して、ハッシュテーブルで占有されていない次の位置にキー値が挿入されます。
線形プロービングの場合、ハッシュ関数は次のように変更される可能性があります。
ハッシュ=ハッシュ％hashTableSize
ハッシュ=（ハッシュ+ 1）％hashTableSize
ハッシュ=（ハッシュ+ 2）％hashTableSize
ハッシュ=（ハッシュ+ 3）％hashTableSize
線形プローブの場合、スロットまたは連続するプローブ間の間隔は一定、つまり1であることがわかります。
上の図では、0でそれがわかりますthハッシュ関数「hash = hash％hash_tableSize」を使用して10を入力する場所。
ここで、要素70はハッシュテーブルの位置0にも等しくなります。しかし、その場所はすでに占領されています。したがって、線形プロービングを使用して、次の場所である1を見つけます。この場所は占有されていないため、矢印を使用して示すように、この場所にキー70を配置します。
結果のハッシュテーブルを以下に示します。
線形プロービングは、連続セルが占有され、新しい要素を挿入する可能性が低くなる可能性がある「プライマリクラスタリング」の問題に悩まされる可能性があります。
また、2つの要素が最初のハッシュ関数で同じ値を取得する場合、これらの要素は両方とも同じプローブシーケンスに従います。
二次プロービング
二次プロービングは線形プロービングと同じですが、唯一の違いはプロービングに使用される間隔です。名前が示すように、この手法では、線形距離ではなく、非線形距離または2次距離を使用して、衝突が発生したときにスロットを占有します。
二次プロービングでは、スロット間の間隔は、すでにハッシュされたインデックスに任意の多項式値を追加することによって計算されます。この手法は、プライマリクラスタリングを大幅に削減しますが、セカンダリクラスタリングでは改善されません。
ダブルハッシュ
ダブルハッシュ手法は、線形プロービングに似ています。ダブルハッシュと線形プロービングの唯一の違いは、ダブルハッシュ手法では、プロービングに使用される間隔が2つのハッシュ関数を使用して計算されることです。ハッシュ関数をキーに次々に適用するため、プライマリクラスタリングとセカンダリクラスタリングが排除されます。
チェーン（オープンハッシュ）と線形プロービング（オープンアドレス法）の違い
| チェーン（オープンハッシュ） | 線形プロービング（オープンアドレス法） |
|---|---|
| キー値は、別のリンクリストを使用してテーブルの外に保存できます。 | キー値はテーブル内にのみ保存する必要があります。 |
| ハッシュテーブルの要素数がハッシュテーブルのサイズを超える場合があります。 | ハッシュテーブルに存在する要素の数は、ハッシュテーブルのインデックスの数を超えることはありません。 |
| 削除は連鎖技術において効率的です。 | 削除は面倒な場合があります。必要がなければ回避できます。 |
| 場所ごとに個別のリンクリストが維持されるため、使用されるスペースが大きくなります。 | すべてのエントリが同じテーブルに収容されるため、使用されるスペースが少なくなります。 |
C ++ハッシュテーブルの実装
配列またはリンクリストを使用してハッシュテーブルをプログラムすることにより、ハッシュを実装できます。 C ++には、ハッシュテーブルに似た構造である「ハッシュマップ」と呼ばれる機能もありますが、各エントリはキーと値のペアです。 C ++では、ハッシュマップまたは単にマップと呼ばれます。 C ++のハッシュマップは通常、順序付けられていません。
マップの機能を実装するC ++の標準テンプレートライブラリ（STL）で定義されたヘッダーがあります。カバーしました STLマップ 詳細については、STLに関するチュートリアルをご覧ください。
次の実装は、リンクリストをハッシュテーブルのデータ構造として使用してハッシュするためのものです。また、この実装では、衝突解決手法として「チェーン」を使用します。
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< 出力：
作成されたハッシュテーブル：
0-> 21-> 14
1-> 15
二
3
4-> 11
5-> 12
6
キー12の削除後のハッシュテーブル：
0-> 21-> 14
1-> 15
二
3
4-> 11
5
6
出力には、サイズ7で作成されたハッシュテーブルが表示されます。衝突を解決するためにチェーンを使用します。キーの1つを削除した後、ハッシュテーブルを表示します。
ハッシュのアプリケーション
＃1）パスワードの検証： パスワードの検証は通常、暗号化ハッシュ関数を使用して行われます。パスワードが入力されると、システムはパスワードのハッシュを計算し、検証のためにサーバーに送信されます。サーバーには、元のパスワードのハッシュ値が保存されます。
＃2）データ構造： C ++のunordered_setとunordered_map、PythonまたはC＃の辞書、JavaのHashSetとハッシュマップなどのさまざまなデータ構造はすべて、キーが一意の値であるキーと値のペアを使用します。値は、異なるキーで同じにすることができます。ハッシュは、これらのデータ構造を実装するために使用されます。
＃3）メッセージダイジェスト： これは、暗号化ハッシュを使用するさらに別のアプリケーションです。メッセージダイジェストでは、送受信されるデータやファイルのハッシュを計算し、保存されている値と比較して、データファイルが改ざんされていないことを確認します。ここで最も一般的なアルゴリズムは「SHA256」です。
＃4）コンパイラの操作： コンパイラーがプログラムをコンパイルするとき、プログラミング言語のキーワードは他のIDとは異なる方法で保管されます。コンパイラは、これらのキーワードを格納するためにハッシュテーブルを使用します。
＃5）データベースのインデックス作成： ハッシュテーブルは、データベースのインデックス作成とディスクベースのデータ構造に使用されます。
＃6）連想配列： 連想配列は、インデックスが整数のような文字列または他のオブジェクトタイプ以外のデータ型である配列です。ハッシュテーブルは、連想配列の実装に使用できます。
結論
ハッシュは、挿入、削除、および検索操作に一定の時間O（1）を要するため、最も広く使用されているデータ構造です。ハッシュは主に、大きなデータエントリに対して一意の小さなキー値を計算するハッシュ関数を使用して実装されます。配列とリンクリストを使用してハッシュを実装できます。
1つ以上のデータエントリが同じキーの値と等しい場合は常に、衝突が発生します。線形プロービング、チェーンなど、さまざまな衝突解決手法を見てきました。また、C ++でのハッシュの実装も見てきました。
結論として、ハッシュはプログラミングの世界で群を抜いて最も効率的なデータ構造であると言えます。
=> ここでC ++トレーニングシリーズ全体を探してください。
推奨読書