問題タブ [hash-function]

固定サイズの文字列と整数で構成される単純な構造体があります。この構造体をハッシュ テーブルのキーとして使用する必要があります。文字列 Hs(string) のハッシュ関数と、整数 Hi(int) のハッシュ関数があります。この単純な構造体のハッシュ関数が H(struct) = Hs(string) + になるかどうか疑問に思っています。こんにちは(整数)? または、整数を文字列にエンコードして文字列に追加し、文字列ハッシュ関数を使用することもできます。助言がありますか？ありがとう。

次の要件を悪用するハッシュ関数を探しています。

• N個の異なる整数値がハッシュテーブルに保存されます
• 任意の時点で、ハッシュテーブルに存在する値が M 個を超えることはありません
• ハッシュテーブルはいくつかのクエリに対して静的なままです (つまり、ある時点でハッシュテーブル全体が初期化され、次の呼び出しはハッシュテーブルからのみ読み取られます)
• 可能な最大のキー値 K は、ハッシュテーブルの初期化時に既知です (K >> N)
• クエリされたすべてのキーと値のペアがハッシュテーブルに存在する

これまでのところ、次のようなハッシュ関数を使用しています: h(k) = 7 * k % M with M = PRIME_CLOSE_TO(7*N)

7はやや恣意的です。

これを改善する方法について何か提案はありますか?

私のインストラクターはこれを私たちに投げかけ、ハッシュ関数の書き方をググる必要があるだけだと言いました. 私はこれについて非常に方向性がありません。クラス用の基本的なハッシュ テーブル テンプレートを作成しましたが、約 160,000 個の文字列を少なくとも 500 個のバケットを持つテーブルに並べ替える必要があるプロジェクトが予定されています (速度を上げるために、もっと多くのことをしたいと考えています)。

これに関する簡潔で簡単に消化できる情報をどこから入手すればよいかわかりません。

どんな助けでも大歓迎です。

私のハッシュ関数は次のとおりです。

約 160,000 個の文字列を、1 つあたり約 3 ～ 10 個の文字列を含むテーブルに分散しようとしています。私はかなり迷っています。

上記の実装は非常にトップヘビーです。私の任務では、少なくとも 500 個のバケットが必要ですが、それ以上の数でも十分です。

誰にも提案/方向性はありますか? それは大歓迎です。

Cコードからdjb2ハッシュ関数を翻訳しようとしました

C ++コードに、しかし私はセグメンテーション違反があります。

私の間違いはどこですか？前もって感謝します

unordered_mapC++ では、順不同の連想コンテナー ( 、unordered_set、 など)ごとunordered_multimapにハッシュ関数を定義する必要があります。ウィキペディアで指摘されているように、

struct hash_Xのカスタムハッシュ関数ですstruct X。しかし、この関数は何をするのでしょうか? なぜハッシュ関数が必要なのですか? 他のタイプのカスタム ハッシュ関数はありますか? もしそうなら、どのように2つのそのような機能間の効率を比較しますか.