Map - C P P

Theory

• Hashmaps
  • To store key-value pair
  • Every key will have a unique value
  • Implementation
    • Linked List, BST => Takes higher Time complexity
    • Hash Table => Using Array & Hash Function
• Types
  • Ordered Map
    • Time Complexity = O(logn)
    • Stored in sorted order according to key
    • Not stored in continuous manner
    • Implemented using Red-Black tree
    • #include <map> => Header to include
      • map<dataType1, dataType2> variable; => Initialization of Map
  • Unordered Map
    • Implemented using Hash Table
    • Time Complexity
      • Average Case = O(1)
      • Worst Case = O(L)
        • L is length of word
    • Not sorted while stored
    • Cannot use Complex data structures likes vectors, pairs because inbuilt hash function for these are not defined
    • #include <unordered_map> => Header to include
      • unordered_map<dataType1, dataType2> variable; => Initialization of Unordered Map
  • Multimap
    • Does not contains unique keys
    • Implemented using Red-Black tree
    • multimap <int, int> var => Same as Map but can contain duplicate keys
• Bucket Array
  • Array in which you store your values of the pair
• Hash Function
  • Hash Code
    • Conversion of the key to integer for mapping
    • Uniform distribution of mapping for less collision
    • Identity Function
      • Gives output same as input
  • Compression Function
    • Bring in range the integer obtained from hash code
• Collision
  • After applying Hash function, if we get same value
  • Collision Handling
    • Separate Chaining/Open Hashing
      • Create chain of values at same key using linked list
    • Open Addressing/Closed Hashing
      • Using a second argument called probe number, h(n) is the hash function value
      • H_i(n) = h(n) + F_i(n)
      • Types
        • Linear probing => H_i(n) = h(n) + i
        • Quadratic probing => H_i(n) = h(n) + i²
        • Double hashing => H_i(n) = h1(n) + i*h2(n)
• Load Factor = Number of entries in map (n)/ Number of boxs available (b)
  • Ensure it is less than 0.7
• Rehashing
  • When bucket size is increased

STL Commands

• Insert value with key
  • variable[key] = value
  • variable.insert({key, value}) => Inserts element in the map
  • variable.insert(make_pair(key, value))
• Find
  • variable[key] => Returns value of that key, If key not present then creates an entry with that key and value 0 and Returns 0
  • variable.at(key) => Returns value of that key, Returns error if key not present
• variable.size() => Returns size
• variable.count(key) => Returns 1 if element is present, 0 if not present
• variable.erase(key) => Deletes the given key value pair
• variable.clear()
• For Loop

      for(auto var1: variable) {
          cout << var1.first << " " << var1.second << endl;
      }
  

• map<int, int> :: iterator it; => Declare an iterator
  • auto it = variable.find(value) => Returns iterator to that element
  • variable.begin() => Returns iterator pointing to the first element
  • variable.end() => Returns iterator pointing to element next to the last element