Python Dictionaries as Hash Maps

A Python dictionary is one of the most important tools in your DSA toolkit: under the hood it is a hash map, a data structure that stores key-value pairs and retrieves any value in O(1) average time, no matter how many items it holds. Instead of scanning through a list to find something, which costs O(n), a hash map jumps almost directly to the right slot using a hash function. This lesson covers how Python’s dict actually implements hashing, what its real performance guarantees are, and the patterns, such as frequency counting, fast lookups, and caching, that make it one of the most reached-for structures in coding interviews.

Overview: How Python’s dict Works as a Hash Map

A hash map (also called a hash table) stores data as key-value pairs and uses a hash function to decide where each pair lives internally. When you write d[key] = value, Python does not search through existing entries to find a free spot. It calls hash(key), uses that number to compute an index into an internal array, and stores the pair there. Looking up d[key] later repeats the exact same computation, so Python goes almost straight to the answer instead of scanning everything.

Concretely, imagine an internal array with 8 slots. Insert the key ‘cat’: Python computes hash('cat'), a large integer, reduces it modulo the table size to get an index, say 3, and stores the pair in slot 3. Insert ‘dog’ and it might land in slot 5. Now insert ‘bird’, and suppose hash('bird') also reduces to index 3, a collision. CPython resolves collisions with open addressing: it probes a deterministic pseudo-random sequence of other slots, say 4 next, until it finds an empty one, and stores ‘bird’ there instead. This differs from languages like Java, where a HashMap resolves collisions by chaining a linked list at each bucket. When you later look up ‘bird’, Python recomputes its hash, goes to slot 3, notices the key stored there is ‘cat’ and not equal to ‘bird’, and continues the same probe sequence until it finds the matching key.

Two consequences fall directly out of this design. First, keys must be hashable: hash(key) must return a consistent integer for as long as the key lives in the dict, which is why mutable types like list, dict, and set cannot be used as keys. Their contents, and therefore their hash, could change after insertion and corrupt the table. Tuples of hashable items, strings, numbers, and frozensets are all safe to use as keys. Second, a good hash function that spreads keys evenly is essential for performance. If many keys collide into the same slots, lookups degrade toward a linear scan.

Python also keeps the internal table sparse on purpose. Once the table gets more than roughly two-thirds full, Python allocates a larger array and re-inserts every existing key into it. This resize is what keeps the average case O(1) instead of degrading as the dict grows: it trades an occasional O(n) rebuild for consistently fast O(1) operations most of the time, so the amortized cost per insertion stays constant. Since Python 3.7, dictionaries also guarantee that insertion order is preserved when you iterate, but that is a side effect of the table also keeping a compact record of insertion order. It does not mean the dict is sorted by key, and code that needs sorted output must call sorted() explicitly.

Time and Space Complexity

Operation	Average Case	Worst Case	Why
d[key] = value (insert/update)	O(1)	O(n)	Hashing gets you to the right bucket directly on average; worst case, adversarial or unlucky collisions force a scan of every colliding slot.
d[key] / d.get(key) (lookup)	O(1)	O(n)	Same reasoning as insert: one hash computation gets you to the probable slot.
del d[key]	O(1)	O(n)	Must locate the key first (hash, then probe), then remove it.
key in d	O(1)	O(n)	Membership testing is a lookup under the hood, not a scan.
Iterating all items	O(n)	O(n)	Every key-value pair must be visited exactly once.
Space	O(n)	O(n)	One slot per stored pair, plus overhead from the table being kept intentionally sparse to reduce collisions.

The worst case exists in theory: if every key you insert happens to collide into the same bucket (or an attacker crafts keys to force this, called hash-flooding), operations degrade toward O(n). CPython defends against this by randomizing string hashes per process by default (PYTHONHASHSEED), so hash('abc') differs between runs. In everyday algorithm analysis, treat dict operations as O(1) average case, and mention the O(n) worst case only when it is relevant, such as discussing why a hash map is not a hard real-time guarantee.

Examples

Example 1: Basic Dictionary Operations

This example builds a dict of student scores one key at a time, checks membership, looks up a missing key both with and without a default, and deletes an entry.

def demonstrate_dict_basics() -> None:
    student_scores: dict[str, int] = {}
    student_scores['Alice'] = 92
    student_scores['Bob'] = 85
    student_scores['Charlie'] = 78

    print(student_scores)
    print('Alice' in student_scores)
    print(student_scores.get('Diana'))
    print(student_scores.get('Diana', 0))

    del student_scores['Bob']
    print(student_scores)

demonstrate_dict_basics()

Output:

{'Alice': 92, 'Bob': 85, 'Charlie': 78}
True
None
0
{'Alice': 92, 'Charlie': 78}

Each assignment inserts a key in O(1) average time, and printing the dict shows the three pairs in the order they were inserted, since Python 3.7 guarantees that. 'Alice' in student_scores is a hash lookup, not a scan, so it returns True in O(1). get('Diana') returns None because the key is absent and no default was given; get('Diana', 0) returns the explicit fallback 0 instead of raising a KeyError. After del student_scores['Bob'], only Alice and Charlie remain, still in their original relative order.

Example 2: Two Sum with a Hash Map

Two Sum is the canonical interview problem for hash maps: given a list of numbers and a target, find the indices of two numbers that add up to the target. The brute-force approach checks every pair in O(n squared). A hash map does it in a single O(n) pass by remembering, for every number already seen, the complement it would need.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen: dict[int, int] = {}
    for index, value in enumerate(nums):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index
    return []


def main() -> None:
    nums = [2, 7, 11, 15]
    target = 9
    print(two_sum(nums, target))

    nums2 = [3, 2, 4]
    target2 = 6
    print(two_sum(nums2, target2))


main()

Output:

[0, 1]
[1, 2]

For the first call, seen starts empty. At index 0, value 2, the complement is 7, which is not in seen, so Python stores seen[2] = 0. At index 1, value 7, the complement is 2, which is in seen (mapped to index 0), so the function immediately returns [0, 1]. For the second call with [3, 2, 4] and target 6: index 0 stores seen[3] = 0; index 1, value 2, complement 4, not seen yet, stores seen[2] = 1; index 2, value 4, complement 2, which is in seen at index 1, so it returns [1, 2]. The key insight is that each number is hashed and checked in O(1), turning an O(n squared) nested-loop problem into a single O(n) pass, at the cost of O(n) extra space for the map.

Example 3: Word Frequency Counting

Counting occurrences is one of the most common hash map patterns. This example builds a frequency dict manually with get, then shows collections.Counter, the standard-library tool built exactly for this job.

from collections import Counter


def word_frequencies(text: str) -> dict[str, int]:
    frequencies: dict[str, int] = {}
    for word in text.split():
        frequencies[word] = frequencies.get(word, 0) + 1
    return frequencies


def main() -> None:
    text = 'the quick brown fox jumps over the lazy dog the fox runs'
    manual_counts = word_frequencies(text)
    print(manual_counts)

    counter_counts = Counter(text.split())
    print(counter_counts.most_common(2))


main()

Output:

{'the': 3, 'quick': 1, 'brown': 1, 'fox': 2, 'jumps': 1, 'over': 1, 'lazy': 1, 'dog': 1, 'runs': 1}
[('the', 3), ('fox', 2)]

text.split() produces 12 words. word_frequencies walks them once, using frequencies.get(word, 0) + 1 so a first-time word defaults to 0 before being incremented to 1, avoiding a KeyError. ‘the’ appears 3 times and ‘fox’ appears 2 times; every other word appears once. The dict prints in first-seen order: the, quick, brown, fox, jumps, over, lazy, dog, runs. Counter computes the same counts internally and most_common(2) returns the two highest-count entries, ‘the’ with 3 and ‘fox’ with 2, as a list of tuples sorted by descending count.

How It Works Step by Step

Tracing two_sum([2, 7, 11, 15], 9) from Example 2 makes the hash map’s role concrete:

1. Start with an empty dict seen = {}.
2. Index 0, value 2: compute complement = 9 - 2 = 7. Hash 7 and check seen: not present. Insert seen[2] = 0 (hashes the key 2 and stores it in its bucket). State: seen = {2: 0}.
3. Index 1, value 7: compute complement = 9 - 7 = 2. Hash 2, jump to its bucket, and find it present with value 0. This is a hit.
4. Return [seen[2], 1], which is [0, 1], without ever comparing index 1 against every other element the way a brute-force nested loop would.

Every step that touches seen does one hash computation and one bucket lookup, both O(1) on average, which is why the whole pass is O(n) instead of O(n squared).

Common Mistakes

Mistake 1: Incrementing a Key That Was Never Initialized

A very common bug is using += on a dict value before that key exists, which raises KeyError because Python must first read the existing value to add to it.

counts = {}
for word in ['a', 'b', 'a']:
    counts[word] += 1
print(counts)

This fails immediately on the first iteration: counts['a'] += 1 is shorthand for counts['a'] = counts['a'] + 1, and reading counts['a'] before it has ever been set raises KeyError: 'a'. The fix is to supply a default with .get(), or use collections.defaultdict(int) so missing keys are created automatically.

def count_words(words: list[str]) -> dict[str, int]:
    counts: dict[str, int] = {}
    for word in words:
        counts[word] = counts.get(word, 0) + 1
    return counts


print(count_words(['a', 'b', 'a']))

Output:

{'a': 2, 'b': 1}

Mistake 2: Mutating a Dict While Iterating Over It

Deleting keys from a dict during a for loop over that same dict raises a RuntimeError, because the iterator detects the size changed mid-iteration.

inventory = {'apples': 10, 'bananas': 0, 'cherries': 5}
for item in inventory:
    if inventory[item] == 0:
        del inventory[item]

The loop reaches ‘bananas’, deletes it because its count is 0, and then raises RuntimeError: dictionary changed size during iteration when it tries to advance to the next item. The safe fix is to build a new dict (or iterate over a separate list of keys) instead of mutating the one you are iterating.

def remove_zero_stock(inventory: dict[str, int]) -> dict[str, int]:
    return {item: count for item, count in inventory.items() if count != 0}


def main() -> None:
    inventory = {'apples': 10, 'bananas': 0, 'cherries': 5}
    cleaned = remove_zero_stock(inventory)
    print(cleaned)


main()

Output:

{'apples': 10, 'cherries': 5}

Mistake 3: Using an Unhashable Type as a Key

Lists cannot be dict keys because they are mutable, and therefore unhashable.

cache = {}
key = [1, 2, 3]
cache[key] = 'cached result'

This raises TypeError: unhashable type: 'list' the moment Python tries to hash key to find its bucket. When you need a composite key, such as caching results for a sequence of numbers, use a tuple instead, since tuples are immutable and hashable as long as everything inside them is also hashable.

def main() -> None:
    cache: dict[tuple[int, ...], str] = {}
    key = (1, 2, 3)
    cache[key] = 'cached result'
    print(cache)


main()

Output:

{(1, 2, 3): 'cached result'}

Best Practices

• Reach for a dict whenever you need repeated O(1) lookups, counts, or grouping instead of repeatedly scanning a list; this is the classic space-for-time tradeoff at the heart of hashing.
• Use .get(key, default) or collections.defaultdict instead of checking key in d and then indexing, which does two lookups where one would do and still risks a KeyError if you forget the check.
• Use collections.Counter for frequency counting and collections.defaultdict(list) for grouping; both are standard-library tools built exactly for these hash map patterns.
• Only use immutable, hashable values as keys: strings, numbers, tuples of hashable items, or frozensets. Never lists, sets, or plain dicts.
• Do not rely on dict iteration order for anything beyond insertion order. If you need sorted output, call sorted() explicitly on the items.
• Prefer dict or set comprehensions for simple transformations; they are typically faster and more readable than an equivalent manual loop.
• Remember that building a hash map costs O(n) extra space. When memory is extremely tight and the input is already sorted, a two-pointer approach may be a better fit than a hash map.

Practice Exercises

1. Contains Duplicate. Given a list of integers nums, return True if any value appears at least twice, and False if every element is distinct. Aim for O(n) time using a set instead of the O(n squared) brute-force nested loop. Example: contains_duplicate([1, 2, 3, 1]) should return True; contains_duplicate([1, 2, 3, 4]) should return False.

2. Group Anagrams. Given a list of words, group the words that are anagrams of each other. Hint: use a dict whose key is a canonical form of each word, such as its letters sorted into a tuple, and whose value is a list of the original words that share that canonical form. Example input ['eat', 'tea', 'tan', 'ate', 'nat', 'bat'] should group into three groups: one containing ‘eat’, ‘tea’, ‘ate’, one containing ‘tan’, ‘nat’, and one containing just ‘bat’.

3. First Non-Repeating Character. Given a string, return the index of the first character that does not repeat anywhere else in the string, or -1 if none exists. Hint: build a frequency dict in one pass, then scan the string again in original order looking for the first character whose count is 1. Example: first_non_repeating('swiss') should return 1, the index of ‘w’.

Summary

• A Python dict is a hash map: it uses hash(key) to jump almost directly to a key’s storage slot instead of scanning, giving O(1) average time for insert, lookup, delete, and membership testing.
• CPython resolves hash collisions with open addressing, probing alternate slots in a deterministic sequence, and resizes the internal table once it gets too full, which is what keeps performance O(1) on average even as the dict grows.
• Worst-case dict operations are O(n) if many keys collide, though Python’s hash randomization makes this rare in practice; treat O(1) as the everyday assumption but know the worst case exists.
• Keys must be hashable and effectively immutable: strings, numbers, and tuples of hashable items work; lists, sets, and dicts do not.
• Since Python 3.7, dicts preserve insertion order on iteration, but that is not the same as being sorted by key.
• Common bugs include incrementing an uninitialized key with +=, mutating a dict while iterating over it, and trying to use an unhashable type as a key; all three are avoidable with .get()/defaultdict, building a new dict instead of mutating in place, and using tuples for composite keys.
• Space cost is O(n), one slot per stored pair, which is the price paid for O(1) average time, the classic space-time tradeoff behind every hash map use case: counting, grouping, caching, and fast membership testing.