hashtable - What is wrong with this hash function implementation - Stack Overflow

admin管理员组

文章数量:1415100

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

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

• hash
• hashtable
• collision
• hash-function
• hash-collision

Share Improve this question Follow edited Feb 20 at 23:55 Barmar 784k5757 gold badges548548 silver badges659659 bronze badges asked Feb 20 at 23:49 PavelPavel 1111 bronze badge 6

• 1 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 Commented Feb 20 at 23:56
• 1 This might be better asked at Cryptography, I think. – Ken Y-N Commented Feb 21 at 0:02
• @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 Commented Feb 21 at 11:23
• @Ken Y-N, thanks, i will try – Pavel Commented Feb 21 at 11:25
• 1 @KenY-N If it's for hash tables, cryptographically secure hashing is not usually a concern. Speed and collision avoidance are more important. – Barmar Commented Feb 21 at 15:33

 |  Show 1 more comment

1 Answer 1

Sorted by: Reset to default 0

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.

本文标签： hashtableWhat is wrong with this hash function implementationStack Overflow