CODEWITHSUNDEEP
c++
jmasterx
jmasterx

Reputation: 54123

Advantages and Disadvantages of hashmap and tree map?

C++ by default provides a tree based map. With Boost you can get a hashmap.

What are the advantages and disadvantages of

  1. C++'s Tree Based Map and

  2. Boost's Hashmap ?

Upvotes: 4

Views: 6371

Answers (2)

Kerrek SB
Kerrek SB

Reputation: 477110

C++0x/TR1 also provides the unordered_map which is usually implemented as a hash map.

The differences are twofold:

  1. The key type. In the ordered map, the key type must obey a strict weak ordering, and entries are maintained in that order. In the unordered map, the key type must be equality-comparable and you must provide a hash function h such that h(Key) returns size_t [thanks to Steve Jessop for the clarification].

  2. Access complexity: Insert/delete/find in an ordered map is O(log n) in the map size n. In the unordered map, it is "usually" O(1), but worst-case behaviour is O(n) (e.g. if all keys map to the same hash value).

So the ordered map provides a total complexity guarantee, while the unordered map provides a (better) complexity in good cases, depending on the quality of your hash function.

The internal implementation complexity of the unordered map is greater than of the ordered map, but you can imagine that you get the better access complexity because you get fewer features, i.e. you don't get sorting for free. It's a classical trade-off.

Another point: Practically, if the weak ordering operator is expensive to compute, like for strings, the unordered map may actually be quite a bit faster, because comparisons on the hash type are very fast. On the other hand, if your key type is one with trivial hash function (like any built-in integral type) and if you don't need the ordering, consider using an unordered container.

Upvotes: 6

Jason
Jason

Reputation: 32510

Hash tables provide very fast search access and insertion/deletions of objects ... the complexity for such operations is on average O(1), meaning constant time. The main limitation for these two operations is the speed of the hashing algorithm (for some types of objects that are not POD's, these can be a bit complex and take up more time for good ones that avoid "collisions" where two different objects hash to the same value). The main penalty for a hash table is that it requires a lot of extra space.

Binary trees on the other-hand have relatively quick insertion and search times, and the complexity for deleting and object is the same as insertions. Because of the way a binary tree works, where each node has two more child-nodes, the search and access time (as well as insertions and deletions), takes O(log N) time. So binaty trees are "slower" than hash tables, but are not as complex to implement (although balanced binary search trees are more complex that unbalanced trees).

Another side-benefit of a binary search tree is that you can, by iterating though the container from the "first" element to the "last" element, get a sorted list of objects, where-as with the hash-map, that list would not be sorted. So the extra time for insertions also takes into account the face that the binary search tree is a sorted insertion. For instance, the complexity of a quicksort on a group of N items is the same complexity as building a balanced binary search tree (i.e., a red/black tree) for the same group of N items. Both operations are O(N log N).

Upvotes: 1

Related Questions