データ構造におけるハッシュの概要:
ハッシュは、大規模なデータ セットを固定長の値にマッピングするコンピューター サイエンスの一般的な手法です。可変サイズのデータセットを固定サイズのデータセットに変換するプロセスです。効率的な検索操作を実行できるため、ハッシュはデータ構造において不可欠な概念となります。
ハッシュ化とは何ですか?
ハッシュ アルゴリズムは、入力 (文字列や整数など) を固定サイズの出力 (ハッシュ コードまたはハッシュ値と呼ばれる) に変換するために使用されます。次に、このハッシュ値を配列またはハッシュ テーブルのインデックスとして使用して、データの保存と取得が行われます。ハッシュ関数は決定論的である必要があり、指定された入力に対して常に同じ結果が得られることが保証されます。
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 にリンクされたリストを作成し、キーと値のペアをリストに追加します。ハッシュ テーブルは次のようになります。
0:
1:
2:
3:
4: ジョン: 123456 -> メアリー: 987654
5:
ハッシュ表：
ハッシュ テーブルは、データを配列に格納するデータ構造です。通常、配列のサイズは、ハッシュ テーブルに収まる要素の数よりも大きく選択されます。キーは、ハッシュ関数を使用して配列内のインデックスにマップされます。
ハッシュ関数は、新しい要素を追加するためにハッシュ テーブル内で要素を挿入する必要があるインデックスを見つけるために使用されます。衝突がない場合、要素はそのインデックスに追加されます。衝突がある場合は、衝突解決メソッドを使用して、配列内の次に使用可能なスロットが検索されます。
ハッシュ関数は、要素が格納されているインデックスを見つけて、ハッシュ テーブルから要素を取得するために使用されます。要素がそのインデックスで見つからない場合、衝突解決メソッドを使用して、リンクされたリスト (チェーンが使用されている場合) または次に利用可能なスロット (オープン アドレッシングが使用されている場合) で要素が検索されます。
ハッシュテーブルの操作
ハッシュ テーブルに対して実行できる操作は次のとおりです。
- 挿入: 新しいキーと値のペアをハッシュ テーブルに挿入します。
- 削除: ハッシュ テーブルからキーと値のペアを削除します。
- 検索: ハッシュ テーブル内のキーと値のペアを検索します。
ハッシュテーブルの作成:
ハッシュは、迅速なデータの挿入、削除、取得を可能にするデータ構造であるハッシュ テーブルを構築するためによく使用されます。ハッシュ テーブルを構成する各バケット配列には、1 つ以上のキーと値のペアを格納できます。
ハッシュ テーブルを作成するには、まず各キーを配列内の固有のインデックスにマップするハッシュ関数を定義する必要があります。単純なハッシュ関数では、キー内の文字の ASCII 値の合計を取得し、配列のサイズで割ったときの剰余を使用することができます。ただし、このハッシュ関数は非効率的であり、衝突 (同じインデックスにマップされる 2 つのキー) が発生する可能性があります。
衝突を避けるために、配列全体でより均等なハッシュ値の分布を生成する、より高度なハッシュ関数を使用できます。一般的なアルゴリズムの 1 つは djb2 ハッシュ関数です。これは、ビット単位の演算を使用してハッシュ値を生成します。
unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 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['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << 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->key = key; new_node->value = value; new_node->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->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 説明：
- まず、ハッシュ テーブル内の単一のノードを表す、node と呼ばれる構造体が定義されます。
- 各ノードには 3 つのメンバーがあります。キーを格納する char* キー、関連する値を格納する int 値、およびリンク リストを使用してハッシュ テーブル内の衝突を処理するために next と呼ばれる別のノードへのポインタです。
- hash_table と呼ばれるノード ポインターの配列は、サイズ 100 で宣言されます。この配列は、ハッシュ テーブルの要素を格納するために使用されます。
- insert 関数は、char* キーと int 値をパラメータとして受け取ります。
- まず、ハッシュ関数を使用して、指定されたキーのハッシュ値を計算します。ハッシュ関数は、プログラム内の他の場所で定義されていると想定されます。
- 次に、ハッシュ値は、モジュラス演算子 % 100 を使用して hash_table 配列のサイズ内に収まるように縮小されます。
- 新しいノードは動的メモリ割り当て (malloc(sizeof(node))) を使用して作成され、そのメンバー (キー、値、および next) には、それぞれ指定されたキー、値、および NULL が割り当てられます。
- hash_table 配列内の対応するスロットが空 (NULL) で、衝突が発生していないことを示す場合、新しいノードはそのスロットに直接割り当てられます (hash_table[hash_value] = new_node)。
ただし、hash_table 配列のそのインデックスにノードがすでに存在する場合、関数は衝突を処理する必要があります。現在のノード (hash_table[hash_value]) から開始してリンク リストを走査し、最後に到達するまで (curr_node->next != NULL)、次のノードに移動します。リストの最後に到達すると、新しいノードが次のノードとして追加されます (curr_node->next = new_node)。
C++ でのハッシュの実装:
衝突解決のためにオープン アドレッシングと線形プローブを使用した C++ でのハッシュの実装を見てみましょう。整数を格納するハッシュ テーブルを実装します。
#include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>