Hash Map vs STL Map

A hash map or unordered_map stores values in terms of hash. It converts the key into a hash value and stores the value linked to this hash value. Whenever we look for a particular key, it converts this search key into its hash value and then checks if the hash value is present in the hash map. If it is, it returns the corresponding value tied to this key/hash value else none. Therefore, it takes O(1) in insertion and finding a key.

A map stores data in ordered (sorted form). It overwrites the new value of a key if it already exists. This is good for smaller operations and sorted data if needed. It is in the form of a balanced binary tree and takes O(logn) to search and insert.

Hash map stored multiple value to same key in the form of a linked list. Collisions also occur sometimes when the hash function return the same hash value for 2 different keys. It is therefore a good idea to store both key and value in the position pointed to by the hash value. The linked list element will hold both key and value. On becoming huge it resizes it accordingly.. Although this leads to collision very frequently. A good hash function can avoid/reduce collisions.

However, Hash map is still good for huge amounts of data. This is because it is faster to search for a key in hash map for large data than it is in a map where it traverses through all of it in order to search.