Sign in to follow this  
thedodgeruk

hash tables vs stl map

Recommended Posts

thedodgeruk    124
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
kdmiller3    178
The STL "map" container isn't a hash table, though it achieves a similar goal (fast random access).

The "map" container:
[list][*]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)[/list]
The "hash_map" container:
[list][*]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[/list]

Share this post


Link to post
Share on other sites
frob    44962
[quote name='kdmiller3' timestamp='1302824425' post='4798598']
The STL "map" container isn't a hash table, though it achieves a similar goal (fast random access).

The "map" container:
[list][*]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)[/list]
The "hash_map" container:
[list][*]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[/list]
[/quote]
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
enunes    123
[quote name='frob' timestamp='1302885650' post='4798826']
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.
[/quote]

Theres [url="http://msdn.microsoft.com/en-us/library/bb982522.aspx"]tr1::unordered_map[/url] 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

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this