usage of hashtable and map

Question

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?

Answer 1

When you depends on that the keys are sorted.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.