hash_map

Discussion in 'C++' started by peter_k, Nov 11, 2005.

  1. peter_k

    peter_k Guest

    Please, help me, i'm new to this.

    I want to do hash_map, where key will be unique structure...

    struct key {
    long data[3];
    }

    ....and the value will be unsigned char;

    How to do efficient hash function which will return first 20 bits of
    data[3]??
    So my hash will have table of 1048657 elements...

    *) Is standard hash_map very fast?? I wanted to store here about 128 MB
    of elements...

    Thanks for help
    peter_k, Nov 11, 2005
    #1
    1. Advertising

  2. peter_k wrote:
    > Please, help me, i'm new to this.
    >
    > I want to do hash_map, where key will be unique structure...
    >
    > struct key {
    > long data[3];
    > }
    >
    > ...and the value will be unsigned char;
    >
    > How to do efficient hash function which will return first 20 bits of
    > data[3]??
    > So my hash will have table of 1048657 elements...
    >
    > *) Is standard hash_map very fast?? I wanted to store here about 128 MB
    > of elements...


    hash_map is not part of the c++ standard. you should have a look at
    your library vendor documentation concerning the concrete
    implementation.

    try to benchmark your implementations default hash algorithm for
    performance figures. if these do not suffice other groups like
    sci.crpyt or comp.programming should be appropiate for information
    regarding known fast hash algorithms for your specific problem.

    -- peter
    Peter Steiner, Nov 11, 2005
    #2
    1. Advertising

  3. peter_k

    Mirek Fidler Guest

    peter_k wrote:
    > Please, help me, i'm new to this.
    >
    > I want to do hash_map, where key will be unique structure...
    >
    > struct key {
    > long data[3];
    > }
    >
    > ...and the value will be unsigned char;
    >
    > How to do efficient hash function which will return first 20 bits of
    > data[3]??


    (I hope you meant 20 bits of whole data as there is no data[3] element :).

    Why do you want just 20 bits of data? When generating hash, you should
    always try to combine as much of key as possible.

    Now to combine data of key, I am using this kind of operations:

    unsigned hash = 123456789; //initial seed
    hash = ((hash << 4) + hash) ^ data[0];
    hash = ((hash << 4) + hash) ^ data[1];
    hash = ((hash << 4) + hash) ^ data[2];

    (actually, I have helper template class to do this). Not perfect maybe,
    but good enough.

    > So my hash will have table of 1048657 elements...
    >
    > *) Is standard hash_map very fast?? I wanted to store here about 128 MB
    > of elements...


    Well, number of keys is more important than total amount of data....

    Generally, hash maps are faster than binary trees, especially for very
    large data sets, but have nasty characteristics to behave oddly when
    your hash function has some problems or sometimes (but it is very rare)
    when your hash function is exposed to specific data (resulting in too
    many collisions).

    Anyway, I use hash-maps exclusively...

    Mirek
    Mirek Fidler, Nov 11, 2005
    #3
  4. peter_k

    peter_k Guest

    Thanks for the reply!

    I'm coding fast engine for one of board games in c++. In data[3] i'll
    store tokens. Only data[0] & data[1] will be used at 100%, but i think
    this will be no difference if i'll take 20 bits of first or 10 bits
    from both.

    So if i want to make hash i should to something like:

    namespace __gnu_cxx {
    template<>
    struct hash<my_structure> {
    size_t operator()(my_structure) const {
    return (my_structure << 12); // or 20 here?
    };
    };
    };

    ?
    peter_k, Nov 11, 2005
    #4
    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. Kristofer Pettijohn

    2d hash_map iteration ?

    Kristofer Pettijohn, Jun 26, 2003, in forum: C++
    Replies:
    1
    Views:
    981
    Rob Williscroft
    Jun 26, 2003
  2. Jacek Generowicz

    Pre-standardizing hash_map & friends.

    Jacek Generowicz, Aug 26, 2003, in forum: C++
    Replies:
    0
    Views:
    352
    Jacek Generowicz
    Aug 26, 2003
  3. Charles Herman

    hash_map iterator

    Charles Herman, Nov 3, 2003, in forum: C++
    Replies:
    5
    Views:
    5,959
    Ron Natalie
    Nov 4, 2003
  4. Florian Liefers

    C2143, hash_map

    Florian Liefers, Nov 12, 2003, in forum: C++
    Replies:
    11
    Views:
    1,296
    Dan Cernat
    Nov 12, 2003
  5. Jon Cosby

    hash_map

    Jon Cosby, Nov 30, 2003, in forum: C++
    Replies:
    10
    Views:
    8,613
    David Fisher
    Dec 2, 2003
Loading...

Share This Page