Question

What are some good hash functions that can be used for implementing Rabin-Karp string search algorithm? I only know of polynomial hash, but it has some flaws — most notably, if hashing is done modulo 264, there is a test which is guaranteed to produce collisions very often (and using another modulus is impractical because the mod operation is very expensive). So, is there a fast, easy-to-write good hash function?

P.S. I know about buzhash, but I am wondering if there are other alternatives…

Was it helpful?

Solution

Since it's not a security hash and you just need a "good" fingerprint, I would suggest something like Tabulation hashing. The hole operation will be about multiple fold faster than mod operation.

Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow
scroll top