Re: Designing a hashing function in C++
"Jack" <jl@knight.com> wrote in message
news:uvEuq%23d1IHA.5300@TK2MSFTNGP06.phx.gbl
What is the general approach to design a hashing function without
collisions?
There ain't no such thing. The whole point of a hash function is to map
a large number of possible values to a smaller number of keys. Since
there are more values than keys, you would necessarily have collisions.
static inline int computeHash(int x,int z)
{
int hash = z<<16|x;
Use XOR (^) instead. With OR, keys with more 1-bits will occur
disproportionately more often than keys with more 0-bits. You want your
hash to be as close to uniformly distributed as possible.
Do you expect z to be small most of the time? If not, don't shift. You
lose high-order bits: if they are significant this would increase the
number of collisions.
--
With best wishes,
Igor Tandetnik
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going to
land, and it could be dangerous sitting under them as they fly
overhead. -- RFC 1925