in C++ STL, there are two map, map and hashmap. Anyone know the main difference of them?
map uses a red-black tree as the data structure, so the elements you put in there are sorted, and insert/delete is O(log(n)). The elements need to implement at least operator<
.
hashmap uses a hash, so elements are unsorted, insert/delete is O(1). Elements need to implement at least operator==
and you need a hash function.
hash_map uses a hash table. This is "constant" time in theory. Most implementations use a "collision" hash table. What happens in reality is:
The theory is that if you have a big enough table, the operations are constant time, i.e. it does not depend on the number of actual elements you have. In practice, of course, the more elements you have the more collisions occur.
std::map uses a binary tree. There is no need to define a hash function for an object, just strictly ordered comparison. On insertion it recurses down the tree to find the insertion point (and whether there are any duplicates) and adds the node, and may need to rebalance the tree so the depth of leaves is never more than 1 apart. Rebalancing time is relative to the depth of the tree too so all these operations are O(log N) where N is the number of elements.
The advantages of hash is the complexity The advantages of the tree is:
One other issue with std::map
is that it uses a single strictly-ordered comparison function whilst a "compare" function that returned -1, 0 or 1 would be a lot more efficient, particularly with the most commonly used key type, std::string, which already has this function implemented (it is char_traits::compare
). (This inefficiency is based on the premise that to check that x==y
, you check x<y
and y<x
so you do two comparisons. You would do this just once per lookup).
map
is a red-black tree, O(log(n))
access time. hash_map
(which is not standard, however unordered_map
will become standard) uses (conceptually) a hash of the key as an index in an array of linked lists, and therefore has a best-case access time of O(1)
and a worst case of O(n)
.
See http://en.wikipedia.org/wiki/Red-black_tree
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With