Hashtables

[ltcmelo]

I don't think it's based on a hash table, but an STL map serves the same purpose.

You're right, they're not based on hash tables, but on trees. Usually, the implementations of std::map are actually red-black trees.

Regarding the purpose of them, there're a couple of differences. As Lindley has already said, most of them come from the fact that trees provide you an ordering mechanism while hash tables don't. On the other hand, good implementations of hash tables provide you amortized constant time for accessing elements (assuming an efficient key and a balanced table).