ハッシュ関数
このセクションでは、以下で説明するデータ構造内のデータ項目の関連キーのハッシュ コードの実行に役立つハッシュ関数について説明します。
整数ハッシュアイテム ( 整数 鍵 ){
戻る 鍵 % テーブルサイズ ;
}
配列のインデックスを実行するプロセスはハッシュと呼ばれます。場合によっては、同じ種類のコードが実行され、衝突と呼ばれる同じキーを使用して同じインデックスが生成されます。衝突は、異なるチェーン (リンク リストの作成) およびオープン アドレス戦略の実装を通じて処理されます。
C++でのハッシュテーブルの仕組み
実際の値へのポインタはハッシュ テーブルに保持されます。キーを使用して、キーに対する値を配列内の目的の場所に格納する必要がある配列のインデックスを検索します。以下に示すように、サイズ 10 のハッシュ テーブルを取得しました。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
さまざまなキーに対してランダムにデータを取得し、インデックスを計算するだけでこれらのキーをハッシュ テーブルに保存してみましょう。したがって、ハッシュ関数を使用して、計算されたインデックスのキーに対してデータが保存されます。データ = {14,25,42,55,63,84} およびキー =[ 15,9,5,25,66,75 ] を取得するとします。
ハッシュ関数を使用してこれらのデータのインデックスを計算します。インデックス値については次のとおりです。
| 鍵 | 15 | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| インデックスの計算 | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| データ | 14 | 25 | 42 | 55 | 63 | 84 |
配列のインデックスを作成した後、前述したように、指定された配列の正確なインデックス上のキーに対してデータを配置します。
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
その後、2 つ以上のキーが同じハッシュ コードを持ち、配列内の要素のインデックスが同じになる場合に衝突が発生することがわかります。衝突の可能性を回避するための解決策が 1 つあります。それは、適切なハッシュ方式を選択し、正確な戦略を実装することです。
ここで、適切な例を使用しながら、さまざまな実装テクニックについて説明しましょう。
例: オープン ハッシュ手法を使用してハッシュ テーブルにデータを追加する
この例では、オープン ハッシュのような実装手法を使用して、ハッシュ テーブルの衝突を回避します。オープン ハッシュまたはチェーンでは、ハッシュ テーブルの値をチェーンするリンク リストを作成します。この例のコード スニペットは、オープン ハッシュ手法を説明する以下に添付されています。
#include#include <リスト>
クラス ハッシュ表 {
プライベート :
静的 定数 整数 テーブルサイズ = 10 ;
標準 :: リスト < 整数 > テーブルあり [ テーブルサイズ 】 ;
整数 ハッシュファンク ( 整数 鍵 ) {
戻る 鍵 % テーブルサイズ ;
}
公共 :
空所 入れる ( 整数 鍵 ) {
整数 索引 = ハッシュファンク ( 鍵 ) ;
テーブルあり [ 索引 】 。 プッシュバック ( 鍵 ) ;
}
空所 ビューテーブル ( ) {
のために ( 整数 私 = 0 ; 私 < テーブルサイズ ; ++ 私 ) {
標準 :: コート << 「[」 << 私 << 「]」 ;
のために ( 自動 それ = テーブルあり [ 私 】 。 始める ( ) ; それ ！ = テーブルあり [ 私 】 。 終わり ( ) ; ++ それ ) {
標準 :: コート << 「 -> 」 << * それ ;
}
標準 :: コート << 標準 :: 終わり ;
}
}
} ;
整数 主要 ( ) {
ハッシュテーブル hasTable ;
テーブルがあります。 入れる ( 15 ) ;
テーブルがあります。 入れる ( 33 ) ;
テーブルがあります。 入れる ( 23 ) ;
テーブルがあります。 入れる ( 65 ) ;
テーブルがあります。 入れる ( 3 ) ;
テーブルがあります。 ビューテーブル ( ) ;
戻る 0 ;
}
これは非常に興味深い例です。リンク リストを作成し、データをハッシュ テーブルに挿入します。まず、プログラムの開始時にライブラリを定義します。の < リスト > ライブラリはリンクリストの実装に使用されます。その後、「HashTable」という名前のクラスを構築し、「private:」キーワードを使用してテーブル サイズとテーブル配列としてプライベートなクラスの属性を作成します。プライベート属性はクラスの外では使用できないことに注意してください。ここではテーブルのサイズを「10」とします。これを使ってハッシュメソッドを初期化し、ハッシュテーブルのインデックスを計算します。ハッシュ関数では、ハッシュ テーブルのキーとサイズを渡します。
いくつかの必要な関数を構築し、これらの関数をクラス内で公開します。パブリック関数はクラス外のどこでも使用できることに注意してください。 「public:」キーワードを使用して、クラスのパブリック部分を開始します。 。 ハッシュ テーブルに新しい要素を追加したいので、キーを関数の引数として持つ「InsertHash」という名前の関数を作成します。 「insert」関数では、インデックス変数を初期化します。 ハッシュ関数をインデックス変数に渡します。その後、プッシュメソッドを使用してインデックス変数をリンクリスト tableHas[] に渡し、テーブルに要素を挿入します。
その後、新しく挿入されたデータを確認するためにハッシュ テーブルを表示する「viewHashTab」関数を構築します。この関数では、ハッシュ テーブルの終わりまで値を検索する「for」ループを使用します。ハッシュ関数を使用して作成されたのと同じインデックスに値が格納されていることを確認してください。ループでは、それぞれのインデックスに値を渡し、ここでクラスを終了します。 「main」関数では、「hasTable」という名前のクラスのオブジェクトを取得します。このクラス オブジェクトを利用すると、メソッドにキーを渡すことで挿入メソッドにアクセスできます。 「main」関数で渡したキーは、ハッシュ テーブル内のインデックス位置を返す「insert」関数で計算されます。 「Class」オブジェクトを使用して「view」関数を呼び出して、ハッシュ テーブルを表示しました。
このコードの出力を以下に添付します。
ご覧のとおり、ハッシュ テーブルは C++ のリンク リストを使用して正常に作成されています。オープンチェーンは、同じインデックスの衝突を避けるために使用されます。
結論
最終的に、ハッシュ テーブルは、大量のデータを効率的に処理するために値のペアを持つキーを保存および取得するための最も新しい技術であるという結論に達しました。ハッシュ テーブルでは衝突の可能性が非常に高く、データとそのストレージが破壊されます。ハッシュ テーブル管理のさまざまな手法を使用して、この衝突を克服できます。 C++ でハッシュ テーブルを開発することにより、開発者はハッシュ テーブルにデータを格納するための最適な手法を使用してパフォーマンスを向上させることができます。この記事がハッシュテーブルの理解に役立つことを願っています。