C++hash(STL hash)とその関数テンプレートの使い方の詳細

コンテナにオブジェクトとその関連するキーを保存し、キー/オブジェクトペアの順序をキーで決定しない場合は、キー値に対してメモリ内の要素の位置を決定する他の方法を使用する必要があります.stringのようなオブジェクトをキーとして使用すると、いくつかの問題が発生し、可能な変数の数は巨大です.10文字のアルファベット文字列の可能な個数は2610です.このインデックスの範囲はあまり役に立たない.それを許容可能な範囲に変えるメカニズムが必要です.また、理想的には、このメカニズムは、キーごとに一意の値を生成することができる.これもハッシュがしなければならないことの一つです.ハッシュは、所与の範囲の基本タイプのデータ項目、またはstringのようなオブジェクトを用いて整数値を生成するプロセスである.ハッシュによって生成される値は、ハッシュ値またはハッシュコードと呼ばれ、通常、テーブル内のオブジェクトの位置を決定するためにコンテナで使用される.前述したように、理想的には、各オブジェクトは一意のハッシュ値を生成すべきであるが、これは一般的に不可能である.異なるキー値の個数が可能なハッシュ値の個数より大きい場合、上述したような状況が明らかになり、私たちは遅かれ早かれ重複するハッシュ値を得ることができる.重複するハッシュ値は衝突とも呼ばれます.ハッシュは、コンテナにオブジェクトを保存するだけでなく、パスワードや暗号化データなどの多くの他の場所にも適用され、パスワード識別にはハッシュが含まれる場合がある.システムに明文パスワードを保存するのはリスクが大きい.パスワードを保存するハッシュ値は、明文パスワードを保存するよりも安全で、ハッカーを防ぐことができます.ハッシュ値を取得したハッカーは、ハッシュ値を彼らに役立つ元のパスワードに変換する必要があります.これは不可能なタスクです.従って、STLが提供する異なるタイプのデータハッシュに対する能力は、関連するコンテナだけでなく、より広いシーンでも使用することができる.容器のハッシュメカニズムを理解する必要はありませんが、何ができるかを基本的に理解することができます.ハッシュアルゴリズムはたくさんありますが、通用するものはありません.あるシーンに適切なハッシュアルゴリズムを決定することは、必ずしも簡単ではない.通常、データを分割して計算する必要があります.これは最も簡単なキーを処理するアルゴリズムかもしれませんが、どんなタイプのキーでも数値として処理されます.したがって、ハッシュ値は、式k%mによって生成される可能性がある.明らかに,この方法は最大m個の異なるハッシュ値を許容し,値の範囲は0〜m−1である.重複するハッシュ値がどこで生成されるかを簡単に見ることができます.値がk+m、k+2*mのキーには重複ハッシュ値があり、m値の選択は重複ハッシュ値の出現を減らすために重要であり、値が均一に分布することを保証することができる.mが2のべき乗、すなわち2 nである場合、ハッシュ値の最小ビットはkのnビットである.これは明らかに良い結果ではない.kのほとんどのビットはハッシュ値に影響しないからである.理想的には、キーのすべてのビットがハッシュ結果に影響を及ぼすはずです.mは通常、ハッシュ値をこの範囲内により均一に分布させることができるため、質量数である.もう1つのより良いハッシュ値を計算する方法は、定数aを選択し、それをkに乗算し、a*kを整数mで割ってその残数を計算し、(a*k)%mの結果からハッシュ値として長さ値を選択することである.明らかにaとmの選択は非常に重要である.32ビットのコンピュータの場合、mは通常232に選択される.乗数aはmに近い素数であり,これはaとmが1を除いて他の共通因子がないことを意味する.また、aのバイナリ表現では、ヘッダとテールは0にできません.そうしないと、他のヘッダが0またはテールが0のキー値と衝突します.これらの理由に基づいて、このアルゴリズムは乗算ハッシュとも呼ばれる.いくつかの専門ハッシュ文字列のアルゴリズムもあります.文字列を一定数の単語と見なし、乗算アルゴリズムのような方法で最初の単語のハッシュ値を計算し、次の単語を加えてハッシュ値を計算し、すべての単語の最後のハッシュ値が計算されるまでこのプロセスを繰り返します.
ハッシュ値を生成する関数
functionalヘッダファイルには、無秩序関連コンテナで使用される特例化hashテンプレートが定義されています.hashテンプレートは、Kタイプのオブジェクトからハッシュ値を生成できる関数オブジェクトのタイプを定義します.hashインスタンスのメンバー関数operator()()は、Kタイプの単一パラメータを受け入れ、size_を返します.tタイプのハッシュ値.基本タイプとポインタタイプについても、特例化されたhashテンプレートが定義されています.hashテンプレート専用のアルゴリズムは実装に依存するが,C++14規格に従う場合,いくつかの具体的な要件を満たす必要がある.これらの要件は次のとおりです.

異常を放出できない

等しいキーに対して等しいハッシュ値

を生成しなければならない

等しくないキーに対して衝突する可能性はsize_に最小に近づかなければならない.t最大値の逆数

なお、等しいキーが等しいハッシュ値を生成するのは、単一の実行にのみ適している.すなわち、所与のキーが異なる場合に異なるハッシュ値を生成することを可能にすることを意味する.これにより、ハッシュアルゴリズムで乱数を使用することができ、パスワードをハッシュする場合、これは私たちが望んでいる使用です.なお、C++14は、一貫性を保つために、所与のタイプのキーのハッシュ値がキーに等しい可能性を排除しない.無秩序関連コンテナでは,ハッシュ関数を用いたハッシュ整数値がこの場合である可能性がある.次に、hashで整数のハッシュ値を生成する例を示します.

std::hash hash_int;// Function object to hash int
std::vector {-5, -2, 2, 5, 10};
std::transform(std::begin(n), std::end(n),std::ostream_iterator (std:: cout," "),hash_int);

ここではtransform()アルゴリズムを用いてvector内の要素をハッシュする.transform()パラメータの最初の2つの反復器は、操作される要素の範囲を指定し、3番目のパラメータは出力アドレスを指定する反復器であり、ここではostream反復器であり、最後のパラメータは範囲要素に適用される関数オブジェクトhashである.テストの出力は次のとおりです.
554121069 2388331168 3958272823 3132668352 1833987007
あなたのC++コンパイラとライブラリでは、すべてのハッシュ値がこのように異なるハッシュ値を生成する可能性があります.ハッシュ浮動小数点数の例を次に示します.

std::hash hash_double;
std::vector x {3.14,-2.71828, 99.0, 1.61803399,6.62606957E-34};
std::transform(std::begin(x), std::end(x),std::ostream_iterator(std::cout," "),hash_double);

テストの出力は次のとおりです.
4023697370 332724328 2014146765 3488612130 3968187275
ポインタもハッシュしやすいです.

std::hash hash_box; // Box class as in Chapter 2
Box box{1, 2, 3};
std:: cout << "Hash value = " << hash_box (&box)<<:endl hash="" value="2916986638</code"/>

同じ関数オブジェクトを使用して、スマートポインタをハッシュできます.

std::hash hash_box; // Box class as in Chapter 2
auto upbox = std::make_unique(1A 2, 3);
std::cout << "Hash value = " << hash_box(upbox.get())<<:endl hash="" value="1143026886</code"/>

ここでunique_を呼び出しますptrオブジェクトのメンバー関数get()は、自由記憶領域アドレスを保存するオリジナルポインタを取得し、ハッシュ関数に渡す.ここで使用するhashテンプレートもunique_ptrとshared_ptrオブジェクトの特例化テンプレート.たとえばunique_ptrオブジェクトは、含まれるオリジナルポインタではなくハッシュされます.

std::hash<:unique_ptr>>hash_box; // Box class as in Chapter 2
auto upbox = std::make_unique(1, 2, 3);
std::cout << "Hash value = "<< hash_box (upbox)<< std::endl; // Hash value = 4291053140

オリジナルポインタとunique_ptrのハッシュ値は同じです.この誤解に導かれないでください.このポインタハッシュに対する能力は、1つのタイプのキーに特定のハッシュ関数がない場合に有用であることを考慮します.オブジェクト自体ではなく、アドレスをハッシュできます.これは、ポインタが指すオブジェクトとは無関係です.無秩序な容器にキーを指すポインタをキーとし、キーをキーとしないでオブジェクトを保存したい場合は、何が起こるか考えてみましょう.キーを指すポインタのハッシュ値と元のキーのハッシュ値は大きく異なり、アドレスが異なるため、オブジェクトを取得するために使用できません.使用する任意のタイプのキーに対してハッシュ値を生成する方法が必要である.キーのタイプが定義されている場合、STLで提供されるハッシュ関数を使用して、定義されたクラスのデータ・メンバーにハッシュ値を生成する選択があります.stringヘッダファイルには、文字列を表すオブジェクトのハッシュ値を生成する関数オブジェクトを生成する特例化されたhashテンプレートが定義されています.文字列タイプ:string、wstring、u 16 string、u 32 stringの4つの特例化テンプレートがあります.wstringタイプの文字列にはwchar_が含まれていますtタイプの文字;u 16 stringタイプにはcharl 6_が含まれていますUTF-16で符号化されたUnicode文字であるtタイプの文字.u 32 stringタイプにはchar 32が含まれています.UTF-32で符号化されたUnicode文字であるtタイプの文字.もちろん、文字タイプchar、wchar_t、charl6_tとchar 32_tはいずれもC++14の基本タイプである.次に、文字列オブジェクトをハッシュする例を示します.

std::hash<:string> hash_str;
std::string food {"corned beef"};
std::cout << "corned beef hash is " <

ここでは、前の章の例と同じ方法でstringオブジェクトをハッシュする関数オブジェクトを生成します.今回のテストの出力結果は以下の通りです.
corned beef hash is 3803755380
ここではCスタイル文字列のハッシュについて具体的な規定はありません.const char*タイプのhashテンプレートを使用すると、ポインタが特例化されます.Cスタイルの文字列を文字列としてハッシュしてハッシュ値を生成する場合は、stringオブジェクトを生成し、関数オブジェクトhashを使用します.コードセグメントによって生成されるハッシュ値は非常に大きい数であり、無秩序コンテナ内のオブジェクトの位置を決定するのに役に立たないように見えます.ハッシュ値を使用して、コンテナ内のオブジェクトの位置を決定する方法はいくつかあります.1つの一般的な使用法は、ハッシュ値のビットシーケンスをテーブルまたはツリー内のオブジェクトのインデックスとして使用することである.