CODEWITHSUNDEEP
hashhashtablecollisionhash-functionhash-collision
Pavel
Pavel

Reputation: 11

What is wrong with this hash function implementation

I have been asked what is a problem with hash function:

h(S) = ((sum(S[i]*x**i)) mod p) mod m,

where i = {1, ..., s-1}. S - some long string, x - some positive number, s - length of S, p - number(1e9), m - hash table capacity.

How can I lower probability of collision in this hash function? Maybe x and p must be relatively prime numbers, or some group of string in this hash function would give same hashes and I need somehow change it?

I thought that problem is overflow and tried Horner's method, but the problem turned out to be collisions

Upvotes: 1

Views: 57

Answers (1)

Raymond Hettinger
Raymond Hettinger

Reputation: 226624

Consider modifying your Horner's method code to provide some feedback from prior steps. Something like this: hᵢ = (Sᵢ ⋅ hᵢ₋₁ + c) mod p where c is a non-zero constant below p.

Upvotes: 0

Related Questions