Lecture 78: Hashmaps in C++
Class Notes
CodeHelp Placement Series
1. Introduction to Maps
Maps are highly used data structures in development and competitive programming due to
their incredible efficiency in operations like insertion, deletion, and searching.
• Key Concept: A Map stores data in Key-Value pairs.
• Constraint: Each key in a map must be unique. A single key points to exactly one value.
2. Why do we need Maps?
• The Problem: If you want to find the maximum occurring character in a string, you can
simply use an array of size 26 to map ’a’ to index 0, ’b’ to 1, etc. However, if you are asked
to find the maximum occurring word in a string (e.g., mapping a word like ”Babbar” to a
frequency count), array mapping is not possible because array indices must be integers
(0, 1, 2...).
• The Solution: Maps allow you to map any data type (Key) to another data type (Value),
such as mapping a string to an int. You can even use custom objects, pairs, or linked list
nodes as keys.
3. map vs unordered_map in C++ STL
• map (Ordered Map):
– Implemented using a Self-Balancing Binary Search Tree (BST) (like Red-Black Trees).
– Keys are stored in a sorted, definite order.
– Time Complexity: O(log N ) for insertion, deletion, and searching.
• unordered_map:
– Implemented using Hash Tables.
– Keys are stored in a random, unordered sequence.
– Time Complexity: O(1) average time for insertion, deletion, and searching.
1
4. Basic Operations & Syntax
To use maps, you must include the <map> or <unordered_map> headers.
#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;
unordered_map<string, int> m; // Creation
Insertion
There are multiple ways to insert a key-value pair:
1. [Link](make_pair("apple", 2));
2. [Link]({"babbar", 3});
3. m["mera"] = 1; (If ”mera” does not exist, it creates a new entry with value 1. If it exists, it
updates the value).
Searching / Accessing
• Using m["key"]: Will return the value. Warning: If the key does not exist, m["key"] will
create a new entry initialized to 0 and return 0.
• Using [Link]("key"): Will return the value. If the key doesn’t exist, it throws an out_of_range
exception.
Other Utilities
• Size: [Link]() returns the number of entries.
• Count: [Link]("key") returns 1 if the key is present and 0 if it is not.
• Erase: [Link]("key") removes the entry.
5. Iterating Over a Map
Maps can be iterated over using a for-each loop or Iterators.
Using auto loop:
for (auto i : m) {
// [Link] is Key, [Link] is Value
cout << [Link] << " " << [Link] << endl;
}
Using Iterators:
unordered_map<string, int>::iterator it = [Link]();
while (it != [Link]()) {
cout << it->first << " " << it->second << endl;
it++;
}
2
6. Hash Tables (Under the Hood of unordered_map)
Hash tables use an internal array to achieve O(1) mapping. It relies on a Hash Function to
figure out which array index a particular key should be stored in.
Hash Function Components:
1. Hash Code: Converts the key (like a string ”babbar”) into an integer. It can be an identity
function, a sum of ASCII values, etc. The main goal of the hash code is to ensure uniform
distribution to minimize collisions.
2. Compression Function: Compresses the integer provided by the Hash Code to fit within
the bounds of the internal array’s size (usually achieved using the Modulo % operator).
7. Collision Handling
A collision occurs when two different keys generate the same compressed hash index. There
are two main ways to handle this:
A. Open Hashing (Separate Chaining)
• Instead of storing values directly in the array, the array stores pointers to the head of a
Linked List.
• If a collision occurs at a specific index, the new element is simply appended to the linked
list at that index.
B. Closed Addressing (Open Addressing)
• Elements are stored directly in the array itself. If an index is already occupied, the algo-
rithm searches for the ”next available” index.
• Linear Probing: It linearly checks indices. If index i is full, it checks (i + 1), (i + 2), etc.
• Quadratic Probing: Instead of linear increments, it checks indices quadratically: (i + 12 ),
(i + 22 ), (i + 32 ).
8. Complexity Analysis & Load Factor
For Hashmaps to maintain O(1) complexity, a rule of thumb is enforced using the Load Factor.
• Let n = total number of entries, and b = number of available boxes (array size).
n
• Load Factor: b
n
• The system ensures that b < 0.7 (meaning the table shouldn’t be more than 70% full).
3
Rehashing:
If n grows too large and the load factor exceeds the threshold (e.g., > 0.7), the system will
automatically perform Rehashing.
• It creates a new array double the size of the original.
• It recalculates the hash indices for all existing elements and places them into the new array
to re-ensure O(1) performance.