I was reading about hashing.
The oldest/standard approach is to use a prime number to produce the hash.
At first I couldn't get why use a prime when I came to this Why hash functions use primes:
Primes are unique numbers. They are unique in that, the product of a prime with any other number has the best chance of being unique (not as unique as the prime itself of-course) due to the fact that a prime is used to compose it. This property is used in hashing functions.
I am not sure I get completely the concept here.
Does it mean that multiplying a*b
and c*d
the posibility to produce the same result is smaller if one of these numbers e.g. a
is a prime?
I was wondering how is this proven in an intuitive manner?
I mean I can understand abstractly the idea but can not formulate something intuitive to base the whole hashing upon this possibility as a property of primes.
Any help?
UPDATE:
Just to be clear: My main problem was why the prime numbers have always been the standard approach for use in a hash function.
An ideal hash function rarely has colisions due to the fact that it produces "unique" hash values of its input.
The blog I mention in the post seemed to give an explanation in my problem.
But if the blog is not correct then I still end up in my original problem.
What is the property of prime numbers (I am not refering to 31 because other primes have been used for hashing) that makes them a must for a hash function.
Also this is I guess also related to the fact that the table of the hashtable must be of prime size?