Hash Maps

Updated Nov 16, 2026 · 5 min read
On this page

    The first idea for many problems is a loop inside a loop: for every element, search the rest for something. That's O(n²), and with 10⁵ elements it is too slow. A hash map fixes this by remembering what you have already seen, so "search the rest" becomes a single O(1) lookup. It is the most common way to turn a nested loop into one pass.

    How it works

    Key → hash → bucket

    Each key is hashed to a bucket number; two keys that land in the same bucket share a short chain.
    Each key is hashed to a bucket number; two keys that land in the same bucket share a short chain.

    A hash map keeps an array of buckets. To store a key, it runs the key through a hash function, which turns it into a number, and uses that number (modulo the array size) to pick a bucket. Looking a key up repeats the same steps, so it goes straight to the right bucket instead of scanning everything.

    Two different keys can land in the same bucket. This is a collision, and there are two common fixes:

    • Chaining: each bucket holds a small list, and colliding keys share it. Java's HashMap works this way.
    • Open addressing: on a collision, probe the next free slot in the array. Python's dict works this way.

    Resizing keeps it fast

    When the map gets too full it doubles its bucket array and re-inserts every key; the rare O(n) resize keeps inserts O(1) on average.
    When the map gets too full it doubles its bucket array and re-inserts every key; the rare O(n) resize keeps inserts O(1) on average.

    When the map gets too full (the load factor, keys divided by buckets, passes a threshold, often around 0.75), it allocates a bigger array and moves every key. That single resize is slow, but it happens rarely enough that inserts stay O(1) on average. This is called amortized constant time.

    A hash set is the same structure with keys only and no values. Use it when you only need "have I seen this?".

    Operations and costs

    OperationAverageWorst case
    Insert or updateO(1)O(n)
    Look up a keyO(1)O(n)
    Delete a keyO(1)O(n)
    Iterate over all entriesO(n)O(n)

    The worst case happens when many keys collide into one bucket. With a decent hash function it is rare, and in interviews you can state "O(1) average" and move on. The real cost is memory: O(n) extra space for n keys.

    When to reach for it

    Listen for these questions inside the problem:

    • "Have I seen this before?" Duplicates, first unique character, cycle detection by remembering visited states.
    • "How many of each?" Counting frequencies, anagram checks, top-K by frequency.
    • "Is the partner I need already here?" Complement lookups, as in Two Sum.
    • "Group these by something." Grouping anagrams by their sorted letters, grouping events by user.
    • "Remember an index or a position." Longest substring without repeats stores the last index of each character; subarray sums store the first index of each running total.

    Example

    Pattern 1: complement lookup

    Given a list of numbers and a target, return the indices of two numbers that add up to the target. The brute force checks every pair, which is O(n²). With a hash map, walk the list once, and for each number ask whether its complement (target − x) was already seen.

    At each step, look up the partner first, then store the current number with its index.
    At each step, look up the partner first, then store the current number with its index.
    def two_sum(nums, target):
        seen = {}  # value -> index
        for i, x in enumerate(nums):
            need = target - x
            if need in seen:
                return [seen[need], i]
            seen[x] = i
        return []
    int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(); // value -> index
        for (int i = 0; i < nums.length; i++) {
            int need = target - nums[i];
            if (seen.containsKey(need)) {
                return new int[] { seen.get(need), i };
            }
            seen.put(nums[i], i);
        }
        return new int[0];
    }
    vector<int> twoSum(const vector<int>& nums, int target) {
        unordered_map<int, int> seen; // value -> index
        for (int i = 0; i < (int)nums.size(); i++) {
            int need = target - nums[i];
            auto it = seen.find(need);
            if (it != seen.end()) return {it->second, i};
            seen[nums[i]] = i;
        }
        return {};
    }
    func twoSum(nums []int, target int) []int {
        seen := make(map[int]int) // value -> index
        for i, x := range nums {
            if j, ok := seen[target-x]; ok {
                return []int{j, i}
            }
            seen[x] = i
        }
        return nil
    }

    Time: O(n), one pass. Space: O(n) for the map.

    Note the order: check for the complement before storing the current number. That way a number never pairs with itself, and [3, 3] with target 6 still works.

    Pattern 2: counting

    Check whether two strings are anagrams: count each character in the first string, subtract counts for the second, and every count must end at zero.

    from collections import Counter
    
    def is_anagram(s, t):
        return len(s) == len(t) and Counter(s) == Counter(t)
    boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) return false;
        Map<Character, Integer> count = new HashMap<>();
        for (char c : s.toCharArray()) count.merge(c, 1, Integer::sum);
        for (char c : t.toCharArray()) {
            if (count.merge(c, -1, Integer::sum) < 0) return false;
        }
        return true;
    }
    bool isAnagram(const string& s, const string& t) {
        if (s.size() != t.size()) return false;
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        for (char c : t) {
            if (--count[c] < 0) return false;
        }
        return true;
    }
    func isAnagram(s, t string) bool {
        if len(s) != len(t) {
            return false
        }
        count := make(map[rune]int)
        for _, c := range s {
            count[c]++
        }
        for _, c := range t {
            count[c]--
            if count[c] < 0 {
                return false
            }
        }
        return true
    }

    Time: O(n). Space: O(k), where k is the number of distinct characters. If the input is only lowercase letters, a fixed array of 26 counters does the same job with less overhead, and it's a nice follow-up to mention.

    Common mistakes

    • Using mutable keys. A Python list can't be a key; use a tuple. In Java, changing an object after it is used as a key breaks lookups.
    • Assuming order. Python's dict keeps insertion order, but Java's HashMap, C++'s unordered_map and Go's map do not. Use a sorted map or sort the keys when order matters.
    • Custom objects as keys. In Java you must override both equals and hashCode; in C++ you must supply a hash.
    • Storing before checking. In complement problems, storing the current element first lets it pair with itself.
    • Forgetting memory. O(1) time costs O(n) space. If the interviewer asks for O(1) space, think sorting plus two pointers instead.

    Say this in the interview

    • "The brute force is O(n²) because for each element I search the rest. If I store what I've seen in a hash map, each lookup is O(1) on average, so the whole thing is O(n) time and O(n) space."
    • "Worst-case lookups are O(n) if everything collides, but with a standard library hash map that's not a practical concern."
    • "Since the keys are only lowercase letters, an array of 26 counts would work too and avoids hashing."

    Used in