DEVELOP > c-Plus-Plus > I cannot use the hash_map::operator[] to read the value in the hash map?
| Topic: |
DEVELOP > c-Plus-Plus |
| User: |
"xz" |
| Date: |
01 Aug 2007 10:52:21 PM |
| Object: |
I cannot use the hash_map::operator[] to read the value in the hash map? |
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
However, there is no example like the following:
int a = hm1[2];
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
.
|
|
| User: "Barry" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in thehash map? |
01 Aug 2007 10:58:33 PM |
|
|
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
.
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
01 Aug 2007 11:53:47 PM |
|
|
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>,
std::allocator<double> >' has no member named 'put'
.
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
01 Aug 2007 11:53:57 PM |
|
|
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>,
std::allocator<double> >' has no member named 'put'
.
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
01 Aug 2007 11:54:07 PM |
|
|
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>,
std::allocator<double> >' has no member named 'put'
.
|
|
|
| User: "Barry" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in thehash map? |
02 Aug 2007 12:06:37 AM |
|
|
xz wrote:
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>,
std::allocator<double> >' has no member named 'put'
maybe you got me wrong,
I said what you said in your original post is right
C++ Java
hm[1] = 2 hm.put(1, 2)
int i = hm[1] int i = (int) hm.get(1);
I just said they are equivalent, not meant that C++ hash_map has put/get
member functions
.
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 12:29:45 AM |
|
|
On Aug 2, 12:06 am, Barry <dh...@126.com> wrote:
xz wrote:
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>,
std::allocator<double> >' has no member named 'put'
maybe you got me wrong,
I said what you said in your original post is right
C++ Java
hm[1] = 2 hm.put(1, 2)
int i = hm[1] int i = (int) hm.get(1);
I just said they are equivalent, not meant that C++ hash_map has put/get
member functions
Now I got it. Thanks.
BTW, you may be using the HashMap in Jave incorrectly here.
HashMap in Java cannot deal with int, it can only deal with classes,
like Integer.
.
|
|
|
|
| User: "James Kanze" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 06:52:28 AM |
|
|
On Aug 2, 7:06 am, Barry <dh...@126.com> wrote:
xz wrote:
maybe you got me wrong,
I said what you said in your original post is right
C++ Java
hm[1] =3D 2 hm.put(1, 2)
int i =3D hm[1] int i =3D (int) hm.get(1);
I just said they are equivalent, not meant that C++ hash_map has put/get
member functions
They're not equivalent, or at least, I don't think so. The
operator[] in C++ map and unordered_map inserts, and can't be
used on a const object or through a const reference. In
practice, it's close to useless.
Java's HashMap is also more complicated than you indicate, since
it cannot contain int's, but only Integer's.
Roughly speaking, to read an element in C++, you need to:
Map::iterator elem =3D hm.find( key ) ;
if ( elem =3D=3D hm.end() ) {
// Doesn't exist...
} else {
T value =3D elem->second ;
// ...
}
Note that the original poster had declared a hash table of
double. I'd like to see the hash code function for that; I've
not found a good way to hash floating point to date.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
.
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 03:12:44 PM |
|
|
On Aug 2, 6:52 am, James Kanze <james.ka...@gmail.com> wrote:
Note that the original poster had declared a hash table of
double. I'd like to see the hash code function for that; I've
not found a good way to hash floating point to date.
.
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 03:13:45 PM |
|
|
On Aug 2, 6:52 am, James Kanze <james.ka...@gmail.com> wrote:
Note that the original poster had declared a hash table of
double. I'd like to see the hash code function for that; I've
not found a good way to hash floating point to date.
Now I simply use map <double, couble> and it works.
I only need the "map" or "hash map" for a small table with 5 or 6 key-
value pairs. So my code is really not demanding for efficiency.
By "good", if you mean "efficient", then I have nothing to tell
you.ace S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
.
|
|
|
| User: "James Kanze" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
03 Aug 2007 04:29:13 AM |
|
|
On Aug 2, 10:13 pm, xz <zhang.xi...@gmail.com> wrote:
On Aug 2, 6:52 am, James Kanze <james.ka...@gmail.com> wrote:
Note that the original poster had declared a hash table of
double. I'd like to see the hash code function for that; I've
not found a good way to hash floating point to date.
Now I simply use map <double, double> and it works.
That's what I'd do too:-). std::map requires an ordering
relationship, and there's a very good one already defined for
double. A hash map requires a hash function, and I've yet to
figure out a good way to write one for double. (In general.
For specific cases, where the doubles are e.g. known to be in a
limited range, it should be possible.)
I only need the "map" or "hash map" for a small table with 5
or 6 key- value pairs.
In which case, std::map is probably even faster than a hash
table. For that matter, up to about 10 or 20 elements, linear
search in a vector or a C style table can be the fastest
solution. I actually use this a lot for constant tables, with C
style arrays, so that I can use static initialization, and avoid
order of initialization problems.
So my code is really not demanding for efficiency.
By "good", if you mean "efficient", then I have nothing to tell
you.
By "good", I mean a hash function that, given two arbitrary
values that compare different, the probability is very high that
the hash value will be different. And of course, given two
values that compare the same, the hash value is guaranteed to be
the same.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
.
|
|
|
|
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
01 Aug 2007 11:52:31 PM |
|
|
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
error: 'class __gnu_cxx::hash_map<double, double,
__gnu_cxx::hash<double>, std::equal_to<double>, std::allocator<double>
' has no member named 'put'
.
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
01 Aug 2007 11:47:13 PM |
|
|
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
Thanks.
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
.
|
|
|
| User: "Alf P. Steinbach" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in thehash map? |
02 Aug 2007 12:06:17 AM |
|
|
* xz:
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
It's not a standard header.
So do whatever your /documentation/ tells you.
In the old days we just said RTFM (Read The Fucking Manual), or RTFMM,
but the younger generation, brought up on movies like Kill Bill I and
II, is so sensitive about "anti-American" terminology (nobody faqs in
America) that we can't even redirect them to <url: ftp://rtfm.mit.edu/>
to read the faqs, without a high chance of mortally offending them. And
as a consequence of that political correctness, as I recall Wikipedia
doesn't even provide the correct and only meaning of RTFM, but some
made-up US double-morality-compatible children's version. Oh well, but
anyway: RTFM, in your case <url: http://msdn.microsoft.com/library/>.
Cheers,
- Alf (slightly bad mood)
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
.
|
|
|
|
| User: "" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 12:25:11 AM |
|
|
On Aug 2, 1:47 pm, xz <zhang.xi...@gmail.com> wrote:
like km1.put(2, 40); in Java
like int a = (int) hm1.get(2); in Java
I think hash map is so basic data structure, why is it such a headache
to use this famous HASH MAP?
In java, life is simple......
This is simple? This is hideous compared to the natural operator[]
usage.
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
If you want to be a programmer, you should at least know how to do a
recursive directory search for filenames including *hash*. Really,
kids these days.... ;-P
FWIW, many people just use std::map, which has a similar interface,
the benefit of sorting the elements, is standardised and portable
(just #include <map>), and is unlikely to have a noticeable
performance difference unless you're inserting tens of thousands or
more elements for frequent lookup or the elements are difficult to
compare. Basically, map does a binary lookup which typically requires
approximately log2(N) element comparisons, or 10 for a thousand
elements, 20 for a million....
Tony
.
|
|
|
| User: "James Kanze" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 06:36:00 AM |
|
|
On Aug 2, 7:25 am, wrote:
On Aug 2, 1:47 pm, xz <zhang.xi...@gmail.com> wrote:
like km1.put(2, 40); in Java
like int a =3D (int) hm1.get(2); in Java
I think hash map is so basic data structure, why is it such a headache
to use this famous HASH MAP?
In java, life is simple......
This is simple? This is hideous compared to the natural operator[]
usage.
Still, the STL version is worse:
std::map< X, int >::const_iterator it =3D hm1.find( key ) ;
int a =3D it =3D=3D hm1.end() ? 42 : *hm1 ;
The real problem in reading a map (or a hashmap) is how to
handle missing values. Sometimes, an exception is appropriate,
but it's not a good general solution. So you need something out
of band.
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
Whatever the documentation for your system tells you. The
latest draft says <unordered_set>, but this is fairly recent,
and it's likely that your implementation still uses something
pre-standard. Which it *should* document.
If you want to be a programmer, you should at least know how to do a
recursive directory search for filenames including *hash*. Really,
kids these days.... ;-P
Given that the correct name is unordered_set, searching for a
file whose name includes *hash* isn't going to help. More
generally, of course, recursive directory search is almost
certainly the wrong way to go about it here.
FWIW, many people just use std::map, which has a similar interface,
the benefit of sorting the elements, is standardised and portable
(just #include <map>), and is unlikely to have a noticeable
performance difference unless you're inserting tens of thousands or
more elements for frequent lookup or the elements are difficult to
compare. Basically, map does a binary lookup which typically requires
approximately log2(N) element comparisons, or 10 for a thousand
elements, 20 for a million....
The advantage of std::map is that it has been in the standard
from the very beginning, and so is standard. The various
pre-standard implementations of hash_map varied somewhat, which
created no end of portability problems. In the near future, of
course, there's std::unordered_map. But I don't think you can
count on it yet.
Note too that std::map guarantees O(n ln n). unordered_set will
be *typically* O(n), but only if you have a good hashing
function on the key. And good hashing functions are not
necessarily trivial to come by.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
.
|
|
|
| User: "BobR" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 12:41:24 PM |
|
|
James Kanze <james.kanze@gmail.com> wrote in message...
/* """ quote
On Aug 2, 7:25 am, wrote:
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
Whatever the documentation for your system tells you. The
latest draft says <unordered_set>, but this is fairly recent,
and it's likely that your implementation still uses something
pre-standard. Which it *should* document.
If you want to be a programmer, you should at least know how to do a
recursive directory search for filenames including *hash*. Really,
kids these days.... ;-P
Given that the correct name is unordered_set, searching for a
file whose name includes *hash* isn't going to help. More
generally, of course, recursive directory search is almost
certainly the wrong way to go about it here.
""" */
On an older implementation[1], it can help sometimes. I have no
'unordered_set', but, I do have:
....\Dev-Cpp\include\c++\3.3.1\backward\hash_map.h
.... so, if I wanted(?) to use it, I'd do:
#include <backward/hash_map.h>
// TODO: NOTE: OLD header.
// Update to <unordered_set> on next upgrade.
[1] - like that one poor guy whos boss would not upgrade from vc6.
--
Bob R
POVrookie
.
|
|
|
|
| User: "" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
05 Aug 2007 06:31:24 PM |
|
|
On Aug 2, 8:36 pm, James Kanze <james.ka...@gmail.com> wrote:
Still, the STL version is worse:
std::map< X, int >::const_iterator it = hm1.find( key ) ;
int a = it == hm1.end() ? 42 : *hm1 ;
The real problem in reading a map (or a hashmap) is how to
handle missing values. Sometimes, an exception is appropriate,
but it's not a good general solution. So you need something out
of band.
Yeah - that is ugly too :-(. But trivial wrapper functions can clean
up usage for these simple cases, and at least it discourages
inefficiency as people are more aware of their ability to use the
iterators for further operations.
If you want to be a programmer, you should at least know how to do a
recursive directory search for filenames including *hash*. Really,
kids these days.... ;-P
Given that the correct name is unordered_set, searching for a
file whose name includes *hash* isn't going to help. More
generally, of course, recursive directory search is almost
certainly the wrong way to go about it here.
As you said above "it's likely that your implementation still uses
something
pre-standard". Because it's non standard, many implementations put
the hash_map header in some strange subdirectory of their "include"
directory. Recursive find / ls -R / dir /s whatever is typically an
effective and quick way to find the header files. Try it for your
compiler and let us know if it doesn't work for you...
Note too that std::map guarantees O(n ln n). unordered_set will
be *typically* O(n), but only if you have a good hashing
function on the key. And good hashing functions are not
necessarily trivial to come by.
This seems bizarre to me. Unordered_set should typically be O(1), as
the insert/search/delete operations are only dependent on the
collisions in the hash bucket (which should typically be 1), and
completely independent of the number of elements in the table ("n").
map "typically" will be ln n for these operations, though after insert
and/or delete it may take extra time to rebalance the tree. James,
how do you arrive at O(n ln n)?
One hint for making good hash functions: try to have it so that if one
bit varies in the value being hashed, about half the bits vary in the
hash value. This minimises collisions even for nearly-identical
values. One simple and reliable way to do this is to use parts of the
hash value as keys into random data.
Cheers,
Tony
.
|
|
|
| User: "James Kanze" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
06 Aug 2007 03:58:35 AM |
|
|
On Aug 6, 1:31 am, wrote:
On Aug 2, 8:36 pm, James Kanze <james.ka...@gmail.com> wrote:
Still, the STL version is worse:
std::map< X, int >::const_iterator it =3D hm1.find( key ) ;
int a =3D it =3D=3D hm1.end() ? 42 : *hm1 ;
The real problem in reading a map (or a hashmap) is how to
handle missing values. Sometimes, an exception is appropriate,
but it's not a good general solution. So you need something out
of band.
Yeah - that is ugly too :-(.
I don't particularly like the interface of any of the standard
containers; if nothing else, push_back() is a horrible name for
append(). In this case, however, there is no right solution:
When I first started using C++, I wrote a hash map based on AWK,
where [] also automatically inserts (which makes a lot of sense
in AWK). After a number of years, I found that I was
systematically checking before calling the [], because I didn't
want automatic insertion. So, on porting the library to a new
client, I modified it to treat a missing entry as an error. As
you might guess, the first time I used the new version, I found
that I had to check for the error, and insert if it occured.
IMHO, the real solution with regards to std::map is to forget
about [] (most of the time, anyway), and write higher level
functions with whatever semantics corresponds to what you need
for the particular application: insert, return a pointer which
can be NULL, raise an exception, return a default value, etc.
But trivial wrapper functions can clean
up usage for these simple cases, and at least it discourages
inefficiency as people are more aware of their ability to use the
iterators for further operations.
If you want to be a programmer, you should at least know how to do a
recursive directory search for filenames including *hash*. Really,
kids these days.... ;-P
Given that the correct name is unordered_set, searching for a
file whose name includes *hash* isn't going to help. More
generally, of course, recursive directory search is almost
certainly the wrong way to go about it here.
As you said above "it's likely that your implementation still uses
something
pre-standard". Because it's non standard, many implementations put
the hash_map header in some strange subdirectory of their "include"
directory. Recursive find / ls -R / dir /s whatever is typically an
effective and quick way to find the header files. Try it for your
compiler and let us know if it doesn't work for you...
Because it's non standard, all of the implementations implement
something slightly different as well. So just finding the
header is not enough. You have to find the documentation, in
order to know how to use it. And the documentation should tell
you what you need to include. If you need to use find or "ls
-R", then the extension isn't adequately documented to risk
using.
Note too that std::map guarantees O(n ln n). unordered_set will
be *typically* O(n), but only if you have a good hashing
function on the key. And good hashing functions are not
necessarily trivial to come by.
This seems bizarre to me. Unordered_set should typically be O(1), as
the insert/search/delete operations are only dependent on the
collisions in the hash bucket (which should typically be 1), and
completely independent of the number of elements in the table ("n").
map "typically" will be ln n for these operations, though after insert
and/or delete it may take extra time to rebalance the tree. James,
how do you arrive at O(n ln n)?
By mistyping:-). I meant O(ln n), obviously. std::map is
guaranteed O(ln n) (where complexity is measured in terms of
number of comparaisons---if the allocator is O(n) over the
number of nodes allocated, then you could end up with O(n ln n)
total anyway).
One hint for making good hash functions: try to have it so that if one
bit varies in the value being hashed, about half the bits vary in the
hash value.
I wouldn't recommend it for double. Having +0.0 and -0.0 hash
to different values is a NOT a good idea. I wouldn't recommend
it for an unordered_set, either.
This minimises collisions even for nearly-identical
values. One simple and reliable way to do this is to use parts of the
hash value as keys into random data.
You're thinking of the Pearson algorithm, from the CACM, June,
1990, I think. FWIW, there's a somewhat old article at my site
(http://kanze.james.neuf.fr/code/Docs/html/Hashcode.html), with
the results of some measurements I did a while back. I only
considered hashing of strings, where every bit is significant,
as is order, which makes things easier. I've done some
additional tests since then (present in the code for the
benchmark at the site, but not in the document). All in all, I
found that "h[i]=3D127*h[i-1]+c[i]" seems to result in the fastest
tables for a wide variety of data sets; FNV hashing or CRC
actually do better in terms of distribution, but only very
marginally, and cost more to calculate. (This obviously depends
on the machine. My timings were done on a Sparc, which doesn't
have hardware multiply, so the multiplication by 127---a shift
and a subtraction---is significantly faster than that required
in FNV.) Replacing the 127 by 31 or 33---the first is used by
Java and g++---usually does just as well, but do significantly
poorer for some particular very "dense" data sets. (The "dense"
data set I tested consisted of 8836 two character strings. Not
that dense, when you think about it, since there are a total of
65536 possible two character strings.)
The hashing algorithms I tested can easily be modified for other
string-like structures. The problem is to adapt them (or
anything else) to structures where different bit patterns can
compare equal, such as double or an iteration over an
unordered_set.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34
.
|
|
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 03:01:58 PM |
|
|
Thank you guys for all the suggestions and critisisms.
I am not the kind of persons who are reluctant to read "fucking
manual".
I never asked such stupid questions when coding in Java, since there
is the awesome "Java API speicification" available there.
I think my problem is I am not familiar with the manuals of C++.
Actually I posted the orignial post kinda because I got confused when
looking at the MSDN.
I did not know that hash_map is not in stadard until you guys told me
so.
When I searched "hash map" in msdn, it listed:
hash_map> (C++ Std Lib)
Defines the container template classes hash_map and hash_multimap and
their supporting templates. In Visual C++ .NET 2003, members of the
<hash_map> and <hash_set> header files are no longer in the ...
http://msdn2.microsoft.com/en-us/library/6x7w9f6z(vs.71).aspx
hash_map Class (Standard C++ Library)
Stores and retrieves data quickly from a collection in which each
element is a pair that has a sort key whose value is unique and an
associated data value.
http://msdn2.microsoft.com/en-us/library/0d462wfh(VS.80).aspx
I thought this second entry is in the "Standard C++ Library", which is
"standard".
The confusion about which to include, <hash_map> or <hash_map.h>, is
also from MSDN. The manual in MSDN told me "Header: <hash_map>" and
also gave an example code which #include <hash_map>.
(see http://msdn2.microsoft.com/en-us/library/8zz3703d(VS.80).aspx)
Now I resolved the problem by using map as suggested by Tony. Thanks!
.
|
|
|
|
|
|
| User: "Barry" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in thehash map? |
02 Aug 2007 12:02:14 AM |
|
|
xz wrote:
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
Thanks.
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
hash_map is not in standard, still extension(now is in tr1, unordered_map)
#include <hash_map> or <hash_map.h> is implementation defined (as it's
not standard)
moreover, hash_map is in namespace std or not is implementation defined
.
|
|
|
| User: "xz" |
|
| Title: Re: I cannot use the hash_map::operator[] to read the value in the hash map? |
02 Aug 2007 12:07:35 AM |
|
|
On Aug 2, 12:02 am, Barry <dh...@126.com> wrote:
xz wrote:
On Aug 1, 10:58 pm, Barry <dh...@126.com> wrote:
xz wrote:
From the reference of MSDN about hash map:
operator[] Inserts an element into a hash_map with a specified
key value.
And such example is given:
hash_map <int, int> hm1;
hm1[ 2 ] = 40;
like km1.put(2, 40); in Java
However, there is no example like the following:
int a = hm1[2];
like int a = (int) hm1.get(2); in Java
Is the line above correct at all?
If not, how to implement the function to read the value corresponding
to key 2 stored in the hash map?
What I am looking for is just like the get() method in HashMap of Java.
Thanks.
And should I include <hash_map> or <hash_map.h> ?
I thought it should be
#include<hash_map>
but turns out:
error: hash_map: No such file or directory
hash_map is not in standard, still extension(now is in tr1, unordered_map)
#include <hash_map> or <hash_map.h> is implementation defined (as it's
not standard)
moreover, hash_map is in namespace std or not is implementation defined
The weird thing is that if I
#include<hash_map.h>
I got
In file included from /usr/lib/gcc/x86_64-linux-gnu/4.1.2/../../../../
include/c++/4.1.2/backward/hash_map.h:59,
from Bond.h:1,
from Bond.cpp:3:
/usr/lib/gcc/x86_64-linux-gnu/4.1.2/../../../../include/c++/4.1.2/
backward/backward_warning.h:32:2: warning: #warning This file includes
at least one deprecated or antiquated header. Please consider using
one of the 32 headers found in section 17.4.1.2 of the C++ standard.
Examples include substituting the <X> header for the <X.h> header for C
++ includes, or <iostream> instead of the deprecated header
<iostream.h>. To disable this warning use -Wno-deprecated.
However, if I
#include<hash_map>
I got
error: hash_map: No such file or directory
What should I do to use hash map?
I think hash map is so basic data structure, why is it such a headache
to use this famous HASH MAP?
In java, life is simple......
.
|
|
|
|
|
|
|
|
Related Articles |
|
|
