Hash Map

Hash Map Code Labs

Mental Model

A hash map stores an association from a key to a value. The key is how you ask a question. The value is the answer you want to retrieve later.

For an interview problem, the most important design decision is not the dictionary syntax. It is the meaning of the association:

Write that relationship down before coding. If the key or value changes meaning halfway through the loop, the implementation becomes difficult to reason about and hidden edge cases follow.

Python’s dict is the general-purpose mapping type used for these associations. It preserves insertion order, but exact-key lookup is still the central capability. Verify the language contract in the Python documentation(opens in a new tab). Do not choose a dictionary only because you want the first, smallest, or next key. Those are different query requirements.

Python Dict Operations

Create a dictionary with a literal, a constructor, or a comprehension:

scores = {"Ada": 92, "Grace": 98}
empty = dict()
squares = {number: number * number for number in range(5)}

Read, insert, update, test membership, and delete with operations that state your intent:

scores = {"Ada": 92, "Grace": 98}
scores["Linus"] = 88
scores["Ada"] = 95

ada_score = scores["Ada"]
optional = scores.get("Guido")
with_default = scores.get("Guido", 0)
grace_score = scores["Grace"] if "Grace" in scores else None

removed = scores.pop("Linus", None)
del scores["Ada"]

Iterating a dictionary produces keys. Use .items() when both parts of the association matter:

scores = {"Ada": 95, "Grace": 98}
names = []
pairs = []

for name in scores:
    names.append(name)

for name, score in scores.items():
    pairs.append((name, score))

Do not change dictionary size during a traversal of its live views. Iterate over a snapshot when deletion is intentional:

scores = {"Ada": 92, "Grace": 98, "Linus": 87}

for name in list(scores):
    if scores[name] < 90:
        del scores[name]

Choose the Missing-Key Behavior Deliberately

These tools solve related but different problems:

setdefault is concise for a small grouping loop:

words = ["tea", "eat", "tan"]
groups = {}

for word in words:
    signature = "".join(sorted(word))
    groups.setdefault(signature, []).append(word)

grouped = list(groups.values())

For a larger grouping routine, defaultdict makes the accumulation rule explicit:

from collections import defaultdict

words = ["tea", "eat", "tan"]
groups = defaultdict(list)

for word in words:
    signature = "".join(sorted(word))
    groups[signature].append(word)

grouped = list(groups.values())

Practical Code Patterns

Frequency Map

Write the manual form when the interview expects you to demonstrate the invariant:

def count_words(words):
    counts = {}
    for word in words:
        counts[word] = counts.get(word, 0) + 1
    return counts

counts = count_words(["red", "blue", "red", "green"])

Use Counter when the problem simply needs standard frequency behavior:

from collections import Counter

counts = Counter(["red", "blue", "red"])
most_common = counts.most_common(1)

Group by a Canonical Key

The dictionary mechanics stay simple. The interview insight is choosing a stable signature that places equivalent inputs in the same group:

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        signature = tuple(sorted(word))
        groups[signature].append(word)
    return list(groups.values())

groups = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])

The tuple is hashable. A list containing the same characters would not be a valid key.

One-Pass Complement Lookup

def two_sum(values, target):
    seen = {}  # value -> earlier index

    for index, value in enumerate(values):
        complement = target - value
        if complement in seen:
            return [seen[complement], index]
        seen[value] = index

    return []

The order is the proof. Before each lookup, seen contains only earlier indices. A match therefore uses two different positions, and the returned indices remain in original input order.

How Lookup Works

At the abstract data-structure level, a lookup follows three ideas:

1. Python obtains hash and equality behavior from the key.
2. The mapping uses that information to narrow the search for a matching key.
3. If an equal key is present, the mapping returns the associated value.

Different keys can produce the same hash. A correct mapping still uses equality to distinguish them. This is why a hash match alone cannot prove that two keys are the same.

The key must keep stable hash and equality behavior while stored. Immutable built-ins such as strings, numbers, and tuples of hashable values are common keys. Mutable containers such as lists, dictionaries, and sets are not hashable.

This guide intentionally stops at the language-level contract. You do not need CPython table layout details to choose a dictionary, write a correct invariant, or explain average complexity in a coding round.

Interview Recognition Patterns

Look for the inner search in a brute-force solution. If every iteration scans earlier values to answer one of these questions, a dictionary may replace that scan:

• Where did I see this value?
• How many times has this value appeared?
• Which group owns this item?
• Have I already computed this state?
• What earlier prefix would complete the current target?

Then define the association in one sentence and decide when it becomes valid. That timing often separates a correct solution from a plausible one.

For Two Sum(opens in a new tab), check before inserting. For prefix-sum counting(opens in a new tab), seed the empty prefix before the loop. For grouping(opens in a new tab), compute one canonical signature per item. For sliding-window counts(opens in a new tab), update both the entering and leaving sides so the map describes exactly the current window.

When the prompt asks only whether something exists, compare a set. When it requires a value, count, index, group, or computed result, a dictionary is usually the clearer model.