ハッシュテーブルの説明:それは何であり、それを実装する方法

ハッシュテーブルは、ハッシュマップとも呼ばれ、キーを値にマップするデータ構造です。これはハッシュと呼ばれる手法の一部であり、もう1つはハッシュ関数です。ハッシュ関数は、ハッシュテーブルで値を検索または格納できる場所のインデックスを生成するアルゴリズムです。

ハッシュテーブルに関するいくつかの重要な注意事項:

  1. 値はソートされた順序で保存されません。
  2. あなたは潜在的な衝突の説明をつぶします。これは通常、チェーンと呼ばれる手法で行われます。連鎖とは、値のリンクリストを作成することを意味し、そのキーは特定のインデックスにマップされます。

ハッシュテーブルの実装

ハッシュの背後にある基本的な考え方は、ハッシュテーブル内のプレースホルダーまたは「バケット」の配列全体にキーと値のペアを分散させることです。

ハッシュテーブルは通常、リンクリストの配列です。キーと値のペアを挿入する場合は、最初にハッシュ関数を使用して、キーをハッシュテーブルのインデックスにマップする必要があります。キーが与えられると、ハッシュ関数は値を見つけたり保存したりできるインデックスを提案できます。

index = f(key, array_size)

これは多くの場合、2つのステップで行われます。

hash = hashfunc(key) index = hash % array_size

この方法を使用するhashと、ハッシュテーブルのサイズに依存しません。モジュロ(%)演算子を使用hashして、インデックス(0、配列の開始から、、配列array_size - 1の終了までの数値)に縮小されます。

次の文字列について考えてみますS

string S = “ababcd”

のすべての文字の頻度を数える必要がありますS。これを行う最も簡単な方法は、考えられるすべての文字を繰り返し処理し、それぞれの頻度を1つずつ数えることです。

これは機能しますが、時間がかかります。このようなアプローチの時間計算量はO(26 * N)でNあり、文字列のサイズにSAZからの26の可能な文字を掛けたものです。

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

出力:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

ハッシュを使用するソリューションを見てみましょう。

配列を取得し、ハッシュ関数を使用して、26個の可能な文字を配列のインデックスでハッシュします。次にS、文字列の現在の文字の値を繰り返して、各文字に対応するインデックスを付けて増やします。

このハッシュアプ​​ローチの複雑さはO(N)です。ここで、Nは文字列のサイズです。

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

出力

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

ハッシュ衝突

ハッシュマップは処理しているデータの量よりもかなり小さい可能性があるため、ハッシュの衝突は避けられません。衝突を処理するには、チェーンオープンアドレス法の2つの主要なアプローチがあります。

チェーン

前述のように、チェーンとは、ハッシュテーブル内の各キーと値のペアであり、値が単一のセルではなく、データのリンクリストであることを意味します。

たとえば、キー152が値「JohnSmith」を保持していると想像してください。値「SandraDee」が同じキーに追加されると、「Sandra Dee」は、「JohnSmith」の直後のキー152に別の要素として追加されます。

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

連鎖の主な欠点は、時間の複雑さが増すことです。通常のハッシュテーブルのように0(1)の代わりに、正しい値を見つけるために各リンクリストをトラバースする必要があるため、各ルックアップには時間がかかります。

オープンアドレス法

オープンアドレッシングとは、値がすでに占有されているキーにマップされると、空のキーが見つかるまでハッシュテーブルのキーに沿って移動することを意味します。たとえば、「John Smith」が152にマップされている場合、「SandraDee」は次のオープンインデックスにマップされます。

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

オープンアドレッシングの主な欠点は、値を検索するときに、期待するキーマップに値がない可能性があることです。代わりに、ハッシュテーブルのさまざまな部分をトラバースして、探している値を見つける必要があります。