Hi, and welcome! Today, we'll explore HashMaps, a data structure that organizes data as key-value pairs, much like a treasure box with unique labels for each compartment.
Imagine dozens of toys in a box. If each toy had a unique label (the key), you could directly select a toy (the value) using the label. No rummaging required — that's the power of HashMaps
! Today, we'll understand HashMaps
and learn how to implement them in C++.
HashMaps
are special types of data structures that utilize unique keys instead of indexes. When you know the key (toy's label), you can directly pick up the value (toy). That's how a HashMap
works!
Consider an oversized library of books. With HashMaps
(which act like the library catalog), you'll quickly locate any book using a unique number (key)!
C++ implements HashMaps
through the unordered_map
class in the standard library. They hold data in key-value pairs.
Let's create an unordered_map
, functioning as a catalog for a library:
C++1#include <iostream> 2#include <unordered_map> 3#include <string> 4 5int main() { 6 // Creating a catalog for the library using unordered_map 7 std::unordered_map<std::string, std::string> library_catalog = { 8 {"book1", "A Tale of Two Cities"}, 9 {"book2", "To Kill a Mockingbird"}, 10 {"book3", "1984"} 11 }; 12 13 return 0; 14}
In this unordered_map
, book1
, book2
, and book3
are keys, while the book titles serve as their respective values.
It's important to remember that the keys should be of a type that supports hashing and equality comparison (such as std::string
or primitive data types). The values can be of any type.
unordered_map
allows you to access, update, or remove elements:
Accessing Elements: You can retrieve a book's title using its key in a straightforward way: library_catalog["book1"]
would return "A Tale of Two Cities." But what happens if you try to access a key that isn't present in the unordered_map
? This would return a default-constructed value, which could be problematic.
To prevent such issues, C++ unordered_map
provides the find()
method. It fetches the iterator for a given key if it exists. If it doesn't, it returns library_catalog.end()
.
C++1// Using find() to access a book's title 2auto it = library_catalog.find("book1"); 3if (it != library_catalog.end()) 4 std::cout << it->second << std::endl; // Output: "A Tale of Two Cities" 5else 6 std::cout << "Key not found" << std::endl; 7 8// Using find() to access a nonexistent key 9auto it_nonexistent = library_catalog.find("book100"); 10if (it_nonexistent != library_catalog.end()) 11 std::cout << it_nonexistent->second << std::endl; 12else 13 std::cout << "Key not found" << std::endl; // Output: "Key not found"
Adding or Updating Elements: Whether you're adding a new book to the catalog or updating an existing book's title, you'll use the assignment operator (=
). This syntax in C++'s unordered_map
allows for both updating existing key-value pairs and establishing new ones.
If the specified key exists in the unordered_map
, the assigned value replaces the existing one. For updating a title: library_catalog["book1"] = "The Tell-Tale Heart"
.
If the key doesn't exist in the unordered_map
yet, the operation creates a new key-value pair. For adding a new book: library_catalog["book4"] = "Pride and Prejudice"
.
Removing Elements: If book1
no longer exists, you can remove it using library_catalog.erase("book1")
.
C++ unordered_map
offers several useful methods to interact with and manage your data:
Iterating over the HashMap: Loop through your unordered_map
to access each key-value pair in turn. To get both the key and the value from an unordered_map
iterator, you can use the first
and second
members of the std::pair
that the iterator points to:
C++1// Looping over the unordered_map 2for (const auto& pair : library_catalog) { 3 std::cout << pair.first << " : " << pair.second << std::endl; 4}
When run, this code prints:
Plain text1book1 : A Tale of Two Cities 2book2 : To Kill a Mockingbird 3book3 : 1984
HashMaps
(unordered_map
) are popular because they save time! Operations like adding, updating, and locating elements take average constant time, O(1)
, which means they require nearly the same amount of time regardless of the library size.
Well done! You've mastered HashMaps
, understood C++'s implementation of HashMaps
through unordered_map
, learned their operations, and grasped the concept of time complexity. Now, gear up for some practice exercises to reinforce your learning. Happy coding!