質問
すべてのメンバー データ型に既に std::hash の適切な特殊化があるユーザー定義型の std::unordered_map または std::unordered_set の 3 番目のテンプレート パラメーターで使用するための std::hash の適切な特殊化は何ですか。
この質問に対して、私は「良い」とは、実装と理解が簡単で、適度に効率的で、ハッシュ テーブルの衝突が発生する可能性が低いと定義します。良いの定義には、セキュリティに関する記述は含まれません。
Google で何ができるか
現時点では、「std hash specialization」を Google で検索すると、2 つの StackOverflow の質問が最初にヒットします。
最初、順序付けられていないコンテナ内のユーザー定義型に対して std::hash::operator() を特殊化するにはどうすればよいですか?は、std 名前空間を開いてテンプレートの特殊化を追加することが正当かどうかを扱います。
二番目、他のライブラリの型にstd::hashを特化する方法は、本質的に同じ質問に答えます。
これで現在の質問は終わりです。C++ 標準ライブラリの実装では、プリミティブ型と標準ライブラリ内の型のハッシュ関数が定義されているので、std::hash をユーザー定義型に特化する簡単で効果的な方法は何でしょうか? 標準ライブラリ実装によって提供されるハッシュ関数を組み合わせる良い方法はありますか?
(dyp さん、編集ありがとうございます。)もう一つの質問StackOverflowでは、ペアハッシュ関数の。
他の Google の結果はもう役に立ちません。
これDr. Dobbs の記事では、2 つの満足できるハッシュの XOR により、新しい満足できるハッシュが生成されると述べています。
これ記事は知識に基づいて語っているようで、多くのことを暗示していますが、詳細が不足しています。最初の例の短いコメントで、ハッシュ関数を結合するために XOR を使用すると、結果として得られるハッシュ関数が弱くなると述べており、Dr. Dobbs の記事と矛盾しています。
任意の 2 つの等しい値に XOR を適用すると結果は 0 になるため、XOR 自体が弱い理由がわかります。
メタ質問
この質問がなぜ無効であり、一般的には答えられないのかを説明する、十分に根拠のある回答も歓迎します。
ベストアンサー1
簡単な方法の一つは、boost::hashライブラリとあなたのタイプに合わせて拡張する拡張機能が充実しているhash_combine(std::hashそれが欠けている) これにより、構造体の個々のデータ メンバーのハッシュを簡単に構成できるようになります。
言い換えると：
boost::hash_value独自のタイプにオーバーロードします。std::hash独自の型に特化し、 を使用して実装しますboost::hash_value。
この方法では、std と boost の両方の世界の長所を活用でき、std::hash<>自分boost::hash<>のタイプに合わせて機能します。
より良い方法は、提案されている新しいハッシュインフラストラクチャを使用することです。N3980 タイプは不明 #このインフラストラクチャはhash_combine不要になります。