ハッシュテーブルとは何ですか?
ハッシュ テーブルは、キーと値のペアを迅速に挿入、検索、削除するために使用されるデータ構造として定義されます。で動作します。 ハッシュの概念 ここで、各キーはハッシュ関数によって配列内の個別のインデックスに変換されます。インデックスは、一致する値の保存場所として機能します。簡単に言うと、キーと値をマッピングします。
負荷率とは何ですか?
ハッシュ テーブルの負荷係数は、テーブルの大きさに応じてそこに保持される要素の数によって決まります。負荷率が高い場合、テーブルが乱雑になり、検索時間が長くなり、衝突が発生する可能性があります。適切なハッシュ関数を使用し、テーブルのサイズを適切に変更することで、理想的な負荷率を維持できます。
ハッシュ関数とは何ですか?
キーを配列インデックスに変換する関数は、ハッシュ関数として知られています。衝突を減らし、迅速な検索速度を確保するには、適切なハッシュ関数を介してキーを配列全体に均等に分散する必要があります。
- 整数ユニバースの仮定: キーは、整数ユニバースの仮定に従って、特定の範囲内の整数であると想定されます。これにより、除算ハッシュや乗算ハッシュなどの基本的なハッシュ操作を使用できるようになります。
- 除算によるハッシュ: この単純なハッシュ手法では、キーを配列のサイズで割った後の残りの値をインデックスとして使用します。配列のサイズが素数で、キーが等間隔に配置されている場合、パフォーマンスは良好です。
- 乗算によるハッシュ化: この単純なハッシュ操作では、結果の小数部分を取得する前に、キーに 0 から 1 までの定数を乗算します。その後、小数部分に配列のサイズを乗算してインデックスが決定されます。また、キーを均等に分散させた場合にも有効に機能します。
ハッシュ関数の選択 :
適切なハッシュ関数の選択は、キーのプロパティとハッシュ テーブルの意図された機能に基づいて行われます。キーを均等に分散し、衝突を減らす関数を使用することが重要です。
ハッシュ関数が選択される基準は次のとおりです。
- 衝突の数を最小限に抑えるために、優れたハッシュ関数では、均一な方法でハッシュ テーブル全体にキーを分散する必要があります。これは、すべてのキーの組み合わせにおいて、2 つのキーがテーブル内の同じ位置にハッシュされる可能性はかなり一定であることを意味します。
- 高速なハッシュ化とキーの取得を可能にするには、ハッシュ関数の計算効率が高くなければなりません。
- ハッシュ値からキーを推測するのは難しいはずです。その結果、ハッシュ値を使用してキーを推測する試みは成功する可能性が低くなります。
- ハッシュ関数は、ハッシュされるデータの変化に応じて調整できる柔軟性を備えている必要があります。たとえば、ハッシュされるキーのサイズや形式が変更された場合でも、ハッシュ関数は適切に実行し続ける必要があります。
衝突解決テクニック :
2 つ以上のキーが同じ配列インデックスを指している場合、衝突が発生します。チェーン、オープン アドレス指定、およびダブル ハッシュは、衝突を解決するためのいくつかの手法です。
- オープンアドレッシング : 衝突は、テーブル内で次の空きスペースを探すことによって処理されます。最初のスロットがすでに使用されている場合は、1 つが空になるまでハッシュ関数が後続のスロットに適用されます。このアプローチには、二重ハッシュ、線形プローブ、二次プローブなど、さまざまな方法があります。
- 個別のチェーン化 : 個別のチェーンでは、ハッシュ テーブルの各スロットにハッシュされるオブジェクトのリンクされたリストが存在します。 2 つのキーが同じスロットにハッシュされる場合、リンク リストに含まれます。この方法は使用するのがかなり簡単で、いくつかの衝突を管理できます。
- ロビンフッドのハッシュ: チェーンの長さを短縮するために、ロビン フッド ハッシュの衝突はキーをオフにすることで対処されます。新しいキーがすでに占有されているスロットにハッシュされる場合、アルゴリズムはスロットと 2 つのキーの占有スロットの間の距離を比較します。既存のキーが理想的なスロットに近づくと、新しいキーに置き換えられます。これにより、既存のキーが理想的なスロットに近づきます。この方法は、衝突と平均チェーン長を削減する傾向があります。
動的なサイズ変更:
この機能により、テーブルに含まれる要素数の変化に応じてハッシュ テーブルを拡張または縮小できます。これにより、理想的な負荷率が向上し、検索時間が短縮されます。
ハッシュテーブルの実装
Python、Java、C++、Ruby は、ハッシュ テーブルをサポートするプログラミング言語のほんの一部です。これらは、標準ライブラリに含まれることが多いほか、カスタマイズされたデータ構造としても使用できます。
例 – 文字列 geeksforgeeks 内の文字数をカウントします。
この例では、文字列のカウントを保存するためにハッシュ技術を使用します。
C++ #include using namespace std; int main() { //initialize a string string s='geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int arr[26]={0}; //Storing the count for(int i=0;i ジャワ public class CharacterCount { public static void main(String[] args) { // Initialize a string String s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int[] arr = new int[26]; // Storing the count for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a']++; } // Search the count of the character char ch = 'e'; // Get count System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']); } }> パイソン # Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])> C# using System; class Program { static void Main(string[] args) { //initialize a string string s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int[] arr = new int[26]; //Storing the count for (int i = 0; i < s.Length; i++) { arr[s[i] - 'a']++; } //Search the count of the character char ch = 'e'; // get count Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']); } }> JavaScript // Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) { arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>
出力：
The count of e is 4>
ハッシュ テーブルの複雑さの分析:
ルックアップ、挿入、および削除操作の場合、ハッシュ テーブルの平均時間計算量は O(1) です。ただし、これらの操作には、最悪の場合、O(n) 時間がかかる可能性があります (n はテーブル内の要素の数です)。
ハッシュテーブルの用途:
- ハッシュ テーブルは、大量のデータのインデックス作成と検索によく使用されます。検索エンジンは、ハッシュ テーブルを使用して、インデックスを付けた Web ページを保存する場合があります。
- データは通常、ハッシュ テーブルを介してメモリにキャッシュされ、頻繁に使用される情報に迅速にアクセスできるようになります。
- ハッシュ関数は、デジタル署名の作成、データの検証、データの整合性の保証のために暗号化で頻繁に使用されます。
- ハッシュ テーブルを使用してデータベース インデックスを実装すると、キー値に基づいてデータに高速にアクセスできるようになります。