問題タブ [perfect-hash]

longたとえば、値がLong.MIN_VALUE = 0x80...0(-2^63) とLong.MAX_VALUE = 0x7f...f(2^63 - 1)の間の整数型があります。Long.MAX_VALUEきれいで効率的な方法で、同じ型 (つまり 1 と の間) の正の整数に ~50% の衝突でハッシュしたいと考えています。

私の最初の試みは次のようなものでした：

• Math.abs(x) + 1
• (x & Long.MAX_VALUE) + 1

しかし、それらおよび同様のアプローチには、特定の値、つまりxis 0/ Long.MIN_VALUE/の場合に常に問題がありますLong.MAX_VALUE。もちろん、単純な解決策は 2 つの if ステートメントを使用することですが、よりクリーンで、より短く、より高速なものを探しています。何か案は？

注: ブール値への暗黙的な変換がなく、シフト セマンティクスが定義されている Java で作業していると仮定します。

これが私が必要とするものです（言語：C＃4）：

苦情を提出できる制度を構築しています。苦情が提出されると、システム内の苦情を識別する一意の9桁の番号が与えられます。

セキュリティ（隠すことによるセキュリティ）の目的で、チケットIDをシーケンシャルにしたくありません。しかし、データベースを使用してシーケンシャルIDを生成したいと思います。

したがって、必要なのは、両方の方法で高速な単射関数です。つまり、連続番号からチケットIDに、そしてチケットIDから連続番号に戻ります。

ticketIdデータベース内がシーケンシャルであるように、ユーザーに表示する前に難読化します。同様に、ユーザーから番号を取得したら、難読化を解除し、データベースで苦情を検索するために使用します。

難読化の部分は、あまり複雑である必要はなく、一般の人々にとっては「十分に明白ではない」だけです。

たとえば、値のビット数を変更するだけで、次のようになります（8ビット値の場合）。

0-> 0
1-> 128
2-> 192
3-> 64
4-> 160
5-> 96

等

0xc0003000から0xc04a0144までのメモリアドレスのリストがあります。リストには多くのギャップがあり、4096未満のエントリがあります。コンパイル時に既知であり、完璧なハッシュを作成したいと思います。

ただし、完全なハッシュをオンラインで検索すると、主にハッシュ文字列に関連する情報が得られ、それらはうまく翻訳されていないようです。

明確にするために、実行時にメモリアドレスを取得し、それがハッシュにすばやく含まれていることを確認できるようにしたいと思います。現在、私は答えを見つけるために平均して約8ループの二分探索を使用しています。

樹皮を張るべき木はありますか？

まず、2つの整数Nとを定義します。KここでN >= K、両方ともコンパイル時に認識されます。例：N = 8およびK = 3。

次に、整数のセットを定義し[0, N)（または[1, N]、それによって答えが簡単になる場合）、それを呼び出しますS。例えば：{0, 1, 2, 3, 4, 5, 6, 7}

SwithK要素のサブセットの数は式で与えられC(N, K)ます。例

私の問題はこれです：それらのサブセットのための完全な最小ハッシュを作成します。サンプルのハッシュテーブルのサイズはC(8, 3)またはになります56。

順序は気にせず、ハッシュテーブルに56個のエントリがあり、K整数のセットからハッシュをすばやく決定できることだけです。可逆性も気にしません。

ハッシュの例：hash({5, 2, 3}) = 42。（42という数字は重要ではありませんが、少なくともここでは重要ではありません）

Nおよびの任意の値で機能するこのための一般的なアルゴリズムはありKますか？私はグーグルを検索することによって、または私自身の素朴な努力によってそれを見つけることができませんでした。

私は Google Maps API を使用していますが、大規模なswitchステートメント以外にパノラマ画像を検索するためのより良い方法があると感じています。外部ハッシュ テーブルを使用すると、はるかに効率的で、保守がはるかに簡単になると思います。各画像には一意panoIDの があり、これを定義できます。ハッシュ テーブルを読んで、必要なデータを一定時間内に取得するためのテーブルと完璧な関数を作成できると言っているのは正しいと思います。これを構築する方法に関する良いリソースはありますか? 私はハッシュの経験がまったくありません。

私のロジックは次のようになります。各画像は としてディレクトリsometext_panoID.jpgに保存されます。前述の switch ステートメントでデータを初期化するとき、すべての切り替えは panoID に従って行われ、他のメタデータはそこでアクセスされます。例えば：sometextpanoID

私はすべてのpanoIDs を知っており、テーブルが構築されたらソート、追加、またはその他の変更を行う必要がないため、完全なハッシュを作成する方法があると感じていますが、どこから始めればよいかわかりません。任意のヒント？事前にたくさんありがとう

ハッシュされる要素の数がわかっている場合、文字列から整数への完全なハッシュ関数を持つことは可能ですか? 完全なハッシュ関数とは、衝突の可能性がないことを意味します。

基本的に、ファイルから複数のテーブルの署名を読み取っています (例: ID、名前、アドレス)。異なるテーブルには共通の属性 (名前など) がありますが、位置 (列など)は異なります。次のような質問ができるようにしたいと思います: table1["name"] とは? または table2["名前"]。

更新: 既にあるものを使用するよりも、自分でそれを行うことを学ぶことを好みます。

アドレスを記述する構造があります。次のようになります。

すべての構造プロパティに依存するこの構造の一意の識別子を作成する方法を探しています（ のタイプでもある必要があると思います）（たとえば、 を変更すると、構造識別子も変更されます）。stringAddressLine1

すべてのプロパティを連結することもできますが、これでは識別子が長すぎます。これよりかなり短いものを探しています。

また、異なるアドレスの数は 100M を超えないようにします。

この識別子を生成する方法についてのアイデアはありますか?

前もって感謝します。

これの前史：

データベースには、いくつかの情報と住所データを保持するいくつかの異なるテーブルがあります。データは、上記と同様の形式で保存されます。

残念ながら、住所データを別のテーブルに移動することは、現時点では非常にコストがかかりますが、将来的に行われることを願っています.

追加のプロパティを住所データに関連付ける必要があり、このために別のテーブルを作成します。そのため、住所データを一意に識別する必要があります。

http://java-bytes.blogspot.com/2009/10/hashcode-of-string-in-java.htmlによると、「まず、完全なハッシュ アルゴリズムがないという既知の事実があります。衝突はありません。」

著者は理論的にではなく実際に話していますよね？理論的には、ここに完全なハッシュ関数があるため、「特定のオブジェクトに新しい番号を割り当てる」。数は無数にあるため、一意のオブジェクトに割り当てるものは常に存在します。ただし、メモリの量が限られているため、実際にはこれは実現可能ではありません。

私はハッシュとハッシュテーブルを読んで学習しており、いくつかのコードで実験しました（私はまだこれに非常に慣れていないので、誤解した何か間違ったことを言うかもしれません）。私は完全なハッシュ関数の問題に直面しました。どういうわけか完全なハッシュ関数を持つ独自のカスタム型があるとします。

Anintのハッシュコードはintそれ自体なので、完全なハッシュ関数を持っていますよね? しかし、ハッシュ関数を使用して、単純な式でオブジェクトをハッシュテーブルにマップすると、次のようになります。

ハッシュテーブルにある要素の数にも依存する可変インデックスを取得します。ハッシュテーブルのサイズが int.MaxValue のみの場合、完全なハッシュ関数が得られます。たとえば、サイズが 2 のハッシュテーブルがあるとします。たとえば、数値 1 と 3 をハッシュすると、次のようになります。

衝突！ハッシュとハッシュテーブルについて何か間違ったことを理解しましたか? 完全なハッシュ関数は完全ではないことがわかります。

ハッシュ関数のハッシュ キーのリストが既知で不変の場合、完全なハッシュ関数を生成できます。JavaのEnumは、既知の不変要素のリストです。したがって、 EnumMapを完全なハッシュとして実装できるはずです。これは現在 (1.7) Java で行われていますか?