Hash key for vector of 3 ints

[onelesscar]

Hi all,


I'm currently creating my hash key by stuffing the bits into an
unsigned long long.

key = static_cast<uint64>(x) | (static_cast<uint64>(y) << 20) |
(static_cast<uint64>(z) << 40);

But this limits the range in x,y,z.

I've made a few attempts in Visual Studio including making an XOR of
the vector ints.
I don't think the XOR gives keys that are unique enough.

error C2440: 'type cast' : cannot convert from 'const vector3i' to
'size_t' c:\program files\microsoft visual studio 8\vc\include
\xhash


Anyone have an example or hints?
thanks

 

[James Kanze]

I'm currently creating my hash key by stuffing the bits into an
unsigned long long.

key = static_cast<uint64>(x) | (static_cast<uint64>(y) << 20) |
(static_cast<uint64>(z) << 40);

But this limits the range in x,y,z.

I've made a few attempts in Visual Studio including making an
XOR of the vector ints. I don't think the XOR gives keys that
are unique enough.

I don't either. Especially, it will result in all permutations
of the same values having the same hash code.

You might want to read
http://kanze.james.neuf.fr/code/Docs/html/Hashcode.html. This
summarizes the results of some trials I did years back. (I've
since updated it with some additional hash code algorithms, but
the newer version isn't on line, and the results don't really
change either.) The article, like most articles concerning hash
codes, concerns hashing strings, but in fact, most of the
algorithms (including all of the good ones) will work for any
sequence whose elements can be converted into an unsigned int.

The basic conclusion is to use either FNV or a Mersenne prime
hash. (The Mersenne prime may be slightly faster on machines
with a slow multiply.)

You might also be interesting in the Hashing component of my
library (http://kanze.james.neuf.fr/code-en.html -- it's in the
Basic subsystem). It contains a few generic functions for
generating a FNV hash, and a generic HashAccumulator which can
be used to hash any sequence using std::accumulate. Although
they were designed to be used within the context of my library,
it shouldn't be too difficult to extract them and adapt them to
your needs.