-
May 6th, 2006, 05:15 PM
#1
std::map vs std:hash_map
I did spend some time looking for this answer here, but didn't succeed so here goes.
I know that std::map uses a self-balancing tree to store key-data pairs, and hash_map as you could gess - a hash map.
What I would like to know is what are the basic differences between those two? Insert time, access time, memory usage, anything else?
I need to create a codepage converter where convention table is read from a file. There could be around 5 to 128 conventions stored in this file.
A string is read from a text file and each character is compared to a convention table. If there is a mach, character is substituted with one from the convention table.
I now use std::map<unsigned long, unsigned char> char_conv,
but maybe I must switch to hash_map?
Which of them will perform faster?
-
May 6th, 2006, 05:33 PM
#2
Re: std::map vs std:hash_map
Here are some interesting reads on std::map complexity
Link 1
Link 2
Link 3
And also for std::hash_map
Link 4
I now use std::map<unsigned long, unsigned char> char_conv,
but maybe I must switch to hash_map?
This depends on your data.
A Hash Map (or other data structure using a hashing algorithm) is extremely quick in terms of access time. It is O(1) constant time regardless of input size; basically instantaneous.
There is a flip side to this however. A Hash Map does not sort the data in any way. So if you need to keep your data in some kind of order, you will have to stick with std::map, which has O( log n ) access time, or some other data structure.
Last edited by dcjr84; May 7th, 2006 at 02:24 PM.
-
May 7th, 2006, 06:16 AM
#3
Re: std::map vs std:hash_map
Ok, from this I understand that hash_map will be better in my case because data is loaded only once at the beginning of the program, and there is absolutely no need to sort its keys.
-
May 7th, 2006, 06:12 PM
#4
Re: std::map vs std:hash_map
If you are only interested in storing and retrieving data as fast as
possible, and ordering is not important, then yes I would agree.
-
April 18th, 2010, 06:33 AM
#5
Re: std::map vs std:hash_map
Hi,
Map:
1. STL map is an associative array where keys are stored in sorted order using balanced trees. While hash_map is a hashed associated container, where keys are not stored in an ordered way. Key, value pair is stored using a hashed function.
2. Insertion and lookup takes Ologn time in map, Also performance would degrade as the key size increases. Mainly balance operations on large key ranges would kill performance. while lookup is very efficient O(1) in hash_map.
3. Map is useful where you want to store keys in sorted order, hash_map is used where keys order is not important and lookup is very efficient.
4. One more difference is map has the important property that inserting a new element into a map does not invalidate iterators that point to existing elements. Erasing an element from a map also does not invalidate any iterators.
Performance would mostly be o(lgn) due to the implementation of a balanced tree.
For Map custom objects you would need at the minimum the following operators to store data in a map "<" ">" "==" and of course the other stuff for deep copy.
Listen voice notes on stl map vs hash_map at http://listenvoice.com/listenVoiceNote.aspx?id=36
-
April 18th, 2010, 07:59 AM
#6
Re: std::map vs std:hash_map
Originally Posted by Slowmo
Ok, from this I understand that hash_map will be better in my case because data is loaded only once at the beginning of the program, and there is absolutely no need to sort its keys.
No, you need to measure to be able to say which is faster.
What a lot of people seem to forget is that random access in an unordered map is constant in terms of the number of elements stored in the container. That does not mean it is fast, and certainly not instant. For every lookup, a hash has to be made of the element you are looking up. It really depends on the data type you are using as a key, whether that will be fast or not.
Given that you know that you will maximally store 128 elements in your container, asymptotic performance measures are not so important as real measurements. You should make a test application where you can test performance of a std::vector (possibly sorted, so you can use std::binary_search), a std::map and a hash table - e.g. std::tr1::unordered_map if your compiler supports it.
Cheers, D Drmmr
Please put [code][/code] tags around your code to preserve indentation and make it more readable.
As long as man ascribes to himself what is merely a posibility, he will not work for the attainment of it. - P. D. Ouspensky
-
April 18th, 2010, 08:33 AM
#7
Re: std::map vs std:hash_map
One of the biggest differences that rarely get mentioned is that:
A map sorts it's elements, and requires operator< to determine equivalence.
A hashmap does not sort its elements, and uses operator== to equality.
-
April 19th, 2010, 09:48 AM
#8
Re: std::map vs std:hash_map
Originally Posted by Slowmo
each character is compared to a convention table. If there is a mach, character is substituted with one from the convention table.
The fastest data structure may be an ordinary array.
The characters are used as indexes to address the array. If an array position is empty no conversion takes place. If an array position holds a character it's used as replacement.
Say the characters are encoded as bytes, then the size of the conversion array is just 256 (2^8).
Last edited by nuzzle; April 19th, 2010 at 10:34 AM.
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|