Dictionaries

A dict maps unique keys to values. Think of it as a real dictionary: you look up a word (the key) and get its definition (the value). Since Python 3.7 the insertion order is guaranteed. Iterate a dict and you get the keys back in the order you added them.

person = {"name": "Alice", "age": 30, "city": "Rome"}
empty  = {}

Why dicts are fast

A dict is backed by a hash table. When you write d["age"], Python runs the key through a hash function to compute where in memory the value sits, then jumps straight there. It does not scan the other keys. That is why lookup is O(1), constant time, no matter how many pairs the dict holds. A list, by contrast, has to walk element by element (O(n)) to find a value.

The only requirement: keys must be hashable. In practice this means immutable. Strings, numbers, and tuples work as keys; lists, sets, and other dicts do not.

What is a hash function and a hash map?

A hash function takes a value and returns a fixed-size integer called the hash. The same input gives the same integer within a program run, and different inputs almost always give different integers. Python exposes this as the built-in hash():

hash(42)      # 42          ints hash to themselves
hash("age")   # some large integer, e.g. 8384960025602973102

A hash map is a structure that uses that integer to decide where to store each pair. Python’s dict is a hash map. Internally it keeps an array of numbered slots and picks one with hash(key) % number_of_slots. To read the value back, it runs the same calculation and jumps straight to that slot without checking the others. That jump is what makes lookup O(1).

 Storing  d["age"] = 30

   key         hash(key)              slot = hash % 8
  "age"  ──►  8384960...102  ──►  8384960...102 % 8 = 2
                                            │
                                            ▼
  ┌──────┬──────┬─────────────┬──────┬──────┬──────┬──────┬──────┐
  │  0   │  1   │      2      │  3   │  4   │  5   │  6   │  7   │
  │      │      │ ("age", 30) │      │      │      │      │      │
  └──────┴──────┴─────────────┴──────┴──────┴──────┴──────┴──────┘

 Reading  d["age"]  later

  hash("age") % 8 = 2  ──►  go straight to slot 2  ──►  return 30

Collisions: open addressing. Sometimes two keys hash to the same slot. Python does not pile them into that slot. Instead it probes: it walks to the next slot, and the next, until it finds a free one, and stores the pair there. Say both "age" and "dog" want slot 2:

 Insert "age"  →  hash % 8 = 2  →  slot 2 free    →  place at 2
 Insert "dog"  →  hash % 8 = 2  →  slot 2 taken   →  probe → slot 3 free → place at 3

   slot:   0     1        2            3         4     5     6     7
         ┌────┬────┬────────────┬────────────┬────┬────┬────┬────┐
         │    │    │ ("age",30) │ ("dog", 7) │    │    │    │    │
         └────┴────┴────────────┴────────────┴────┴────┴────┴────┘
                      first choice   bumped here
                                     by probing

Looking "dog" back up repeats the same walk: hash to slot 2, see it holds "age" (wrong key), probe to slot 3, find "dog", return its value. Because the table is never crowded, the walk almost always stops after a step or two.

Resizing: why it costs, and why it is still O(1) on average. The slot of a key is hash % table_size. When the table grows, table_size changes, so every key must be re-placed with the new modulo. Growing an 8-slot table to 16 means re-hashing all the keys already in it:

 old table (8 slots)              new table (16 slots)
 slot = hash % 8                  slot = hash % 16
 ┌──┬──┬──┬──┬──┬──┬──┬──┐        every key recomputed and moved
 │  │a │  │b │c │  │d │e │  ───►  ┌──┬──┬──┬──┬──┬── … ──┬──┬──┐
 └──┴──┴──┴──┴──┴──┴──┴──┘        │  │e │  │  │a │  … c  │  │d │
                                  └──┴──┴──┴──┴──┴── … ──┴──┴──┘

A normal insert is O(1): compute the hash, find a free slot, store the pair. The expensive case is the insert that triggers a resize. On top of storing its own key, it has to move every key already in the dict into the bigger table. So if the dict already holds n keys, that one insert does n re-placements: its cost is O(n), not O(1).

The saving grace is that this rarely happens. A resize only fires when the table crosses 2/3 full, and each resize roughly doubles the size, so the thresholds get further and further apart (at ~5 keys, then ~10, then ~21…). Out of many inserts only a handful pay the O(n) price, and when you add up all that extra work across n inserts it comes to about O(n) total, or O(1) per insert on average. That “cheap almost every time, occasionally expensive, still O(1) on average” is what amortised O(1) means. So: a single insert is O(1) normally and O(n) on a resize, and amortised O(1) over many inserts.

Why immutable?

The dict decides where to store a pair from the key’s hash. If the key could change after you inserted it, its hash would change too, and the dict would go looking in the wrong slot on the next lookup. The pair would still be sitting in the old slot, now unreachable. To rule that out, Python only accepts keys whose value cannot change, so their hash is fixed for life.

That is exactly why a list cannot be a key. A list is mutable: you can append to it or reassign an element, which would move the hash out from under the dict. Python blocks the problem at the source by refusing to hash a list at all.

hash((1, 2))     # works    → tuples are immutable, so hashable
hash([1, 2])     # TypeError: unhashable type: 'list'

d = {}
d[(1, 2)] = "ok"   # a tuple key is fine
d[[1, 2]] = "no"   # TypeError: unhashable type: 'list'

The rule extends to anything mutable: list, set, and dict are all unhashable and cannot be keys. Their immutable counterparts can: use a tuple instead of a list, or a frozenset instead of a set.

d = {}
d[frozenset({1, 2})] = "ok"   # frozenset is immutable → hashable
d[{1, 2}]             = "no"   # TypeError: unhashable type: 'set'

One subtlety: a tuple is only hashable if everything inside it is too. A tuple that contains a list is itself unhashable, because that inner list could still change.

hash((1, 2, 3))        # works
hash((1, [2, 3]))      # TypeError — the inner list is mutable

Python dict vs Java HashMap

Both are hash maps with average O(1) lookup, but they resolve collisions differently, and that one choice ripples out into their worst case, their ordering, and their memory layout.

	Python dict	Java HashMap
Collision handling	open addressing (probe next slot)	separate chaining (a list per bucket)
get / put / delete (avg)	O(1)	O(1)
Worst-case lookup	O(n)	O(log n) since Java 8
Iteration order	insertion order (guaranteed 3.7+)	none (use LinkedHashMap)
Resize threshold	~2/3 full	0.75 full (default)
Key requirement	must be hashable (immutable)	needs hashCode() + equals()

Collisions. Python keeps one flat array and, on a clash, walks to the next free slot, which is the open addressing shown above. Java instead gives each bucket its own container. Originally that was a linked list, so a bucket holding k entries took O(k) to scan. Since Java 8, once a single bucket grows past 8 entries (and the table is at least 64 wide) that list is converted into a red-black tree, so even a heavily-collided bucket costs O(log n) instead of O(n). Python has no tree fallback. Its defence against deliberately-collided keys is hash randomization: a random seed is mixed into string hashes on each run, so an attacker cannot predict which keys map to the same slot.

Ordering. A Python dict remembers the order you inserted keys and always iterates in that order. A Java HashMap makes no such promise: iteration order looks arbitrary and can change after a resize. For order in Java you use LinkedHashMap (insertion order) or TreeMap (kept sorted, with O(log n) operations).

Memory. Since 3.6 Python uses a “compact dict”: a dense array stores the entries in insertion order, and a smaller sparse array of indices points into it. That layout is what makes ordered iteration cheap and cuts memory use. Java stores an array of bucket nodes, each a small object holding key, value, cached hash, and a next pointer.

Keys. Python enforces immutability up front: an unhashable key raises TypeError immediately. Java only asks that a key implement hashCode() and equals() consistently; it will let you use a mutable object as a key and then silently lose the entry if you mutate it afterwards, which is the same bug Python refuses to allow.

Core operations

d = {"a": 1, "b": 2, "c": 3}

# ── Read ──────────────────────────────────────────
d["a"]          # 1   — direct hash lookup.        O(1)
                #       KeyError if the key is missing
d.get("z")      # None — safe read, never raises.  O(1)
d.get("z", 0)   # 0    — supply your own default.  O(1)

# ── Write ─────────────────────────────────────────
d["d"] = 4              # add a new pair OR overwrite existing.  O(1)
d.update({"e": 5})      # merge another dict in.                 O(k)
d |= {"f": 6}           # Python 3.9+: same as update.           O(k)

# ── Update / increment ────────────────────────────
scores = {"alice": 10, "bob": 7}

scores["alice"] = 99    # overwrite: alice goes from 10 to 99
scores["alice"] += 5    # increment: works only if the key exists
                        # raises KeyError if "alice" is not in the dict

# Safe increment: use get() to default to 0 when the key is missing
scores["carol"] = scores.get("carol", 0) + 1   # carol doesn't exist → 0 + 1 = 1
scores["bob"]   = scores.get("bob",   0) + 1   # bob exists → 7 + 1 = 8

# ── Delete ────────────────────────────────────────
del d["a"]      # remove by key. KeyError if missing.  O(1)
d.pop("b")      # remove AND return the value.         O(1)
d.pop("z", None)# safe pop — returns None if missing.  O(1)

# ── Iterate ───────────────────────────────────────
for key in d:            ...   # keys   (default).  O(n)
for val in d.values():   ...   # values.            O(n)
for k, v in d.items():   ...   # both at once.      O(n)

# ── Check ─────────────────────────────────────────
"a" in d        # True — membership test on KEYS.    O(1)
len(d)          # number of pairs.                   O(1)

The key takeaway from the right-hand column: almost everything a dict does to a single key is O(1). Only operations that touch every pair (iteration, merging) scale with size.

Big O reference

Operation	Cost	Note
d[key] read/write	O(1)	hash jump, no scan
key in d	O(1)	membership on keys
d.get(key)	O(1)	safe read
del d[key] / pop	O(1)	hash jump then remove
len(d)	O(1)	stored as metadata
iteration	O(n)	visits every pair once
d.update(other)	O(k)	k = size of the other dict
value in d.values()	O(n)	values are not indexed: full scan

The one common O(n) trap

Membership testing checks keys, not values. "a" in d is O(1), but 1 in d.values() scans every value, which is O(n). If you frequently look up by value, you probably want a second dict mapping value to key.

Dict comprehensions

A dict comprehension builds a dictionary from any iterable in one expression. The syntax mirrors list comprehensions, but uses curly braces and a key: value pair instead of a single value.

# General shape:
# {key_expression: value_expression for item in iterable}

squares = {x: x**2 for x in range(6)}
# → {0: 0, 1: 1, 2: 4, 3: 9, 4: 16, 5: 25}

This is equivalent to the loop below, but more concise:

squares = {}
for x in range(6):
    squares[x] = x**2   # same result, more lines

Why “comprehension”?

The term comes from mathematical set-builder notation, where you describe a set by its rule rather than listing every element. In math:

{ x² | x ∈ ℕ, x < 6 }

reads as “all x² such that x is a natural number less than 6”. Python borrowed the same idea:

[x**2 for x in range(6)]

The structure is identical: first the result (x**2), then where the values come from (for x in range(6)), then an optional condition (if x > 2).

A useful way to remember it: a comprehension is a recipe, not a shopping list. A shopping list names every item. A recipe says how to produce them all.

Unpacking pairs with .items()

When you already have a dict and want to transform it, .items() gives you (key, value) pairs to unpack:

grades = {"Alice": 90, "Bob": 75, "Carol": 88}

# Add a 10-point bonus to every grade
curved = {name: score + 10 for name, score in grades.items()}
# → {"Alice": 100, "Bob": 85, "Carol": 98}

# Swap keys and values (only safe when values are unique)
inverted = {score: name for name, score in grades.items()}
# → {90: "Alice", 75: "Bob", 88: "Carol"}

Filtering while building

Add an if condition at the end to skip items that do not match:

grades = {"Alice": 90, "Bob": 55, "Carol": 88, "Dan": 40}

# Keep only students who passed (score >= 60)
passed = {name: score for name, score in grades.items() if score >= 60}
# → {"Alice": 90, "Carol": 88}

# Keep only even squares
even_squares = {x: x**2 for x in range(10) if x % 2 == 0}
# → {0: 0, 2: 4, 4: 16, 6: 36, 8: 64}

Building from a list of pairs

Any iterable of two-element sequences works, not just dicts:

pairs = [("a", 1), ("b", 2), ("c", 3)]

# Turn a list of (key, value) tuples into a dict
d = {k: v for k, v in pairs}
# → {"a": 1, "b": 2, "c": 3}

# dict() does the same without a comprehension when no transformation is needed
d = dict(pairs)
# → {"a": 1, "b": 2, "c": 3}

defaultdict: no more “does the key exist?”

A normal dict raises KeyError on a missing key. A defaultdict instead calls a factory function you provide and inserts that default automatically. This kills the most common dict boilerplate.

from collections import defaultdict

# Goal: group the words into lists by their first letter, turning
#   ["apple", "avocado", "banana"]
# into
#   {"a": ["apple", "avocado"], "b": ["banana"]}

# Plain dict: you must create the list the first time you see a letter
groups = {}
for word in ["apple", "avocado", "banana"]:
    key = word[0]              # word is a string; word[0] is its first letter
    if key not in groups:      # first word for this letter?
        groups[key] = []       # then start an empty list for it
    groups[key].append(word)   # now it is safe to append

# defaultdict: a missing key auto-creates the empty list, so the check is gone
groups = defaultdict(list)     # missing key → a fresh empty list
for word in ["apple", "avocado", "banana"]:
    groups[word[0]].append(word)   # word[0] = first letter; just append

# both versions produce:
# {"a": ["apple", "avocado"], "b": ["banana"]}

print(groups) shows the type prefix (defaultdict(<class 'list'>, {...})). To print just the data, convert first:

print(dict(groups))
# {'a': ['apple', 'avocado'], 'b': ['banana']}

The factory is any zero-argument callable:

defaultdict(int)    # missing key → 0     (great for counting)
defaultdict(list)   # missing key → []    (great for grouping)
defaultdict(set)    # missing key → set()
defaultdict(dict)   # missing key → {}    (nested dicts)

hits = defaultdict(int)
hits["page_a"] += 1   # starts from 0, becomes 1 (no KeyError)

Counter: counting done for you

Counter is a dict subclass built for tallying. Feed it an iterable and it counts occurrences. Looking up a key that is not present returns 0 instead of raising a KeyError, so you can read any key without checking first.

from collections import Counter

words  = ["apple", "banana", "apple", "cherry", "banana", "apple"]
counts = Counter(words)
# Counter({"apple": 3, "banana": 2, "cherry": 1})

counts["apple"]         # 3
counts["missing"]       # 0 — never a KeyError
counts.most_common(2)   # [("apple", 3), ("banana", 2)] — top N by count

Counter even supports arithmetic, which makes combining tallies trivial:

a = Counter({"x": 3, "y": 1})
b = Counter({"x": 1, "y": 2, "z": 1})

a + b   # add counts       → Counter({"x": 4, "y": 3, "z": 1})
a - b   # subtract         → Counter({"x": 2})  (zero/negative dropped)
a & b   # intersection min → Counter({"x": 1, "y": 1})
a | b   # union max        → Counter({"x": 3, "y": 2, "z": 1})

Merging dicts

There are two ways to combine dicts into a new one.

defaults  = {"color": "blue", "size": "M"}
overrides = {"size": "L", "weight": "light"}

# Python 3.9+ : the | operator
merged = defaults | overrides
# {"color": "blue", "size": "L", "weight": "light"}
#                    ^ on a shared key the right side wins

# Python 3.5+ : dict unpacking, also works on older versions
merged = {**defaults, **overrides}
# same result: overrides is unpacked last, so it wins

Both build a brand-new dict and leave the originals untouched. On modern Python | reads more clearly. Reach for {**a, **b} when you need to run on Python older than 3.9, or when you want to drop in an extra key while merging:

config = {**defaults, "debug": True}   # merge and add a key at once

Both forms are O(n + m) in time and space, where n and m are the sizes of the two dicts. Every pair from both inputs is copied into the fresh dict, and each copy is a constant-time insertion.

The unpacking operators * and **

{**a, **b} is one example of a more general idea called unpacking. Unpacking takes a collection and pours out its items one by one, as if you had typed each item yourself instead of passing the whole collection.

The clearest way to see it is with and without the star:

nums = [2, 3]

[1, *nums, 4]     # [1, 2, 3, 4]     nums is poured in
[1, nums, 4]      # [1, [2, 3], 4]   nums stays as one item

With *nums, the elements 2 and 3 land directly in the new list. Without it, the list nums goes in as a single nested element.

There are two operators. Use * on a sequence (a list, tuple, or set) and ** on a mapping (a dict, whose items come in key/value pairs). They show up in three places.

Building new collections by pouring existing ones into a fresh literal:

a = [1, 2]
b = [3, 4]

[*a, *b]        # [1, 2, 3, 4]   list           O(n+m)
(*a, *b)        # (1, 2, 3, 4)   tuple          O(n+m)
{*a, *b}        # {1, 2, 3, 4}   set (dedup)    O(n+m)
{**d1, **d2}    # merge dicts, d2 wins          O(n+m)

Each of these copies every element from the inputs into a new object, so the cost grows with the total number of elements spread: O(n + m) for two inputs, O(k) for k of them.

Passing arguments to a function. * spreads a sequence into positional arguments, ** spreads a dict into keyword arguments:

def point(x, y, z):
    ...

coords = [1, 2, 3]
point(*coords)              # same call as point(1, 2, 3)

kw = {"x": 1, "y": 2, "z": 3}
point(**kw)                 # same call as point(x=1, y=2, z=3)

Collecting arguments in a function definition. The mirror image: *args gathers any extra positional arguments into a tuple, **kwargs gathers any extra keyword arguments into a dict:

def f(*args, **kwargs):
    print(args)     # tuple of the positional arguments
    print(kwargs)   # dict of the keyword arguments

f(1, 2, mode="fast")
# args   = (1, 2)
# kwargs = {"mode": "fast"}

In a function call, spreading also costs O(k) in the number of arguments handed over, and *args / **kwargs cost O(k) to gather them back up. For a normal call the argument count is small, so this is effectively constant.

A single * also appears in assignment, where it grabs “the rest” of a sequence (see the Tuples section):

first, *rest = [1, 2, 3, 4]
# first = 1, rest = [2, 3, 4]   rest is a new list: O(n)

One star or two?

Use * for sequences (lists, tuples, sets, any iterable) and ** for mappings (dicts). In a function call * fills positional parameters while ** fills keyword ones. The number of stars follows the shape of what you are spreading, not where you spread it.

Tips & tricks for efficient dicts

1. Replace list scans with dict lookups. This is the change that saves the most time in practice. If you loop through a list to find matching items, a dict turns each O(n) search into O(1).

# Slow — O(n) lookup inside a loop → O(n·m) total
users = [{"id": 1, "name": "Al"}, {"id": 2, "name": "Bo"}]
def find(uid):
    for u in users:            # scans every time
        if u["id"] == uid:
            return u

# Fast — build an index once, then O(1) forever
by_id = {u["id"]: u for u in users}
by_id[2]                       # {"id": 2, "name": "Bo"} — instant

2. Use dict.get with a default instead of if key in d. One lookup instead of two, and cleaner.

# Two lookups: one for `in`, one for `[key]`
count = d[key] if key in d else 0

# One lookup
count = d.get(key, 0)

3. Use setdefault to read-or-initialise in one call (when a full defaultdict is overkill):

# Instead of the if-not-in dance
groups.setdefault(key, []).append(value)

4. Iterate .items() once, not the dict twice. Reading the value through d[key] inside a for key in d loop is a second, wasted hash lookup per iteration.

# Wasteful — a lookup on every pass
for k in d:
    print(k, d[k])       # d[k] re-hashes k

# Efficient — value comes free with the key
for k, v in d.items():
    print(k, v)

5. Deduplicate while preserving order with dict.fromkeys (dicts keep insertion order, and keys are unique):

data   = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3]
unique = list(dict.fromkeys(data))   # [3, 1, 4, 5, 9, 2, 6]

6. Reach for Counter and defaultdict before hand-rolling. They are written in C and handle the edge cases for you, and they are almost always faster and shorter than a manual dict with if guards.

The mental shortcut

If your code contains “search a list for X” or “check whether I’ve seen X”, a dict or a set is usually the right structure. Both give you constant-time membership, which is exactly what that pattern needs.