Hash key for vector of 3 ints

Discussion in 'C++' started by onelesscar, Apr 9, 2008.

  1. onelesscar

    onelesscar Guest

    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
    onelesscar, Apr 9, 2008
    #1
    1. Advertising

  2. onelesscar

    James Kanze Guest

    On Apr 9, 11:12 pm, onelesscar <> wrote:

    > 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.

    --
    James Kanze (GABI Software) email:
    Conseils en informatique orientée objet/
    Beratung in objektorientierter Datenverarbeitung
    9 place Sémard, 78210 St.-Cyr-l'École, France, +33 (0)1 30 23 00 34
    James Kanze, Apr 10, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    3
    Views:
    560
    Mark P
    Apr 3, 2005
  2. Skybuck Flying

    ints ints ints and ints

    Skybuck Flying, Jul 8, 2004, in forum: C Programming
    Replies:
    24
    Views:
    829
    Jack Klein
    Jul 10, 2004
  3. Markus Dehmann

    key-value pairs: key consists of 3 ints

    Markus Dehmann, Jan 15, 2006, in forum: C++
    Replies:
    13
    Views:
    632
    Richard Herring
    Jan 23, 2006
  4. Replies:
    8
    Views:
    1,914
    Csaba
    Feb 18, 2006
  5. Une bévue
    Replies:
    5
    Views:
    149
    Une bévue
    Aug 10, 2006
Loading...

Share This Page