 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
peter_k
Guest
|
 Posted: Fri Nov 11, 2005 12:11 pm Post subject: hash_map |
 |
|
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
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
 |
richard@ex-parrot.com
Guest
|
| Posted: Sat Nov 12, 2005 10:25 am Post subject: Re: hash_map |
|
|
peter_k wrote:
| Quote: | 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]??
|
To get the 20 most significant non-sign bits of a long:
data[3] & (0xFFFFFl << (std::numeric_limits
(as numeric_limits<>::diits is an integer constant expression, any
reasonable optimiser will optimise this down to data[3] & 0xFFFFF000 on
a 32-bit platform, but it has the advantage of being architecture
neutral).
Or, to get the 20 least significant bits of a long:
data[3] & 0xFFFFFl
--
Richard Smith
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Alberto Ganesh Barbati
Guest
|
| Posted: Sat Nov 12, 2005 10:30 am Post subject: Re: hash_map |
|
|
peter_k wrote:
| Quote: |
*) Is standard hash_map very fast?? I wanted to store here about 128 MB
of elements...
|
Problem is that there is *no* standard container called hash_map. A few
vendors offer implementations of hashed containers and most of them are
called hash_map (a few vendors put them in namespace std but really they
shouldn't). Unfortunately, those implementation are often different and
incompatible with each other, so it's not possible to answer your
question unless you specify which implementation you are going to use.
However, if you do that, then the question would be off-topic on this
newsgroup, as it would relate to a specific implementation! ;-)
The upcoming revision of the C++ standard library (called TR1) will
introduce the container unordered_map which is in fact a hash map, but I
can't give you hints about it as I have yet to see an implementation.
Ganesh
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Harald Luessen
Guest
|
| Posted: Sat Nov 12, 2005 10:32 am Post subject: Re: hash_map |
|
|
On 11 Nov 2005 "peter_k" wrote:
| Quote: | 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...
|
For first tests you can do this:
long hash = data[0];
hash ^= data[1];
hash ^= data[2];
hash &= 0x0fffffL;
But this ignores the high-bits and the order of data elements.
Another idea:
For the rest of this posting I will assume that sizeof(long) is 4.
Prepare helper-arrays with long random numbers for each byte
on each position in data[]:
long ra[3][4][256]
int i, j, k;
for ( i = 0; i < 3; ++i )
{
for ( j = 0; j < 4; ++j )
{
for ( k = 0; k < 256; ++k )
{ // Do not trust my syntax here.
ra[i][j][k] = ((rand()&0xffffL)<<16) | (rand()&0xffff);
}
}
}
Later use this hash function:
long hash = 0;
for ( i = 0; i < 3; ++i )
{
for ( j = 0; j < 4; ++j )
{
unsigned char byte = (data[i] >> j) & 0xff;
hash ^= ra[i][j][byte];
}
}
hash &= 0x0fffffL;
In chess programming this is called Zobrist Keys.
| Quote: | *) Is standard hash_map very fast?? I wanted to store here about 128 MB
of elements...
|
Try it.
Harald
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
jrm
Guest
|
| Posted: Sat Nov 12, 2005 10:33 am Post subject: Re: hash_map |
|
|
| Quote: | How to do efficient hash function which will return first 20 bits of
data[3]??
So my hash will have table of 1048657 elements...
Do you mean data[0] & 0xFFFFF or data[2] & 0xFFFFF? |
Assuming the latter:
struct hashkey
{
size_t operator(const key& k) const
{
return k.data[2] & 0xFFFFF;
}
};
struct eqkey
{
bool operator () (const key& k1, const key& k2) const
{
return memcmp(&k1, &k2, sizeof(key)) == 0;
}
};
hash_map<key, unsigned char, hashkey, eqkey> some_hash_map(1048576);
Since you are only hashing first 20bits, the initial bucket size is
chosen around this number. The gcc implementations I have seen actually
chooses the next prime number (closest to a power of 2) from the
supplied bucket size - TAOCP by Donald Knuth covers these issues in
good detail.
| Quote: | *) Is standard hash_map very fast?? I wanted to store here about 128 MB
of elements...
|
Short answer is yes. But it will all depend upon the quality of the
hash function. Since you are storing 128MB worth of data ( (sizeof(key)
+ sizeof(value)) * n elements??), using 22 bits or more for the hash
might be recommended.
| Quote: | From space and time perspective, I would always recommend using
std::hash_map compared to other associative containers as long as the |
order of elements is not desired.
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
Harald Luessen
Guest
|
| Posted: Sun Nov 13, 2005 3:36 pm Post subject: Re: hash_map |
|
|
I wrote:
| Quote: | long hash = 0;
for ( i = 0; i < 3; ++i )
{
for ( j = 0; j < 4; ++j )
{
unsigned char byte = (data[i] >> j) & 0xff;
|
unsigned char byte = (data[i] >> (j* ) & 0xff;
| Quote: | hash ^= ra[i][j][byte];
}
}
hash &= 0x0fffffL;
|
Harald
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
