hash_map

[peter_k]

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 Steiner]

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

 

[Mirek Fidler]

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

 

[peter_k]

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?
};
};
};

?