Jump to content
  • Advertisement
Sign in to follow this  
thedodgeruk

hash tables vs stl map

This topic is 2596 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

i have been looking at hash tables and the idea of them makes compleate sense, then i came across slt map container, and this to me looks the same thing .

i was wondering though if there wasa speed differnece when accessing the relevent data

Share this post


Link to post
Share on other sites
Advertisement
The STL "map" container isn't a hash table, though it achieves a similar goal (fast random access).

The "map" container:
  • is typically implemented as a red-black binary tree
  • takes O(log N) time to find or insert an element
  • requires a separate allocation per entry
  • iterator returns entries in sorted order (which may be useful)
    The "hash_map" container:
    • is implemented as a true hash table
    • takes amortized O(1) time to find or insert an element
    • stores entries in an array but requires about twice as many slots as entries for decent performance
    • iterator returns elements in arbitrary order

Share this post


Link to post
Share on other sites

The STL "map" container isn't a hash table, though it achieves a similar goal (fast random access).

The "map" container:
  • is typically implemented as a red-black binary tree
  • takes O(log N) time to find or insert an element
  • requires a separate allocation per entry
  • iterator returns entries in sorted order (which may be useful)
    The "hash_map" container:
    • is implemented as a true hash table
    • takes amortized O(1) time to find or insert an element
    • stores entries in an array but requires about twice as many slots as entries for decent performance
    • iterator returns elements in arbitrary order

Being picky:


std::map is part of the C++ standard library. As mentioned, it has performance requirements that must meet or exceed a balanced tree.

hash_map is NOT part of the c++ standard library, nor is it part of the proposed standard. It is a non-standard extension found in several implementations, and should not be in the std namespace. (The standard specifically states that non-standardized modifications to namespace std are undefined behavior). Performance requirements are not standardized, there are no requirements about a "true hash table", or specific other requirements. What you describe may be true of your hash_map, but there is no assurance about any other implementation, or that the class even exists at all.



@OP: Learning C++ means you should have known about the C++ standard library, including the containers. If you don't know about them, I suggest you go learn some books about the language, such as "Accelerated C++" by Koenig and Moo to learn more about the language generally, or if you want to focus on the standard library, "The C++ Standard Library" by Josuttis.

Share this post


Link to post
Share on other sites

Being picky:


std::map is part of the C++ standard library. As mentioned, it has performance requirements that must meet or exceed a balanced tree.

hash_map is NOT part of the c++ standard library, nor is it part of the proposed standard. It is a non-standard extension found in several implementations, and should not be in the std namespace. (The standard specifically states that non-standardized modifications to namespace std are undefined behavior). Performance requirements are not standardized, there are no requirements about a "true hash table", or specific other requirements. What you describe may be true of your hash_map, but there is no assurance about any other implementation, or that the class even exists at all.



@OP: Learning C++ means you should have known about the C++ standard library, including the containers. If you don't know about them, I suggest you go learn some books about the language, such as "Accelerated C++" by Koenig and Moo to learn more about the language generally, or if you want to focus on the standard library, "The C++ Standard Library" by Josuttis.


Theres tr1::unordered_map which, as far as I understand, is part of the proposed standard and implements a hash function to achieve O(1).
Not an expert and I don't deeply know the specification, but that's also an alternative :)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!