Dicts and Sets: Hashing, Defaults, and What Makes a Key Legal

Why a dict is fast

Looking something up in a list means comparing against every element: \(O(n)\). A dict instead computes hash(key), uses the low bits of that integer to pick a slot in an internal table, and looks there. One hash, one or two comparisons, done — independent of how many entries the dict holds.

The cost is memory (the table is deliberately kept sparse, so collisions stay rare) and a restriction on keys, which the last section makes precise.

Creating and reading

d = {"a": 1, "b": 2}
print(dict(a=1, b=2))                    # -> {'a': 1, 'b': 2}
print(dict([("a", 1), ("b", 2)]))        # -> {'a': 1, 'b': 2}

d[key] raises KeyError if the key is absent. d.get(key) returns None instead, and d.get(key, default) returns whatever you nominate:

print(d["a"])            # -> 1
print(d.get("z"))        # -> None
print(d.get("z", 0))     # -> 0
d["z"]                   # KeyError: 'z'

get never inserts. setdefault does: it returns the existing value if the key is present and otherwise inserts your default and returns that.

print(d.setdefault("c", 3))   # -> 3     key was absent, now d has 'c'
print(d.setdefault("a", 99))  # -> 1     key was present, 99 discarded
print(d)                      # -> {'a': 1, 'b': 2, 'c': 3}

in tests keys, not values, and is \(O(1)\):

print("a" in d, 1 in d)   # -> True False

Views, iteration and merging

keys(), values() and items() return views — live windows onto the dict, not copies. Iterating a dict directly iterates its keys, so for k in d: and for k in d.keys(): are the same thing; use items() when you want both halves.

for k, v in d.items():
    print(k, v)
# -> a 1
# -> b 2
# -> c 3

Since Python 3.7 insertion order is a language guarantee rather than a CPython implementation detail — it was an accident of the 3.6 dict rewrite, then blessed in the 3.7 release notes. Keys come back in the order they were first inserted; re-assigning an existing key does not move it.

order = {}
for k in "zebra":
    order[k] = order.get(k, 0) + 1
print(order)   # -> {'z': 1, 'e': 1, 'b': 1, 'r': 1, 'a': 1}

Merging has three spellings. | is the newest (PEP 584, Python 3.9+) and reads best; in every case the right-hand side wins on conflicts.

m1 = {"a": 1, "b": 2}
m2 = {"b": 20, "c": 3}
print(m1 | m2)          # -> {'a': 1, 'b': 20, 'c': 3}
print({**m1, **m2})     # -> {'a': 1, 'b': 20, 'c': 3}
m1 |= m2                # in-place, same as m1.update(m2)

Nesting is just values that happen to be dicts. Reaching into one safely means chaining get, since cfg["db"]["port"] explodes if either level is missing:

cfg = {"db": {"host": "localhost", "port": 5432}}
print(cfg["db"]["port"])                     # -> 5432
print(cfg.get("cache", {}).get("ttl", 60))   # -> 60

collections: defaultdict, Counter, OrderedDict

defaultdict(factory) calls factory() to manufacture a value the first time a missing key is read. Grouping becomes one line instead of four:

from collections import defaultdict

groups = defaultdict(list)
for word in ["apple", "avocado", "banana", "blueberry"]:
    groups[word[0]].append(word)
print(dict(groups))
# -> {'a': ['apple', 'avocado'], 'b': ['banana', 'blueberry']}

defaultdict(int) gives a counter, defaultdict(set) a multimap without duplicates. The one surprise is that merely looking creates the entry — groups["z"] returns [] and leaves 'z': [] behind — so use .get or in for read-only probing.

Counter is a dict subclass built for tallying. Missing keys read as 0 without inserting, and it supports arithmetic:

from collections import Counter

c = Counter("mississippi")
print(c)                 # -> Counter({'i': 4, 's': 4, 'p': 2, 'm': 1})
print(c.most_common(2))  # -> [('i', 4), ('s', 4)]
print(c["z"])            # -> 0     no KeyError, no insertion
print(Counter("aab") + Counter("abc"))
# -> Counter({'a': 3, 'b': 2, 'c': 1})

OrderedDict predates the 3.7 ordering guarantee and is now rarely needed, but it is not redundant. Its == is order-sensitive, and it offers move_to_end, which is what LRU caches are built from:

from collections import OrderedDict

od = OrderedDict([("a", 1), ("b", 2)])
print(od == OrderedDict([("b", 2), ("a", 1)]))   # -> False  order counts
print({"a": 1, "b": 2} == {"b": 2, "a": 1})      # -> True   plain dicts ignore it
od.move_to_end("a")
print(list(od))                                  # -> ['b', 'a']

Sets

A set is an unordered collection of distinct hashable objects — a dict without values. Membership is \(O(1)\), which is the whole reason to convert a list before testing against it repeatedly.

s = {1, 2, 3}
t = {3, 4}
print(s | t)   # -> {1, 2, 3, 4}   union
print(s & t)   # -> {3}            intersection
print(s - t)   # -> {1, 2}         difference
print(s ^ t)   # -> {1, 2, 4}      symmetric difference

Each operator has a named method (union, intersection, difference, symmetric_difference) that additionally accepts any iterable, not just another set. issubset, issuperset and isdisjoint answer the relational questions.

{} is an empty dict; the empty set is set(). There is no literal for it.

frozenset is the immutable version, and therefore itself hashable — so it can be a set element or a dict key, which is how you index things by an unordered group:

fs = frozenset([1, 2])
print({fs: "ok"}[frozenset([2, 1])])   # -> ok

What makes an object hashable

Three conditions. The object implements __hash__; that hash never changes during the object’s lifetime; and objects that compare equal have equal hashes. The last one is a contract, not a check — break it and lookups silently fail.

Mutable built-ins deliberately set __hash__ = None, because a key whose hash changed after insertion would be stranded in the wrong slot forever:

hash([1, 2])   # TypeError: unhashable type: 'list'

Hashable out of the box: int, float, str, bytes, bool, None, frozenset, and tuples whose every element is hashable. Not hashable: list, dict, set. Your own classes are hashable by default (identity-based), but defining __eq__ sets __hash__ to None unless you define __hash__ too — Python removes it rather than let you violate the contract by accident.

Next: strings and formatting, where immutability turns into a performance question.

References

1. Python Software Foundation. Mapping Types — dict.
2. Python Software Foundation. Set Types — set, frozenset.
3. Python Software Foundation. collections — container datatypes.
4. Python Software Foundation. Glossary: hashable.
5. Vandevoorde, B., & Boddu, S. PEP 584 — Add Union Operators To dict.
6. Python Software Foundation. What’s New in Python 3.7 — dict order is now guaranteed.
7. Python Wiki. TimeComplexity — dict and set operations.