1

Rabin-Karp 文字列検索アルゴリズムの実装に使用できる優れたハッシュ関数は何ですか? 私は多項式ハッシュしか知りませんが、いくつかの欠陥があります。最も顕著なのは、ハッシングが modulo 2 64で行われる場合、非常に頻繁に衝突が発生することが保証されているテストがあります (mod操作が非常に高価であるため、別の法を使用することは実用的ではありません) 。 . では、高速で書きやすい優れたハッシュ関数はありますか?

PS buzhash については知っていますが、他に代替手段があるかどうか疑問に思っています…</p>

4

1 に答える 1

1

これはセキュリティ ハッシュではなく、「適切な」フィンガープリントが必要なだけなので、Tabulation hashingのようなものをお勧めします。穴の操作は、mod 操作よりも約 1 倍高速になります。

于 2012-10-05T01:37:46.387 に答える