CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 8 of 8
  1. #1
    Join Date
    Apr 2006
    Posts
    9

    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?

  2. #2
    Join Date
    Sep 2005
    Location
    United States
    Posts
    799

    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.

  3. #3
    Join Date
    Apr 2006
    Posts
    9

    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.

  4. #4
    Join Date
    Sep 2005
    Location
    United States
    Posts
    799

    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.

  5. #5
    Join Date
    Apr 2010
    Posts
    1

    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

  6. #6
    Join Date
    Jul 2005
    Location
    Netherlands
    Posts
    2,042

    Re: std::map vs std:hash_map

    Quote Originally Posted by Slowmo View Post
    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

  7. #7
    Join Date
    Jun 2009
    Location
    France
    Posts
    2,513

    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.

  8. #8
    Join Date
    May 2009
    Posts
    2,413

    Re: std::map vs std:hash_map

    Quote Originally Posted by Slowmo View Post
    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
  •  





Click Here to Expand Forum to Full Width

Featured