Sundar's Notes

Hash Maps Data Structure

2 min read

Hash Maps Data Structure

Hash maps (hash tables) implement an associative array abstract data type, mapping keys to values using a hash function. They provide O(1) average-case lookup time by computing an index into an array of buckets.

Performance Characteristics

  • Lookup: O(1) average, O(n) worst case (collisions).
  • Insertion: O(1) average.
  • Iteration: Slower than vectors due to non-contiguous memory layout; vectors benefit from cache locality even though both are O(n) for iteration.
  • Construction: O(n) for n elements inserted into a hash map, vs O(n log n) for sorting a vector.

C++ std::unordered_map

The C++ Standard Library provides std::unordered_map in <unordered_map>:

#include <iostream>
#include <string>
#include <unordered_map>
 
int main() {
    std::unordered_map<std::string, int> scores;
 
    scores["Alice"] = 95;
    scores["Bob"] = 88;
 
    std::cout << scores["Alice"] << std::endl; // 95
 
    if (scores.count("Charlie")) {
        std::cout << scores["Charlie"] << std::endl;
    } else {
        std::cout << "Not found" << std::endl;
    }
}

Key methods: count() for existence check, [] for access/insertion, find() for iterator-based lookup.

Application: Two Sum Problem

Hash maps are frequently used to reduce nested loops to single passes. The classic Two Sum problem stores each element’s value-to-index mapping as it iterates, checking if the complement exists in the map:

#include <unordered_map>
#include <vector>
using namespace std;
 
vector<int> twoSum(vector<int> &nums, int target) {
    unordered_map<int, int> hash;
    for (int i = 0; i < nums.size(); i++) {
        if (hash.count(target - nums[i])) {
            return {i, hash[target - nums[i]]};
        }
        hash[nums[i]] = i;
    }
    return {};
}

This technique also applies to frequency counting in anagram detection and sliding window problems.

Relation to Dynamic Programming

Hash maps serve as the cache storage for memoization in top-down dynamic programming. Results for computed subproblem states are stored by key and retrieved in O(1) time. See Dynamic Programming for details.

References

Graph View

Backlinks