Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C++ > hash_map

Reply
Thread Tools

hash_map

 
 
peter_k
Guest
Posts: n/a
 
      11-11-2005
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

 
Reply With Quote
 
 
 
 
Peter Steiner
Guest
Posts: n/a
 
      11-11-2005
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

 
Reply With Quote
 
 
 
 
Mirek Fidler
Guest
Posts: n/a
 
      11-11-2005
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
 
Reply With Quote
 
peter_k
Guest
Posts: n/a
 
      11-11-2005
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?
};
};
};

?

 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
hash_map Jon Cosby C++ 10 12-02-2003 12:31 AM
C2143, hash_map Florian Liefers C++ 11 11-12-2003 09:18 PM
hash_map iterator Charles Herman C++ 5 11-04-2003 02:50 AM
Pre-standardizing hash_map & friends. Jacek Generowicz C++ 0 08-26-2003 12:58 PM
2d hash_map iteration ? Kristofer Pettijohn C++ 1 06-26-2003 08:18 AM



Advertisments