What is wrong with this hash function implementation

Question

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

Many languages have hash functions built in or in common libraries. Why are you writing your own? They also often have built-in hash table implementations. — Barmar
– Barmar, Commented Feb 20 at 23:56
@Barmar, I need to implement my own hash function and hash table as part of a coursework assignment. I can't use built in hash functions — Pavel
– Pavel, Commented Feb 21 at 11:23
@KenY-N If it's for hash tables, cryptographically secure hashing is not usually a concern. Speed and collision avoidance are more important. — Barmar
– Barmar, Commented Feb 21 at 15:33

Raymond Hettinger · Accepted Answer · 2025-02-20 23:59:25Z

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.

Collectives™ on Stack Overflow

What is wrong with this hash function implementation

1 Answer 1

Comments

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Related