Hash maps in your language

Every language ships one

You will rarely write a hash table yourself, but you will use one every day. Here is what the main languages provide:

The details differ, but each one is the structure you built in this module: a hash function, a way to turn the hash into a slot, a collision strategy and a resize policy. Knowing which strategy your language uses tells you what to expect when tables get large or keys get unlucky.

What a key has to provide

A hash map relies on two operations for every key type: a hash and an equality check. The two must agree: if two keys are equal, their hashes must be equal. Built-in types such as integers, strings and tuples already keep this rule. For your own types, keeping it is your job.

In Java, that means overriding equals() and hashCode() together. Override only equals(), and two equal objects will usually have different hashes inherited from Object, which are based on identity. They land in different slots, and a lookup for one never finds the other.

Python protects you from half of this mistake: a class that defines __eq__ without __hash__ becomes unhashable, so using its instances as keys raises an error instead of quietly misbehaving. Go and Rust settle the question at compile time. In Go, map keys must be comparable, so slices can't be keys. In Rust, key types must implement Eq and Hash, and the compiler checks that they do.

Keys must not change while they are stored

The trace above shows the most confusing hash map bug there is. A point (1, 2) is stored as a key. Its hash, 33, put it in slot 1. Then the program changes the point's x to 5. The object still sits in slot 1, but its hash would now be 157, which maps to slot 5.

Now nothing can find it. Looking up (5, 2) goes to slot 5, which is empty. Looking up (1, 2) goes to slot 1, finds the stored key, compares it, and sees (5, 2), which isn't equal. The entry is still in memory and still counted in the map's size, but no lookup can reach it.

Languages handle this risk in different ways:

• Python refuses mutable built-in types as keys: {[1, 2]: "x"} raises TypeError: unhashable type: 'list'. Tuples are allowed, as long as everything inside them is hashable.
• Java lets you use any object as a key, mutable or not. Keeping keys unchanged while they are in a map is up to you, and immutable types such as String, Integer and records make that easy.
• Go and Rust make the mistake hard to make by accident: Go copies keys into the map, and Rust only hands out read-only references to stored keys.

The safe habit in every language is the same: use immutable values as keys.

Don't depend on iteration order

Looping over a hash map visits entries in whatever order they sit in the array, which depends on their hashes and on the table's history of resizes. Unless your language guarantees an order, treat it as unpredictable, and expect it to change between versions or even between runs.

Go goes further and randomizes the starting point of every loop over a map, on purpose, so that programs can't come to depend on an order that might change. Python's dict guarantees insertion order by keeping its entries in a separate array, in the order they were added, and using the hash table only as an index into that array. JavaScript engines implement Map in a similar way.

When the attacker picks the keys

The first lesson mentioned hash flooding. If an attacker can choose keys that all collide, every lookup in that slot becomes a linear search, and inserting n such keys takes O(n²) time. In 2011, researchers showed that a single web request with many crafted form fields could keep a server busy for minutes this way, across many popular web platforms.

Languages responded in two ways:

• A secret seed. Python, Rust and Go mix a random value that the attacker can't see into their hashes, so nobody can know in advance which keys collide. Python picks the value when the program starts; Go and Rust pick one for each new table. Rust's default hasher, SipHash, was designed for exactly this job.
• A better worst case. Java's string hash is fixed by its specification, so Java instead turns long collision chains into balanced trees. Even if every key collides, a lookup in that slot takes logarithmic time instead of linear, as long as the keys can be put in order, as strings can.

Hash map or sorted map?

A hash map gives you constant-time lookups on average and no useful order. Sometimes you need order: the smallest key, all the keys between two values, or iteration in sorted order. For that, languages provide a sorted map built on a balanced tree, such as Java's TreeMap, C++'s std::map or Rust's BTreeMap. Every operation costs O(log n) instead of O(1) on average, but the keys stay sorted.

That completes the module. Check yourself with the questions below, then try the practice problems, which use everything from the five lessons.

Pseudocode & Multi-Language Implementations (C++, Java, Python)

To translate Hash maps in your language from mental model into production and interview code, start from the language-independent pseudocode below and compare how C++, Java, and Python express the exact same loop invariant:

function two_sum_hash(nums, target):
    seen = empty_hash_map()
    for i from 0 to length(nums) - 1:
        need = target - nums[i]
        if need in seen:
            return (seen[need], i)
        seen[nums[i]] = i
    return (-1, -1)

#include <vector>
#include <unordered_map>
 
std::pair<int, int> twoSumHash(const std::vector<int>& nums, int target) {
    std::unordered_map<int, int> seen;
    seen.reserve(nums.size() * 2);
    for (int i = 0; i < static_cast<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 {-1, -1};
}

import java.util.*;
 
public class HashSolver {
    public static int[] twoSumHash(int[] nums, int target) {
        Map<Integer, Integer> seen = new HashMap<>(nums.length * 2);
        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[]{-1, -1};
    }
}

def two_sum_hash(nums: list[int], target: int) -> tuple[int, int]:
    seen: dict[int, int] = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return seen[need], i
        seen[x] = i
    return -1, -1

Complexity Derivation, Edge Cases & Common Mistakes

• Time & Space Complexity Derivation: Always count how many times the inner state advances relative to input size n (amortized pointer movements, tree height O(log n), or hash-table load factor < 1) and distinguish auxiliary space (extra stack frames or buffers allocated by your algorithm) from the input storage itself.
• Boundary & Edge Cases to Verify: Test empty or single-element inputs (n <= 1), all-duplicate values, already-sorted and reverse-sorted sequences, disconnected components, and 32-bit signed integer limits (2^31 - 1) where intermediate sums or index products require 64-bit long long / long.
• Common Beginner Mistakes: Avoid recomputing prefix/window state from scratch inside nested loops, mutating a container while iterating over it, or forgetting base-case termination guards before dereferencing pointers or indices.