0

The hashtable and map is hashtable is implemented as a hash function but map is implemented as a tree.

My question is, in what situation, hashtable can not be used but a map is a must?

skydoor
  • 25,218
  • 52
  • 147
  • 201
  • Potential duplicate: http://stackoverflow.com/questions/2196995/is-there-any-advantage-of-using-map-over-unordered-map-in-case-of-trivial-keys – Manuel Feb 13 '10 at 18:21

6 Answers6

5

There are a number of potential reasons.

  • When it is not possible or at least not practical to provide a sensible hashing function for your keys.
  • When the ordering specified by std::map is necessary or desirable.
  • When you only have access to the standard library and are limited as to what other libraries you can use.
CB Bailey
  • 755,051
  • 104
  • 632
  • 656
2

One motivation for choosing to use a map over a hashtable is the constraints which each one places on the key type used in the template instantiation. As described in the documentation for hash_map in the SGI implementation of STL, an instantiation hash_map requires provision of a functor which hashes K. The STL includes a functor, std::hash, which does this, but it is only implemented for a limited set of types T.

Instantiation of std::map on the other hand only requires a functor which compares objects of type K to generate a weak ordering. The standard functor std::less will work for any T which defines an operator<.

This means that, for many user-defined types, adding the support necessary to use the type as a key in a std::map is much less than that required to use it in a std::hash_map.

Aside from the question of overhead,

  1. Only std::map, not std::hash_map, guarantees that the keys will be ordered, so if this is a requirement, use std::map
  2. hash_map is not part of the standard, so while some STL implementations include it, this is not true of all implementations. Using hash_map therefore has potential impact on the portability of your program.
Gareth Stockwell
  • 3,112
  • 18
  • 23
  • hash_map will be included in C++0x as std::unordered_map – Matthew Flaschen Feb 13 '10 at 18:26
  • @gareth - std::unordered_map is already widely available (GCC/VS08) as part of TR1. Also, generating hash keys for custom types is trivial with the Boost.Hash library, which should be standardized someday (maybe in TR2?) – Manuel Feb 13 '10 at 18:39
2

The runtime characteristics are different:

A tree-based map always has a runtime (worst case, average case) in the order of O(log n), i.e. the height of the (balanced) binary search tree.

Hash maps, on the other hand, have a much more complicated runtime behaviour. But in the usual case, a hash table has an expected runtime of O(1), i.e. constant overhead.

In general, the worst case is O(n), which sounds bad. However, it can be shown that for a good choice of parameters, this worst case gets so rare as to not play a role in practice. “Rare” here means really rare, as in winning the lottery ten times in a row and then being killed by a comet. In practice, a bad choice of parameters (hashing technique, load factor …) can raise this probability considerably.

Konrad Rudolph
  • 530,221
  • 131
  • 937
  • 1,214
1

When you depends on that the keys are sorted.

kennytm
  • 510,854
  • 105
  • 1,084
  • 1,005
1

I'm going to answer with regard to std::unordered_map (hashtable) and std::map (tree). Note that neither of these actually specify implementation mechanisms. Basically, you use map when you need to access the keys in sorted order, and unordered_map otherwise.

Matthew Flaschen
  • 278,309
  • 50
  • 514
  • 539
1

If you need to find the 'next' item in the data structure, a hashtable cannot be used because it doesn't keep items in a traversable order.

hodgesmr
  • 2,765
  • 7
  • 30
  • 41