Hash Maps

What actually happens

Interactive hash map demo

Add key-value pairs and watch how they are stored in buckets.

Association semantics, step by step

The bucket demo shows physical storage. This trace focuses on observable behavior: insert versus update, present-null versus missing, compute-style updates, and removal.

Key → value association

Map API: similar names, different contracts

Keys obey the same equality–hash contract

Implementation

from collections import defaultdict

words = ["to", "be", "or", "not", "to", "be"]

# Frequency map: missing keys start at zero.
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

# Index/grouping map: missing keys start with a list.
positions = defaultdict(list)
for index, word in enumerate(words):
    positions[word].append(index)

# Presence is separate from the stored value.
cache = {"report": None}
assert cache.get("report") is None
assert cache.get("missing") is None
assert "report" in cache and "missing" not in cache

# Python dict preserves insertion order.
for key, value in counts.items():
    print(key, value)

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static void main(String[] args) {
        List<String> words = List.of("to", "be", "or", "not", "to", "be");

        // LinkedHashMap matches Python dict's insertion-order iteration.
        Map<String, Integer> counts = new LinkedHashMap<>();
        for (String word : words) {
            counts.merge(word, 1, Integer::sum);
        }

        Map<String, List<Integer>> positions = new LinkedHashMap<>();
        for (int i = 0; i < words.size(); i++) {
            positions.computeIfAbsent(words.get(i), key -> new ArrayList<>())
                     .add(i);
        }

        Map<String, String> cache = new LinkedHashMap<>();
        cache.put("report", null);
        assert cache.get("report") == null;
        assert cache.get("missing") == null;
        assert cache.containsKey("report");
        assert !cache.containsKey("missing");

        for (Map.Entry<String, Integer> entry : counts.entrySet()) {
            System.out.println(entry.getKey() + " " + entry.getValue());
        }
    }
}

Missing is not the same as stored null

API details matter: Java HashMap.get returns null in both cases, while Python dict[key] raises for absence. Java's computeIfAbsent also treats a null mapping as absent.

Patterns that naturally produce a map

Iteration order is a separate feature

Python dictionaries preserve insertion order. Java HashMap does not; LinkedHashMap adds insertion/access order, while TreeMap provides sorted keys. Rely only on guarantees documented by the exact implementation.

Complexity ledger

These bounds treat key hashing/equality as constant-time. Hashing a long uncached string or comparing large composite keys adds their own cost.

Caching and concurrency require stronger contracts

Common failure modes

Exercises

1. A cache stores report → null meaning “loaded, empty.” How do you distinguish that from a missing key in Java HashMap vs Python dict?
2. n = 10⁵ inserts into a table that never resizes (tiny fixed capacity). What happens to average probe length as load factor grows past 1 for chaining? For open addressing?
3. Construct a failure timeline: insert a mutable key, change a hash field, then lookup. Where is the entry physically, and what does containsKey return?

Primary sources

• Cormen et al., Introduction to Algorithms (CLRS): hash tables, chaining, open addressing, load factor.
• Java Map / HashMap documentation: null keys/values, compute, and iteration contracts.
• Python data model: __hash__ / __eq__ and dict insertion-order guarantees.