Hash-based lookup

When you need to find a piece of data quickly, searching through a list gets expensive. If you have a thousand names and need to look up whether "Alice" is in the list, a loop through all a thousand items might take a thousand checks. A dictionary solves this by trading space for speed.

A dictionary is a collection that stores pairs of keys and values. When you ask for the value attached to a key, Python looks it up in nearly constant time, no matter how many pairs the dictionary holds. This fast lookup is powered by a technique called hashing.

How a dictionary works

Imagine you are running a quiz and need to record the score for each team. You could store pairs like ("Blue", 85) and ("Red", 72) in a list. But to find Blue's score, you would have to search through the list. A dictionary lets you write:

scores = {"Blue": 85, "Red": 72}print(scores["Blue"])

The output is:

85

Under the hood, Python applies a hash function to the key "Blue". This produces a number that points to a location in memory where the value 85 is stored. Retrieving the value takes the same amount of time whether the dictionary holds 10 pairs or 10 million pairs.

The set of built-in types that can be dictionary keys are those whose hash does not change: numbers, strings, and tuples of immutable values. Lists cannot be keys because they can be modified in place.

Building a dictionary for counting

Many contest problems ask you to count occurrences. A dictionary makes this pattern natural.

Here is a worked example. A farm plants one crop in each of several fields. Given the list of crops, one per field, find how many crop types appear in more than one field.

num_fields = 5fields = ["corn", "wheat", "corn", "barley", "wheat"]

The answer is 2: corn and wheat each appear in more than one field. Barley appears in only one.

You can solve this by looping through the fields and counting each crop.

1fields = ["corn", "wheat", "corn", "barley", "wheat"]2crop_count = {}3for crop in fields:4    if crop in crop_count:5        crop_count[crop] += 16    else:7        crop_count[crop] = 18
9result = 010for count in crop_count.values():11    if count > 1:12        result += 113
14print(result)

This builds a dictionary where each key is a crop name and the value is how many times it appears. The in operator checks whether a key exists. The .values() method gives all the counts. The output is 2.

Python offers a more concise way to write this. The .get() method retrieves a value from the dictionary and returns a default if the key is not present.

1fields = ["corn", "wheat", "corn", "barley", "wheat"]2crop_count = {}3for crop in fields:4    crop_count[crop] = crop_count.get(crop, 0) + 15
6result = sum(1 for count in crop_count.values() if count > 1)7print(result)

Both versions do the same thing. Choose the style that matches the rest of your code.

Avoiding missing key errors

If you try to access a key that does not exist, Python raises a KeyError and stops.

data = {"name": "Alice"}print(data["age"])

This crashes with KeyError: 'age'.

Three safe ways to handle missing keys exist. First, check with in before accessing:

data = {"name": "Alice"}if "age" in data:    print(data["age"])

Second, use .get() with a default:

data = {"name": "Alice"}age = data.get("age", 0)print(age)

This prints 0, the default value you provided. Third, use .setdefault() to store the default if the key is missing:

data = {"name": "Alice"}age = data.setdefault("age", 0)print(age)

For counting, .get() is the most natural choice. For collecting lists of values, .setdefault() saves a line.

Speed and memory trade

A dictionary uses more memory than a list of the same items would. But the fast lookup is often worth the extra space. If you have 100,000 names and 10,000 queries asking "is this name in the set?", a list would require 100,000 × 10,000 = 1 billion checks in the worst case. A dictionary does one lookup per query, 10,000 total.

Contest problems often come down to a choice like this one. A direct simulation or repeated search can be slow. Preprocessing the data into a dictionary first pays off whenever the rest of the program needs repeated lookups, counts, or grouping by key.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    if not input_data:7        return8
9    n = int(input_data[0])10    fields = input_data[1:n+1]11
12    crop_count = {}13    for crop in fields:14        crop_count[crop] = crop_count.get(crop, 0) + 115
16    result = sum(1 for count in crop_count.values() if count > 1)17    sys.stdout.write(str(result) + "\n")18
19
20if __name__ == "__main__":21    main()

5
corn wheat corn barley wheat

2

The program reads the number of fields, then the list of crops. It builds a dictionary counting each crop, then counts how many crops appear more than once. With dictionaries, this problem becomes straightforward.

A second example: grouping by category

Dictionaries also collect data into groups. Suppose you have a list of students and their scores, and you want to find the best score in each grade level.

1Grade: 9, Score: 852Grade: 10, Score: 923Grade: 9, Score: 784Grade: 11, Score: 88

You can group them using a dictionary where the key is the grade and the value is a list of scores.

1data = [2    (9, 85), (10, 92), (9, 78), (11, 88)3]4
5by_grade = {}6for grade, score in data:7    if grade not in by_grade:8        by_grade[grade] = []9    by_grade[grade].append(score)10
11for grade in sorted(by_grade.keys()):12    best = max(by_grade[grade])13    print(f"Grade {grade}: {best}")

The output is:

Grade 9: 85Grade 10: 92Grade 11: 88

Each grade maps to a list of scores. The .setdefault() method makes this pattern even cleaner: by_grade.setdefault(grade, []).append(score) does both the check and the append in one line. This approach scales to any number of groups without nested loops.

Common dictionary mistakes

One mistake is forgetting that dictionaries store references, not copies. If the value is a list and you modify it, the change affects the list in the dictionary.

1data = {"group_a": [1, 2]}2values = data["group_a"]3values.append(3)4print(data)  # Prints {'group_a': [1, 2, 3]}

This is usually fine, but it can surprise you if you expected the original list to stay unchanged.

Another mistake is accessing a key without checking if it exists, then modifying the result. If the key is missing, a KeyError stops the program. Always use .get() or check with in first.

A third mistake is treating a dictionary's iteration order as guaranteed to be insertion order before Python 3.7. Modern Python preserves insertion order, but old code may not. If order matters, sort the keys explicitly before iterating.

When to use a dictionary

Reach for a dictionary in four situations. You want to count occurrences of items and look up a count later. You want to group data by a key and collect every value under that key. You need to look up a value by key many times, so that building the dictionary once pays for itself. Or you need to recognize whether you have seen a particular value before.

These four needs cover most lookup problems in contests. A dictionary turns a problem that looks like it needs nested loops into a single pass over the data.