ハッシュの衝突が問題になるシステムに取り組んでいます。基本的に、ハッシュテーブル+ツリー構造でアイテムを参照するシステムがあります。ただし、問題のシステムは、最初に構造内のパスを含むテキスト ファイルを代わりにハッシュ値を含むバイナリ ファイルにコンパイルします。これは、パフォーマンス上の理由から行われます。ただし、構造体は同じハッシュ値を持つ 2 つのアイテムを格納できないため、この衝突は非常に悪いものです。アイテムを要求する部分には、必要なアイテムを知るのに十分な情報がありません。
私の最初の考えは、2 つの異なるアルゴリズムを使用するか、2 つのソルトを使用して同じアルゴリズムを 2 回使用する 2 つのハッシュの方が衝突耐性が高いということです。異なるハッシュ アルゴリズムに対して同じハッシュを持つ 2 つのアイテムはほとんどありません。
スペース上の理由から、ハッシュ値を 32 ビットのままにしたかったので、1 つの 32 ビット アルゴリズムの代わりに 2 つの 16 ビット アルゴリズムを使用するように切り替えることができると考えました。しかし、それは可能なハッシュ値の範囲を広げません...
2 つの 32 ビット ハッシュに切り替えると衝突に対する耐性が高まることはわかっていますが、2 つの 16 ビット ハッシュに切り替えると、1 つの 32 ビット ハッシュよりも少なくともある程度のメリットがあるのでしょうか? 私は数学に最も傾倒した人間ではないので、力ずくで答えを調べる以外に、答えをチェックする方法さえ知りません...
システムの背景:
アイテムは人間によって付けられた名前であり、ランダムな文字列ではなく、通常、空白のない単語、文字、および数字で構成されます。これはネストされたハッシュ構造であるため、{ a => { b => { c => 'blah' }}} のようなものがある場合、a/b/c の値を取得することで値 'blah' を取得します。コンパイルされたリクエストは、a、b、c のハッシュ値の 3 つのハッシュ値がすぐに連続したものになります。
特定のレベルで衝突がある場合にのみ問題があります。最上位レベルと下位レベルのアイテム間の衝突は問題ありません。{ a => {a => {...}}} を持つことができ、異なるレベルでの衝突がほぼ保証されます (問題ではありません)。
実際には、任意のレベルでハッシュする値は 100 未満である可能性が高く、同じレベルで重複するものはありません。
私が採用したハッシュアルゴリズムをテストするために (どれを忘れたか忘れましたが、私はそれを発明しませんでした)、CPAN Perl モジュールのリスト全体をダウンロードし、すべての名前空間/モジュールを一意の単語に分割し、最後に衝突を検索してそれぞれをハッシュしました。0 に遭遇しました。衝突。これは、アルゴリズムが、CPAN 名前空間リスト内の一意の単語ごとに異なるハッシュ値を持っていることを意味します (または、私が間違っていました)。それは私には十分に思えますが、それでも私の頭を悩ませています。