私は CLRS を読んでいます。この行に出くわしたという点で、「任意の ts が q を法として p に等しくなる可能性が推定できるため、スプリアス ヒットの数は O(n/q) であると予想できます。 1/q として」
34.2トピックの下に完全な説明を含むWebサイトを掲載しています
スプリアス ヒット = O (n/q) を期待する方法を説明してください。
参考までにhttp://staff.ustc.edu.cn/~csli/ Graduate/algorithms/book6/chap34.htm
分析の目的で、使用されるハッシュ関数が であると想定されることがよくありSimple Uniform Hashingます。この仮定は、他のキーがどのようにハッシュされるかに関係なく、すべてのキーが等しくハッシュされる可能性が高いことを示しています。
つまり、qハッシュ関数が生成できる可能性のある値が与えられた場合、それぞれの確率は です1/q。
リンク先の例では、2 つの異なる文字列が同じ値にハッシュされた場合のスプリアス ヒットシナリオについて説明しています。単純な一様ハッシュが与えられた場合、このイベントの確率は?
最初の文字列は値にハッシュされますx。2 番目の文字列も値にハッシュされる確率はx? です1/q。
Karp-Rabin アルゴリズムについて説明しているこの講義をお勧めします。