Hash Maps data structure

Hash Maps

Hash maps, also known as hash tables, are a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash map uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. It is a type of unordered list that allows for fast retrieval of values based on keys. You can search through hash maps in constant time, O(1), on average, which makes them very efficient for lookups.

However, vectors are more efficient for iterating through elements, as they store elements in contiguous memory locations, even though both are O(1) for lookups, the constant for vectors is much smaller. But the advantage of hash maps is that creating a hash map is O(n) for n elements, while creating a vector is O(n log n) for n elements.

Unordered Map

std::unorderd_map is a C++ Standard Library container that implements a hash table. It allows for fast retrieval of values based on keys, similar to hash maps in other programming languages. it is stored in the header <unordered_map>.

#include <iostream>
#include <string>
#include <unordered_map>
 
int main() {
    // 1. Declare a map
    // This map will store string keys and int values
    std::unordered_map<std::string, int> student_scores;
 
    // 2. Add key-value pairs
    student_scores["Alice"] = 95;
    student_scores["Bob"] = 88;
 
    // 3. Access a value using its key
    std::cout << "Alice's score is: " << student_scores["Alice"] << std::endl; // Outputs: 95
 
    // 4. Check if a key exists
    if (student_scores.count("Charlie")) {
        std::cout << "Charlie's score is: " << student_scores["Charlie"] << std::endl;
    } else {
        std::cout << "Charlie is not in the map." << std::endl; // This will run
    }
 
    return 0;
}

Example: Two Sum Problem

Two Sum is a classic problem that can be efficiently solved using hash maps. The goal is to find two numbers in an array that add up to a specific target value.

#include <unordered_map>
#include <vector>
using namespace std;
 
class Solution {
public:
  vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hash; // Store item -> index in a hash table
    for (int i = 0; i < nums.size(); i++) {
      if (hash.count(target - nums[i])) {
        return {i, hash[target - nums[i]]}; // If target - item is already in the table then return it
      }
      hash[nums[i]] = i; // Populate hash table if the analogous item isn't in the table
    }
    return {};
  }
};