多くのランダム化されたアルゴリズムとデータ構造（Count-Min Sketchなど）には、ペアごとに独立プロパティを持つハッシュ関数が必要です。直感的には、これは、特定の要素のハッシュ関数の出力がわかっている場合でも、特定の要素とのハッシュ衝突の可能性が低いことを意味します。
ランダム線形関数に基づく固定長ビットベクトルのペアごとに独立したハッシュ関数の多くの説明を見つけました。ただし、文字列のペアごとに独立したハッシュ関数の例はまだ見ていません。
文字列のペアごとに独立したハッシュ関数のファミリーはありますか？
それらが存在すると確信していますが、あなたの質問には少し測定理論的な微妙さがあります. Mathoverflow で質問したほうがいいかもしれません。私はこのようなことには非常に慣れていませんが、たとえそれらが存在していたとしても、実際にはそれを望んでいないことを示すことができると思います.
まず、文字列の確率測定が必要です。そのような測定は、必然的に「均一」の概念とは大きく異なります。(これは可算集合であり、可算集合に対するすべてのシグマ代数は、要素の集合をまとめて、それらの集合のそれぞれに確率を割り当てるだけです。すべての塊をシングルトンにする必要があります。)
ここで、有限数の文字列に正の確率のみを与えると、有限の場合に戻ります。ここではそれを無視して、任意のイプシロン > 0 について、確率が厳密に 0 とイプシロンの間にある文字列を見つけることができると仮定しましょう。
ハッシュ関数が文字列を {0,1} にマップする場合に限定するとします。
ハッシュ関数のファミリも同様に無限である必要があり、ハッシュ関数の確率空間としてそれについて話したいと思うでしょう。正の確率を持つハッシュ関数のセット H がある場合、すべての文字列は H の (異なる) 要素によって 0 と 1 の両方にマップされます。特に、H の単一の要素は正の確率を持ちません。したがって、H は数えられない必要があり、表現可能性に関する困難な問題に突然遭遇しました。
測度論を忘れていない方がいらっしゃれば嬉しいです。
制限付きの長さのシードと非ゼロの制限付き長さの出力ではありません。
この効果に対するかなり大まかな議論は、ハッシュ関数 H の有限族について、要素 x から H のすべての h に対して h(x) を与えるタプルへの写像 f を考えることです。有限であるため、H のすべての h によって同じようにマッピングされた 2 つの文字列が存在します。これは、少なくとも 2 つの可能なハッシュ値が存在することを考えると、ペアごとの独立性に矛盾します。