問題タブ [perfect-hash]

私はプログラミング言語を開発しています。私のプログラミング言語では、オブジェクトをハッシュ テーブルとして保存しています。私が使用しているハッシュ関数は、256 ビットのルックアップ テーブルに依存するPearson Hashingです。関数は次のとおりです。

私の質問は、256 未満のメンバー名の固定グループが与えられたlookup場合pearson()、'\0'. つまり、完全なハッシュのルックアップ テーブルを作成するアルゴリズムが必要です。これにより、メンバーの数よりも多くのスペースを占有しないオブジェクトを持つことができます。これはコンパイル時に行われるため、速度は大きな問題ではありませんが、高速であればあるほどよいでしょう。これをブルート フォースするのは簡単ですが、もっと良い方法があると思います (願っています)。

例を次に示します。クラスにメンバー変数 'foo'、'bar'、および 'baz' がある場合、次のlookupように決定したいと考えています。

順序は問題ではないことに注意してください。したがって、次の結果も許容されます。

理想的な世界では、テーブルにないすべての名前は 2 より大きい値を返します。これにより、チェックを回避でき、メンバー名の保存を回避できる可能性もありますが、これが可能だとは思わないので、テーブルにあるかどうかを確認するために、追加のチェックを追加する必要があります。これを考えると、使用されていないルックアップ テーブルの値を初期化しない方がおそらく時間を節約できます (衝突は問題ではありません。衝突してチェックに失敗した場合、それはオブジェクトにまったく含まれていないため、衝突は解決する必要はなく、エラーのみを処理する必要があります)。

クラスCがあります：

これを使用して、効率的なマップのインデックスを作成したいと考えています。最も効率的なマップは配列です。そこで、コンパニオン オブジェクトに「グローバル」「静的」カウンターを追加して、各オブジェクトに一意の ID を付与します。

C のプライマリ コンストラクターでは、CI を作成するたびに、グローバル カウンターの値を記憶して増やしたいと考えています。
質問 1:どのようにそれを行う?

これで、C オブジェクトで id をインデックス配列への完全なハッシュとして使用できるようになりました。しかし、array は、特定の配列が C の ID によってインデックス付けされる map のような型情報を保持しません。

質問 2:型安全性を持たせることは可能ですか?

更新:
質問 2 の型の安全性は、2 つの関連しない int の混合を避けるために、マップのインデックスの型に関係します。もちろん、値は（型）セーフです..

質問 1 では、デフォルト コンストラクターで変数をインクリメントする方法を尋ねています。
伊：どこに置く？

限られた範囲の文字列を（非常に）迅速に処理し、それらの値を集計する必要があります。入力ファイルの形式は次のとおりです。

などなど。線幅が同じなので、適度に速い行を簡単に読み取ることができ、fread機能する完璧なハッシュ関数を開発しましたが、それをさらに速くする方法について誰かがアドバイスをくれるかどうかを確認したいと思いました。それぞれの提案のプロファイルを作成して、それがどのように行われるかを確認します。

ハッシュ関数は月の名前に基づいており、バケットへの値の迅速な割り当てを可能にします。ここで私と一緒に耐えなさい。私は最初に、完全なハッシュの最小文字数を見つけました。

入力行全体があるため、月はすべて9文字であることに注意してください。

残念ながら、1か月を一意としてマークする単一の列はありません。列1の重複J、列2の重複a、列3の重複r、列4の重複u、列5以降の重複<space>（他にも重複がありますが、単一列のハッシュキーを防ぐには1つで十分です）。

ただし、1列目と4列目を使用すると、一意の値、、、、、、、、、、、、、、Juが得られます。このファイルには無効な値が含まれないため、入力データのバケットが正しくないことを心配する必要はありません。FrMcAiM<space>JeJyAuStOoNeDe

文字の16進コードを表示することにより、戦略的な値とANDをとるだけで、低い一意の値を取得できることがわかりました。

これにより、静的配列を設定して、（うまくいけば）目がくらむほど高速なハッシュ関数を作成できました。

コードでそれをテストします：

機能的に正しいことを示しています：

しかし、もっと速くできるかどうか知りたいです。

そこに何か提案はありますか？ハッシュ関数に本質的に悪いことがあれば、単純な最適化や完全な書き直しを受け入れることができます。

これはそれほど重要ではないと思いますが、最終バージョンではEBCDICを使用します。理論はそのままですが、文字のコードポイントが異なるため、AND演算がわずかに変わる可能性があります。提供されたアドバイスがEBCDICに問題なく変換されると確信しているので、ASCIIの面でのみ支援に満足します。

CMPHの最小限の完全ハッシュを使用したいと思います。VC++ プロジェクトでどのように使用できますか?

ここで VC++ 2008 Express Edition を使用して新しいプロジェクトを作成し、ヘッダー ファイルとソース ファイルを追加しましたが、コンパイル エラーが出力されます。

値をハッシュしようとしています

衝突を起こさずにサイズ13の配列にマップする関数が必要です。

私はこれを考えてグーグルで数時間を費やしましたが、これを理解することはできません。私は実行可能な解決策に近づいていません。

この種のハッシュ関数を見つけるにはどうすればよいですか？gperfで遊んだことがありますが、よくわからず、探していた結果が得られませんでした。

ウィキペディアで鳩の巣原理を読んでいると、「ハッシュテーブルでは、可能なキーの数が配列内のインデックスの数を超えるため、衝突は避けられません。どんなに巧妙であっても、これらの衝突を回避できるハッシュアルゴリズムはありません」。しかし、gperfはこれを正確に行っていませんか？

啓発してください。

10^11の数値をハッシュできる完璧なハッシュ/一方向性関数を探すように頼まれました。ただし、組み込みデバイスを使用するため、関連するバケットを格納するためのメモリがないため、バケットなしで適切な（最小限の）完全なハッシュを作成できるかどうか疑問に思いました。

計画では、デバイスを使用して数値をハッシュし、ハッシュをオフセットとして使用するレインボーテーブルまたはファイルを使用します。

乾杯

編集：

私はいくつかのより多くの情報を提供しようとします:)

1）10^11は実際には10^10になっているため、簡単になります。この数値は可能な組み合わせです。したがって、0000000001から10000000000（10 ^ 10）までの数値を取得できます。

2）計画は、番号を安全にする一方向性関数の一部として、安全でない方法で送信できるようにすることです。次に、レインボーテーブルを使用してもう一方の端で元の番号を検索します。問題は、デバイスが一般的に使用するメモリが512k-4Megであるということです。

3）それは完璧でなければなりません-私たちは100％衝突することはできません。

Edit2：

4）暗号化はデバイスでは実際には不可能であると言われているため、暗号化を使用することはできません。可能であれば、キー管理は悪夢になります。

Edit3：

これは賢明ではないので、今は純粋に学術的な質問です（私は約束します）

ピアソンの完全なハッシュを生成するジェネレーターを作成しようとしています。最小限の完全なハッシュは必要ないことに注意してください。ウィキペディアによると、ピアソンの完全ハッシュは、ランダム化されたアルゴリズム (S はキーのセット) を使用して O(|S|) 時間で見つけることができます。ただし、そのようなアルゴリズムをオンラインで見つけることができませんでした。これは可能ですか？

注: gperf/cmph/etc. は使用したくありません。独自の実装を作成したいと考えています。

指定された文字列キーの整数を返す必要がある、次のシグネチャを持つ検索関数を考えてみましょう。

さらに、キーと値のマッピング (番号 N) は、関数のソース コードが記述されているときに事前にわかっていることを考慮してください。たとえば、次のようになります。

したがって、上記の入力に対する関数の有効な (ただし完全ではない!) 実装は次のようになります。

また、特定のキーごとに関数が実行時に呼び出される正確な回数 (C>=1) も事前にわかっています。例えば：

ただし、そのような呼び出しの順序は不明です。たとえば、上記は実行時に次の一連の呼び出しを記述することができます。

呼び出し回数が一致する場合、またはその他のシーケンス。

制限 M もあり、最も便利な単位で指定され、 で使用できるルックアップ テーブルやその他のヘルパー構造体のメモリ上限を定義しますGetValue(構造体は事前に初期化されます。その初期化は複雑さに対してカウントされません)。関数の）。たとえば、M=100 文字、または M=256 sizeof(オブジェクト参照) です。

GetValue問題は、可能な限り高速になるように の本体を記述する方法です。つまり、すべてのGetValue呼び出しの合計時間 (上記のすべての合計数を知っていることに注意してください) は、与えられた N、C に対して最小です。そしてM？

アルゴリズムは、M の妥当な最小値を必要とする場合があります (例: M >= ) char.MaxValue。また、M を何らかの合理的な境界に揃えることも必要になる場合があります。たとえば、2 のべき乗のみである場合などです。また、M が特定の種類の N の関数でなければならないことも必要になる場合があります (たとえば、有効な M=N、または M=2N、...; または有効な M=N、または M=N^2、 ...;など)。

アルゴリズムは、適切な言語またはその他の形式で表現できます。生成されたコードのランタイム パフォーマンスの制約については、生成されたコードGetValueが C#、VB、または Java であると仮定します (実際には、文字列が文字の不変配列として扱われる限り、つまり O(1) の長さと O (1) 索引付け、事前に計算されたその他のデータなし)。また、これを少し単純化するために、すべてのキーに対して C=1 であると仮定する回答は有効と見なされますが、より一般的なケースをカバーする回答が優先されます。

可能なアプローチについてのいくつかの熟考

上記に対する明白な最初の答えは、完全なハッシュを使用することですが、完全なハッシュを見つけるための一般的なアプローチは不完全なようです。たとえば、上記のサンプル データに対して Pearson ハッシュを使用して最小限の完全ハッシュのテーブルを簡単に生成できますが、その場合、 を呼び出すたびに入力キーをGetValueハッシュする必要があり、Pearson ハッシュは必然的に入力文字列全体をスキャンします。しかし、すべてのサンプル キーは実際には 3 番目の文字が異なるため、文字列全体ではなく、3 番目の文字のみをハッシュの入力として使用できます。さらに、M が少なくともchar.MaxValueである必要がある場合、3 番目の文字自体が完全なハッシュになります。

別のキーのセットでは、これはもはや当てはまらないかもしれませんが、正確な答えを得る前に考慮される文字の量を減らすことはまだ可能かもしれません. さらに、最小限の完全なハッシュが文字列全体を検査する必要がある場合は、ハッシュを非最小限にすることで、ルックアップをサブセットに減らすか、そうでなければ高速化することができます (たとえば、より複雑でないハッシュ関数?)。 (つまり、M > N) - 速度のためにスペースを効果的に犠牲にします。

また、従来のハッシュは最初からあまり良い考えではない可能性もありますGetValue。一連の条件として本体を構造化する方が簡単であり、最初に「最も可変性のある」文字 (全体的に変化する文字) をチェックするように配置されます。ほとんどのキー)、正しい答えを決定するために、必要に応じてさらにネストされたチェックを行います。ここでの「分散」は、各キーが検索される回数の影響を受ける可能性があることに注意してください (C)。さらに、ブランチの最良の構造がどのようなものであるべきかは、常に容易に明らかであるとは限りません。たとえば、「最も変化しやすい」文字では、100 個のキーのうち 10 個のキーしか区別できず、残りの 90 個のキーについては 1 回の追加チェックが必要になる場合があります。それらを区別する必要はありません。「最も変化しやすい」キャラクターから始めないでください。目標は、チェックの完全な順序を決定することです。

[0;の範囲に多くの整数があります。2^63-1]。ただし、整数は10^8しかありません。重複はありません。完全なリストはコンパイル時に知られていますが、それは単なる一意の乱数です。これらの数値は変更されません。
1つの整数を明示的に格納するには、8バイトが必要であり、1バイトの値が関連付けられているため、明示的に格納するには約860MBが必要です。
したがって、[0; 2^63-1]から[0;10^8-1]までの10^8個の整数のそれぞれをマップするための最小限の完全なハッシュ関数を見つけたいと思います。この関数は一度だけ見つける必要があり、データが変更されることはなく、関数が複雑になる可能性があります。しかし、それは最小限で完璧でなければならず、計算は高速でなければなりません。どうすればこれをより良くすることができますか？たぶん、それらが発生した場合、いくつかのサブシーケンスを見つけて使用することは可能ですか？
ありがとう。