Dicts, Sets and Hashing

40 min · Intermediate

Dict and set questions test whether you know why lookups are fast and when they break. The answer is always hashing: an object's hash picks where to look, and equality confirms the match.

How a dict finds a key

A hash table is a structure that turns each key into a number with a hash function and uses that number to find its slot, so a lookup does not scan all items.

A dict does not scan its keys. It turns the key into a number with hash(), uses the number to jump to a slot, then compares keys to confirm.

Python

prices = {'pen': 20, 'book': 150}print(hash('pen') == hash('pen'))print(prices['pen'])print('cup' in prices)print(prices.get('cup', 0))

Lookup, insert and delete take O(1) on average. When two keys land in the same slot (a collision), CPython probes other slots, so a very bad run of collisions can cost O(n). The table is resized as it fills, so inserts stay O(1) amortized.

A set works the same way but stores only keys.

Hashable keys and the equality rule

An object is hashable if it has a hash value that never changes during its life and it can be compared for equality. Equal hashable objects must have equal hashes.

A key must be hashable: it has a hash that never changes and it can be compared with ==. Equal keys must have equal hashes, so 1, 1.0 and True are the same key.

Python

1d = {}2d[1] = 'int'3d[1.0] = 'float'4d[True] = 'bool'5print(d)6try:7    d[[1, 2]] = 'list'8except TypeError as err:9    print(err)

Example 1 · Equal values share one key

Python

1d = {}2d[1] = 'a'3d[1.0] = 'b'4d[True] = 'c'5print(d, len(d))6print(hash(1) == hash(1.0) == hash(True))

Output

{1: 'c'} 1
True

What this code does

1, 1.0 and True are equal and have equal hashes.
Each assignment replaces the value of the same key, and the original key object 1 stays.

Example 2 · Unhashable keys and tuple keys

Python

1stock = {}2try:3    stock[['A', 1]] = 54except TypeError as err:5    print(err)6stock[('A', 1)] = 57print(stock[('A', 1)])8try:9    stock[('A', [1])] = 710except TypeError as err:11    print(err)

Output

unhashable type: 'list'
5
unhashable type: 'list'

What this code does

A list cannot be a key.
A tuple of hashable items can.
A tuple that holds a list is still unhashable.

Example 3 · Equality without a hash

Python

1class Sku:2    def __init__(self, code):3        self.code = code4    def __eq__(self, other):5        return self.code == other.code6
7class SkuOk(Sku):8    def __hash__(self):9        return hash(self.code)10
11try:12    {Sku('P1')}13except TypeError as err:14    print(err)15print(len({SkuOk('P1'), SkuOk('P1')}))

Output

unhashable type: 'Sku'
1

What this code does

Defining __eq__ alone sets __hash__ to None, so instances become unhashable.
Adding a matching __hash__ lets two equal objects collapse to one set member.

Ints, strings, tuples of hashable items and frozensets are hashable. Lists, dicts and sets are not, because their contents can change and the hash would no longer match the slot.

A class that defines __eq__ without __hash__ becomes unhashable. Define both, built from the same fields.

Ordering of dicts and sets

Insertion order means a dict yields its keys in the order they were first added. Changing the value of an existing key does not move it.

A dict remembers insertion order. A set promises no order at all. Re-assigning an existing key keeps its place; deleting and adding it again moves it to the end.

Python

1d = {'b': 1, 'a': 2}2d['c'] = 33d['a'] = 04del d['b']5d['b'] = 96print(list(d))7print({'x': 1, 'y': 2} == {'y': 2, 'x': 1})

Example 4 · Order of keys

Python

1d = {'b': 1, 'a': 2}2d['c'] = 33d['a'] = 04print(list(d))5del d['b']6d['b'] = 97print(list(d))

Output

['b', 'a', 'c']
['a', 'c', 'b']

What this code does

New keys go to the end; updating a key keeps its position.
A deleted key that is added again goes to the end.

Example 5 · Set operations

Python

1week1 = {'Asha', 'Ravi', 'Meena'}2week2 = {'Ravi', 'Diya'}3print(sorted(week1 & week2))4print(sorted(week1 | week2))5print(sorted(week1 - week2))6print(sorted(week1 ^ week2))

Output

['Ravi']
['Asha', 'Diya', 'Meena', 'Ravi']
['Asha', 'Meena']
['Asha', 'Diya', 'Meena']

What this code does

& keeps names in both weeks, | keeps all names.
- keeps names only in the first set, ^ keeps names in exactly one set.
sorted makes the output order stable.

Insertion order is a language guarantee since Python 3.7. Equality of two dicts ignores order. A set may print in any order, and string hashes change from one run to the next, so never depend on set order. Use sorted(s) when you need a stable listing.

Next step

Check your understanding

12 quick questions

Hashable keys and the equality rule

An object is hashable if it has a hash value that never changes during its life and it can be compared for equality. Equal hashable objects must have equal hashes.

A key must be hashable: it has a hash that never changes and it can be compared with ==. Equal keys must have equal hashes, so 1, 1.0 and True are the same key.

1class Sku:2 def __init__(self, code):3 self.code = code4 def __eq__(self, other):5 return self.code == other.code6 7class SkuOk(Sku):8 def __hash__(self):9 return hash(self.code)10 11try:12 {Sku('P1')}13except TypeError as err:14 print(err)15print(len({SkuOk('P1'), SkuOk('P1')}))