データ構造におけるハッシュ化

データ構造におけるハッシュの概要:

ハッシュは、大規模なデータセットを固定長の値にマッピングするコンピューターサイエンスの一般的な手法です。可変サイズのデータセットを固定サイズのデータセットに変換するプロセスです。効率的な検索操作を実行できるため、ハッシュはデータ構造において不可欠な概念となります。

ハッシュ化とは何ですか?

ハッシュアルゴリズムは、入力 (文字列や整数など) を固定サイズの出力 (ハッシュコードまたはハッシュ値と呼ばれる) に変換するために使用されます。次に、このハッシュ値を配列またはハッシュテーブルのインデックスとして使用して、データの保存と取得が行われます。ハッシュ関数は決定論的である必要があり、指定された入力に対して常に同じ結果が得られることが保証されます。

Javaの参照変数

ハッシュは一般に、データの一部分の一意の識別子を作成するために使用され、これを使用して大規模なデータセット内でそのデータを迅速に検索できます。たとえば、Web ブラウザはハッシュを使用して Web サイトのパスワードを安全に保存する場合があります。ユーザーがパスワードを入力すると、ブラウザはパスワードをハッシュ値に変換し、保存されているハッシュ値と比較してユーザーを認証します。

ハッシュキーとは何ですか?

ハッシュのコンテキストでは、ハッシュキー (ハッシュ値またはハッシュコードとも呼ばれる) は、ハッシュアルゴリズムによって生成される固定サイズの数値または英数字表現です。これは、ハッシュとして知られるプロセスを通じて、テキスト文字列やファイルなどの入力データから派生します。

ハッシュには、特定の数学関数を入力データに適用することが含まれます。これにより、入力のサイズに関係なく、通常は固定長の一意のハッシュキーが生成されます。結果として得られるハッシュキーは、本質的には元のデータのデジタルフィンガープリントです。

ハッシュキーはいくつかの目的に役立ちます。入力データの小さな変更でも大幅に異なるハッシュキーが生成されるため、データの整合性チェックによく使用されます。ハッシュキーは、迅速な検索と比較操作を可能にするため、効率的なデータの取得とハッシュテーブルまたはデータ構造への保存にも使用されます。

ハッシュ化はどのように機能するのか?

ハッシュのプロセスは 3 つのステップに分かれています。

入力: ハッシュされるデータがハッシュアルゴリズムに入力されます。
ハッシュ関数: ハッシュアルゴリズムは入力データを受け取り、数学関数を適用して固定サイズのハッシュ値を生成します。ハッシュ関数は、異なる入力値が異なるハッシュ値を生成し、入力の小さな変化が出力の大きな変化を生み出すように設計する必要があります。
出力: ハッシュ値が返され、データ構造にデータを格納または取得するためのインデックスとして使用されます。

ハッシュアルゴリズム:

ハッシュアルゴリズムは多数あり、それぞれに明確な長所と短所があります。最も一般的なアルゴリズムには次のものがあります。

MD5: 128 ビットのハッシュ値を生成する、広く使用されているハッシュアルゴリズム。
SHA-1: 160 ビットのハッシュ値を生成する一般的なハッシュアルゴリズム。
SHA-256: 256 ビットのハッシュ値を生成する、より安全なハッシュアルゴリズム。

ハッシュ関数:

ハッシュ関数: ハッシュ関数は、入力 (またはキー) を受け取り、ハッシュコードまたはハッシュ値として知られる固定サイズの結果を出力する数学演算の一種です。ハッシュ関数は、決定性を持たせるために、同じ入力に対して常に同じハッシュコードを生成する必要があります。さらに、ハッシュ関数は、ハッシュプロパティと呼ばれる、入力ごとに一意のハッシュコードを生成する必要があります。

ハッシュ関数には次のようなさまざまな種類があります。

分割方法：

この方法では、キーをテーブルサイズで除算し、その余りをハッシュ値として取得します。たとえば、テーブルサイズが 10、キーが 23 の場合、ハッシュ値は 3 (23 % 10 = 3) になります。

乗算方法:

この方法では、キーに定数を乗算し、その積の小数部分をハッシュ値として取得します。たとえば、キーが 23 で定数が 0.618 の場合、ハッシュ値は 2 (floor(10*(0.61823 - Floor(0.61823))) = Floor(2.236) = 2) になります。

ユニバーサルハッシュ:

この方法では、ハッシュ関数ファミリーからのランダムハッシュ関数を使用します。これにより、ハッシュ関数が特定の入力に偏らず、攻撃に対して耐性を持つことが保証されます。

衝突の解決

ハッシュにおける主な課題の 1 つは、2 つ以上の入力値が同じハッシュ値を生成するときに発生する衝突の処理です。衝突を解決するには、次のようなさまざまな手法が使用されます。

連鎖: この手法では、各ハッシュテーブルスロットに、同じハッシュ値を持つすべての値のリンクリストが含まれます。この手法はシンプルで実装が簡単ですが、リンクされたリストが長すぎるとパフォーマンスの低下につながる可能性があります。
オープンアドレッシング: この手法では、衝突が発生すると、アルゴリズムは空のスロットが見つかるまで連続したスロットをプローブすることによって、ハッシュテーブル内の空のスロットを検索します。この手法は、負荷率が低い場合にはチェーンよりも効率的ですが、負荷率が高い場合にはクラスタリングが発生し、パフォーマンスが低下する可能性があります。
ダブルハッシュ: これはオープンアドレッシングの一種で、衝突が発生したときに 2 番目のハッシュ関数を使用してプローブする次のスロットを決定します。この手法は、クラスタリングを削減し、パフォーマンスを向上させるのに役立ちます。

衝突解決の例

サイズ 5 のハッシュテーブルの例を続けましょう。キーと値のペア「John: 123456」と「Mary: 987654」をハッシュテーブルに保存したいと考えています。両方のキーは同じハッシュコード 4 を生成するため、衝突が発生します。

チェーンを使用して衝突を解決できます。インデックス 4 にリンクされたリストを作成し、キーと値のペアをリストに追加します。ハッシュテーブルは次のようになります。

4: ジョン: 123456 -> メアリー: 987654

ハッシュ表：

ハッシュテーブルは、データを配列に格納するデータ構造です。通常、配列のサイズは、ハッシュテーブルに収まる要素の数よりも大きく選択されます。キーは、ハッシュ関数を使用して配列内のインデックスにマップされます。

ハッシュ関数は、新しい要素を追加するためにハッシュテーブル内で要素を挿入する必要があるインデックスを見つけるために使用されます。衝突がない場合、要素はそのインデックスに追加されます。衝突がある場合は、衝突解決メソッドを使用して、配列内の次に使用可能なスロットが検索されます。

ハッシュ関数は、要素が格納されているインデックスを見つけて、ハッシュテーブルから要素を取得するために使用されます。要素がそのインデックスで見つからない場合、衝突解決メソッドを使用して、リンクされたリスト (チェーンが使用されている場合) または次に利用可能なスロット (オープンアドレッシングが使用されている場合) で要素が検索されます。

ハッシュテーブルの操作

ハッシュテーブルに対して実行できる操作は次のとおりです。

挿入: 新しいキーと値のペアをハッシュテーブルに挿入します。
削除: ハッシュテーブルからキーと値のペアを削除します。
検索: ハッシュテーブル内のキーと値のペアを検索します。

ハッシュテーブルの作成:

ハッシュは、迅速なデータの挿入、削除、取得を可能にするデータ構造であるハッシュテーブルを構築するためによく使用されます。ハッシュテーブルを構成する各バケット配列には、1 つ以上のキーと値のペアを格納できます。

ハッシュテーブルを作成するには、まず各キーを配列内の固有のインデックスにマップするハッシュ関数を定義する必要があります。単純なハッシュ関数では、キー内の文字の ASCII 値の合計を取得し、配列のサイズで割ったときの剰余を使用することができます。ただし、このハッシュ関数は非効率的であり、衝突 (同じインデックスにマップされる 2 つのキー) が発生する可能性があります。

衝突を避けるために、配列全体でより均等なハッシュ値の分布を生成する、より高度なハッシュ関数を使用できます。一般的なアルゴリズムの 1 つは djb2 ハッシュ関数です。これは、ビット単位の演算を使用してハッシュ値を生成します。

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash &lt;&lt; 5) + hash) + c; } return hash; }

このハッシュ関数は文字列を入力として受け取り、符号なし長整数のハッシュ値を返します。この関数は、ハッシュ値 5381 を初期化し、ビット単位の演算を使用して文字列内の各文字を反復処理して、新しいハッシュ値を生成します。最終的なハッシュ値が返されます。

C++ のハッシュテーブル

C++ では、標準ライブラリは unowned_map と呼ばれるハッシュテーブルコンテナクラスを提供します。 unowned_map コンテナーはハッシュテーブルを使用して実装され、キーと値のペアへの高速アクセスを提供します。 unowned_map コンテナーは、ハッシュ関数を使用してキーのハッシュコードを計算し、オープンアドレス指定を使用して衝突を解決します。

C++ で unowned_map コンテナーを使用するには、ヘッダーファイルをインクルードする必要があります。 C++ で unowned_map コンテナーを作成する方法の例を次に示します。

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map[&apos;apple&apos;] = 10; my_map[&apos;banana&apos;] = 20; my_map[&apos;orange&apos;] = 30; // print the value associated with the &apos;banana&apos; key std::cout &lt;&lt; my_map[&apos;banana&apos;] &lt;&lt; std::endl; return 0; }

説明：

このプログラムは、ハッシュテーブルを使用して実装され、キーと値のペアへの高速アクセスを提供する、C++ での unowned_map コンテナーの使用法を示します。
まず、プログラムには必要なヘッダーファイルが含まれています。
次に、プログラムは、文字列キーと整数値を持つ my_map という空の unowned_map コンテナーを作成します。これは、構文 std::unowned_map my_map; を使用して行われます。
次に、プログラムは [] 演算子を使用して 3 つのキーと値のペアを my_map コンテナーに挿入します。値が 10 の「apple」、値が 20 の「banana」、値が 30 の「orange」です。
これは、構文 my_map['apple'] = 10;、my_map['banana'] = 20;、および my_map['orange'] = 30; を使用して行われます。それぞれ。
最後に、プログラムは [] 演算子と std::cout オブジェクトを使用して、「banana」キーに関連付けられた値を出力します。

プログラム出力:

ハッシュテーブルへのデータの挿入

キーと値のペアをハッシュテーブルに挿入するには、まずキーと値のペアを格納する配列のインデックスとして使用する必要があります。別のキーが同じインデックスにマップされている場合、衝突が発生するため、適切に処理する必要があります。一般的な方法の 1 つはチェーンを使用することです。チェーンの使用では、配列内の各バケットに、同じハッシュ値を持つキーと値のペアのリンクされたリストが含まれます。

以下は、チェーンを使用してキーと値のペアをハッシュテーブルに挿入する方法の例です。

Java intから文字列へ

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node-&gt;key = key; new_node-&gt;value = value; new_node-&gt;next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node-&gt;next != NULL) { curr_node = curr_node-&gt;next; } curr_node-&gt;next = new_node; } }