map vs hash map in C

Question

I have a question with hash map and map in C    I understand that map is in STL  but hash map is not a standard  What s the difference between the two

User · Answer

The C   spec doesn t say exactly what algorithm you must use for the STL containers   It does  however  put certain constraints on their performance  which rules out the use of hash tables for map and other associative containers    They re most commonly implemented with red black trees    These constraints require better worst-case performance for these containers than hash tables can deliver   Many people really do want hash tables  however  so hash-based STL associative containers have been a common extension for years   Consequently  they added unordered map and such to later versions of the C   standard

User · Answer

Some of the key differences are in the complexity requirements    A map requires O log N   time for inserts and finds operations  as it s implemented as a Red-Black Tree data structure  An unordered map requires an  average  time of O 1  for inserts and finds  but is allowed to have a worst-case time of O N   This is because it s implemented using Hash Table data structure    So  usually  unordered map will be faster  but depending on the keys and the hash function you store  can become much worse

User · Answer

They are implemented in very different ways   hash map  unordered map in TR1 and Boost  use those instead  use a hash table where the key is hashed to a slot in the table and the value is stored in a list tied to that key   map is implemented as a balanced binary search tree  usually a red black tree    An unordered map should give slightly better performance for accessing known elements of the collection  but a map will have additional useful characteristics  e g  it is stored in sorted order  which allows traversal from start to finish    unordered map will be faster on insert and delete than a map

User · Answer

I don t know what gives  but  hash map takes more than 20 seconds to clear   150K unsigned integer keys and float values  I am just running and reading someone else s code   This is how it includes hash map    include  StdAfx h   include  lt hash map gt    I read this here https   bytes com topic c answers 570079-perfomance-clear-vs-swap  saying that clear   is order of O N   That to me  is very strange  but  that s the way it is

User · Answer

hash map was a common extension provided by many library implementations   That is exactly why it was renamed to unordered map when it was added to the C   standard as part of TR1   map is generally implemented with a balanced binary tree like a red-black tree  implementations vary of course    hash map and unordered map are generally implemented with hash tables   Thus the order is not maintained   unordered map insert delete query will be O 1   constant time  where map will be O log n  where n is the number of items in the data structure   So unordered map is faster  and if you don t care about the order of the items should be preferred over map   Sometimes you want to maintain order  ordered by the key  and for that map would be the choice

User · Answer

map is implemented from balanced binary search tree usually a rb tree   since all the member in balanced binary search tree is sorted so is map   hash map is implemented from hashtable Since all the member in hashtable is unsorted so the members in hash map unordered map  is not sorted   hash map is not a c    standard library  but now it renamed to unordered map you can think of it renamed  and becomes c    standard library since c  11 see this question Difference between hash map and unordered map  for more detail    Below i will give some core interface from source code of how the two type map is implemented   map   The below code is just to show that  map is just a wrapper of an balanced binary search tree  almost all it s function is just invoke the balanced binary search tree function   template  lt typename Key  typename Value  class Compare   std  less lt Key gt  gt  class map         used for rb tree to sort     typedef Key    key type          rb tree node value     typedef std  pair lt key type  value type gt  value type       typedef Compare key compare          as to map  Key is used for sort  Value used for store value     typedef rb tree lt key type  value type  key compare gt  rep type          the only member value of map  it s  rb tree      rep type t         one construct function template lt typename InputIterator gt  map InputIterator first  InputIterator last  t Compare                use rb tree to insert value just insert unique value          t insert unique first  last         insert function  just use tb tree insert unique function   and only insert unique value   rb tree insertion time is   log n  rebalance    so map s  insertion time is also   log n  rebalance  typedef typename rep type  const iterator iterator  std  pair lt iterator  bool gt  insert const value type amp  v       return t insert unique v        hash map   hash map is implemented from hashtable whose structure is somewhat like this     In the below code  i will give the main part of hashtable  and then gives hash map      used for node list template lt typename T gt  struct   hashtable node      T val        hashtable node  next      template lt typename Key  typename Value  typename HashFun gt  class hashtable      public          typedef size t   size type          typedef HashFun  hasher          typedef Value    value type          typedef Key      key type      public          typedef   hashtable node lt value type gt  node              member data is buckets array node  array          std  vector lt node  gt  buckets          size type num elements           public                 insert only unique value             std  pair lt iterator  bool gt  insert unique const value type amp  obj         Like map s only member is rb tree  the hash map s only member is hashtable  It s main code as below   template lt typename Key  typename Value  class HashFun   std  hash lt Key gt  gt  class hash map      private          typedef hashtable lt Key  Value  HashFun gt  ht              member data is hash table         ht rep       public             100 buckets by default            it may not be 100 in this just for simplify          hash map   rep 100                 like the above map s insert function just invoke rb tree unique function            hash map  insert function just invoke hashtable s unique insert function         std  pair lt iterator  bool gt  insert const Value amp  v                   return t insert unique v                    Below image shows when a hash map have 53 buckets  and insert some values  it s internal structure     The below image shows  some difference between map and hash map unordered map   the image comes from How to choose between map and unordered map

[c++] map vs. hash_map in C++

Examples related to c++

Examples related to map

Examples related to hashmap