07Hash tables

In Chapter 6 we lined our values up in a row of slots and reached each one by its position — box 0, box 1, box 2. That works right up until the day you know a song's name but not its number. Then a list has no move left but to walk the whole row asking is it you? is it you? That's a million questions for a library of a million tracks. In this chapter we kill that walk, and I want to take it slowly. There's a genuinely beautiful trick hiding in here that most tutorials wave straight past. Here's the plan. We hand every key to hash() and watch it collapse into a single number. We let that number pick a bucket. We see what happens when two keys land in the same one, and we find out why the whole thing quietly trades RAM for speed. All the way through we keep circling the one question that actually matters — how does a dict jump straight to a value without ever scanning for it? By the end you'll ask for library["Titanium"] and get 245 back in a single hop. You'll know exactly why a list can never be a key while "Blinding Lights" always can. And you'll rip the values out of a dict to find a set was hiding inside it the whole time. No magic anywhere in it — just arithmetic standing in for a search.

01The problem: finding one song in a million

Let's start with the one thing a list simply cannot do. Picture your whole music library — a million tracks — living in a list of (title, seconds) pairs. Now answer one small question: how long is "Blinding Lights"? You know the name. The list doesn't care, because it only ever knows positions, box 0, box 1, box 2, never names. So watch what Python is forced to do. It walks the row, holding each pair up to the light and asking the same dull question — is it you? is it you? is it you? The pair you want could be sitting anywhere. In the worst case Python asks all one million times before it finds the match. And here's the sting: the answer isn't remembered. Ask for that same song's length a second time and you pay the full million-question toll all over again. That cost grows with the pile, every single time, and it has a name: O(n).

A dictionary (dict) refuses to play that game. Instead of going position-by-position, it stores key → value pairs and fetches by key in a single move — no walking, no asking. Each key is unique, a label that points at exactly one value. Hand the dict a key and the value falls out. You write one in curly braces: a colon glues each key to its value, and commas separate the pairs. Since Python 3.7 a dict even remembers the order you inserted things in, a small kindness the old ones didn't offer. That one-move cost has its own name, and it's the whole reason this chapter exists: O(1). It's the same tiny price whether the library holds ten songs or ten million. And you have been leaning on one all along without seeing it. The name→object bindings from chapter 3 — your module's globals, and every object's attributes — are themselves stored in a dict, mapping a name-string to the object's heap address. Every time you write x = 5 and later read x, a hash table is doing exactly the lookup this chapter is about to take apart.

song = {"title": "Blinding Lights", "artist": "The Weeknd", "seconds": 200}

print(song["artist"])                # The Weeknd — one jump, no scan
print(song["seconds"])               # 200

# song["genre"]                      → KeyError: 'genre'  (crash!)
print(song.get("genre", "unknown"))  # unknown — the safe fetch

Two ways to ask. song["artist"] demands the value and insists the key exists. Reach for a key that was never there, like "genre", and the dict doesn't shrug and hand back a blank. It raises a KeyError and stops the program cold. When you're not sure a key is present, song.get("genre", "unknown") is the gentle version. It returns the value if the key is there, and your fallback if it isn't — no crash.

you type
song = {"title": "Blinding Lights", "artist": "The Weeknd", "seconds": 200}
print(song["artist"])
print(len(song))
print("genre" in song)

print(song.get("genre"))
print(song.get("genre", "unknown"))

lengths = dict(titanium=245, levels=203)
print(lengths)
print(lengths["titanium"])

empty = {}
print(empty, len(empty), type(empty))

try:
    print(song["genre"])
except KeyError as e:
    print("KeyError:", e)

you see
The Weeknd
3
False
None
unknown
{'titanium': 245, 'levels': 203}
245
{} 0 <class 'dict'>
KeyError: 'genre'

"One jump" and "a million questions" are easy to say. It's another thing to feel the gap. Grow the library below and watch which cost moves.

The dict's entire superpower rests on turning a key into a slot number without looking. So how does "Blinding Lights" — a string, not a number — become an address? Meet hash(): every key becomes a number. →

>>> from timeit import timeit
>>> lst = list(range(1_000_000))
>>> d = {n: n for n in range(1_000_000)}    # a million keys, n -> n
>>> timeit("999_999 in lst", globals=globals(), number=100)   # 100 list scans
>>> timeit("999_999 in d", globals=globals(), number=100)     # 100 dict lookups

0.7066838000027929
4.1000021155923605e-06

02hash(): every key becomes a number

Chapter 0 left you with a superpower and a catch. The superpower: RAM can leap to box 6012 without walking the street, because the address is a calculation, not a search — start + i × 4 and you're there. The catch: that trick only works when your key already is a number. A list is happy, because lengths[3] is arithmetic. But you don't want to ask for song #3, you want to ask for "Blinding Lights", and a title is not a house number. So here's the move that unlocks the whole chapter. What if we could turn any key — a string, a pair, anything — into a number first, and then do the address arithmetic?

That converter is a hash function. Feed it any object and it doesn't just glance at it. It walks every byte of the contents, mixing each one into a running accumulator, so a single changed character avalanches into a completely different result. A string is folded byte-by-byte over its UTF-8 encoding (CPython uses an algorithm called SipHash). A tuple folds together the hashes of its own elements, in order, into one number. Because the fold reads the contents and nothing else, it obeys one iron rule: the same value always comes out as the same number, every time you ask, within one run of your program. For the same reason, equal contents give equal numbers, while ("a","b") and ("b","a") come out different, because order is folded in too. Python hands you the converter as a built-in called hash(). And the surprising part, the part that makes dictionaries possible, is that it works on things that look nothing like numbers.

# every value crunches down to one integer
print(hash(245))                        # 245  — small ints hash to themselves
print(hash("Titanium"))                 # a huge signed int — a new one every run
print(hash(("Titanium", "David Guetta")))  # tuples hash too — one number for the pair
print(hash([200, 245]))                  # TypeError: unhashable type: 'list'  (why? see below)

Now the leap makes sense. A dict keeps an internal array of slots — call them buckets. To store "Blinding Lights" → 200, Python computes hash("Blinding Lights"), then folds that gigantic number down onto a real slot by taking the remainder modulo the number of buckets. A brand-new dict starts with 8 buckets. A remainder modulo 8 can only ever be 0–7, so any 19-digit hash collapses onto a bucket that actually exists. What the bucket then stores is not the song and its length. Picture it holding two of chapter 0's 8-byte addresses — one pointing at the key object, one at the value object. (That two-pointers-in-the-bucket image is a labelled simplification. Since CPython 3.6 the bucket actually stores a small integer index into a separate dense array. It is there that the key-pointer, the value-pointer, and a cached copy of the hash live side by side, and a later deeper cut opens it up. What a bucket remembers is still just where to find the key and value. Only the indirection is glossed here.) The string "Blinding Lights" and the int 200 stay wherever they were built on the heap. The bucket just remembers where to find them. To read the value back, Python runs the exact same arithmetic — same hash, same remainder, same bucket — and follows the value's address. The key becomes an address, after a little math.

you type
lengths = {"Blinding Lights": 200, "Titanium": 245}

lengths["Levels"] = 203              # new key -> a new entry, appended
lengths["Titanium"] = 246            # key already there -> value replaced
print(lengths)

lengths.update({"Faded": 212, "Levels": 202})
print(lengths)

del lengths["Blinding Lights"]
print(lengths)

gone = lengths.pop("Faded")
print(gone, lengths)

print(lengths.pop("Nightcall", 0))

plays = {}
plays.setdefault("Levels", []).append("mon")
plays.setdefault("Levels", []).append("tue")
print(plays)

you see
{'Blinding Lights': 200, 'Titanium': 246, 'Levels': 203}
{'Blinding Lights': 200, 'Titanium': 246, 'Levels': 202, 'Faded': 212}
{'Titanium': 246, 'Levels': 202, 'Faded': 212}
212 {'Titanium': 246, 'Levels': 202}
0
{'Levels': ['mon', 'tue']}

Eight buckets, endless possible keys — you saw 200 and 8 crash into the very same slot. When two keys want one bucket, what does the dict actually do about it? →

03Buckets and collisions

A hash function hands every key a bucket number, and lookups become a single jump instead of a search. Beautiful — until two keys are handed the same number. That's a collision, and here is the uncomfortable truth: collisions are not bad luck you can engineer away. There are only ever a handful of buckets and effectively unlimited possible keys. So by sheer pigeonhole logic — more pigeons than holes — some pair must share. Squeeze 200 songs into 128 buckets and two of them collide with certainty, no matter how clever the hash. A hash table that pretended collisions couldn't happen would be a hash table that sometimes lost your data.

you type
lengths = {"Titanium": 245, "Blinding Lights": 200, "Levels": 203}

for title in lengths:
    print(title)

for title, secs in lengths.items():
    print(title, "->", secs)

print(list(lengths.keys()))
print(list(lengths.values()))
print(sum(lengths.values()), "seconds in", len(lengths), "songs")

for title in sorted(lengths):
    print(title, lengths[title])

you see
Titanium
Blinding Lights
Levels
Titanium -> 245
Blinding Lights -> 200
Levels -> 203
['Titanium', 'Blinding Lights', 'Levels']
[245, 200, 203]
648 seconds in 3 songs
Blinding Lights 200
Levels 203
Titanium 245

Python's answer is refreshingly blunt: if your home bucket is already taken, probe. Step to another slot, and keep stepping until a free one turns up, wrapping past the end back to bucket 0 if you run off the edge. The newcomer simply takes a detour. And the payoff is that lookup, later, retraces the identical steps. It hashes the key, jumps to the home bucket, asks "is this my key?", and if not, steps exactly as insertion did — until it finds the key or hits an empty slot. Same recipe in, same recipe out. That symmetry is the whole reason the detour is safe.

you type
counts = {}
for letter in "LEVELS":
    counts[letter] = counts.get(letter, 0) + 1
print(counts)

genres = {}
for song in ["edm", "pop", "edm", "rap", "edm"]:
    genres.setdefault(song, 0)
    genres[song] += 1
print(genres)

plays = {}
for title in ["Levels", "Titanium", "Levels"]:
    plays.setdefault(title, []).append("played")
print(plays)

broken = {}
try:
    broken["L"] += 1
except KeyError as e:
    print("KeyError:", e)

you see
{'L': 2, 'E': 2, 'V': 1, 'S': 1}
{'edm': 3, 'pop': 1, 'rap': 1}
{'Levels': ['played', 'played'], 'Titanium': ['played']}
KeyError: 'L'

But wait — if the address was computed from the key, why does lookup bother asking "is this my key?" at all? Because a collision may have parked a different key in your home bucket. Arriving at bucket 0 doesn't prove you found your song's length. It might be a squatter that hashed there first. So the table does exactly one kind of comparison — an equality check, == — to confirm the key it found is genuinely yours and not an impostor sharing the address. That's the only comparing a dict or set ever does, and on a healthy table it happens once, maybe twice. One hash, a jump, one ==: that is what "O(1)" is actually made of.

# a song's length IS its own hash — so its bucket is pure arithmetic
print(hash(200))          # 200   — small ints hash to themselves
print(200 % 8)            # 0     — "Blinding Lights" lands in bucket 0
print(248 % 8)            # 0     — "Get Lucky" wants that SAME bucket → collision
print(hash("Titanium"))   # a huge, salted number — different every run

Notice the last line. Integer keys hash to themselves, so their buckets are dead reproducible. But string keys get a salted hash that changes every time Python starts, precisely so an attacker can't hand-craft keys that all collide. That's why the interactive below hashes song lengths (plain integers): the arithmetic is honest and you can check it by hand. Drag the slider and insert five songs one at a time, and watch two of them fight for a bucket.

Probing is cheap while free slots are easy to find — but every insertion crowds the table, probes lengthen, and O(1) starts rotting toward O(n). Python refuses to let that happen: the moment the table drifts past about two-thirds full it quietly builds a bigger one. That trade — spend RAM, keep the speed — is the load factor. →

04Load factor: RAM traded for speed

You've seen the bucket trick: hash(key) % size turns a key straight into a slot number, so a lookup is one jump instead of a search. But a fixed row of buckets has an obvious problem. Keep pouring keys in and it fills up, and the moment two keys want the same slot the dict has to probe onward to the next free one. The fuller the table, the longer those probes. So the dict watches one number like a hawk: the fraction of buckets in use, its load factor. Let the load climb too high and the crisp one-jump lookup rots into a long shuffle past occupied slots.

CPython's rule is blunt and effective: once about two-thirds of the buckets are spoken for, the dict allocates a fresh table twice as big and re-hashes every existing key into it. Bigger table, new % size, a new home computed for everyone. That rebuild is real work, O(n) in the number of keys, and the unlucky insert that triggers it pays the whole bill at once. But it happens rarely enough that, smeared across every insert, the cost stays flat — O(1) on average. It's the exact same amortized bargain you met with list append back in chapter 6: mostly-free operations, punctuated by an occasional pause to rebuild the world.

plays = {"Levels": 3, "Titanium": 1}
song = {"title": "Blinding Lights", "artist": "The Weeknd"}
library = {"Levels": 203, "Titanium": 245}

# ---- the three crashes, caught here so you can read them side by side ----
try:
    plays["Faded"] += 1
except KeyError as e:
    print("crash 1  KeyError:", e)

try:
    print(song["genre"])
except KeyError as e:
    print("crash 2  KeyError:", e)

try:
    del library["Nightcall"]
except KeyError as e:
    print("crash 3  KeyError:", e)

# ---- fix 1: get() supplies the missing starting value ----
plays["Faded"] = plays.get("Faded", 0) + 1
print("fix 1   ", plays)

# ---- fix 2: get() with a fallback, or an `in` guard when you need a branch ----
print("fix 2a  ", song.get("genre", "unknown"))
if "genre" in song:
    print("fix 2b   genre is", song["genre"])
else:
    print("fix 2b   no genre on this track")

# ---- fix 3: pop() with a default deletes if present and shrugs if not ----
library.pop("Nightcall", None)
print("fix 3   ", library)

# the same counting fix, written with setdefault
plays.setdefault("Wake Me Up", 0)
plays["Wake Me Up"] += 1
print("bonus   ", plays)

# ------------- what it prints -------------
crash 1  KeyError: 'Faded'
crash 2  KeyError: 'genre'
crash 3  KeyError: 'Nightcall'
fix 1    {'Levels': 3, 'Titanium': 1, 'Faded': 1}
fix 2a   unknown
fix 2b   no genre on this track
fix 3    {'Levels': 203, 'Titanium': 245}
bonus    {'Levels': 3, 'Titanium': 1, 'Faded': 1, 'Wake Me Up': 1}

Sit with what that threshold implies: a dict is deliberately kept at least one-third empty, forever. The vacancy isn't slack it hasn't gotten around to using. It's the running room that keeps collisions rare and probes short. And it's why the dict is the heaviest container Python ships. On the machine I'm writing this on, building a one-million-entry dict reserves about 70 MiB — close to double the ~39 MiB a plain list of the very same numbers needs. Look at the bucket table alone, ignoring the numbers themselves, and it's 40.0 MiB against the list's 7.6 MiB pointer array — over five times heavier. A dict buys its speed with memory, and pays sticker price.

# letter_frequency.py -- the counting idiom, run over one song title

title = "BLINDING LIGHTS"
counts = {}

for letter in title:
    if letter == " ":
        continue
    counts[letter] = counts.get(letter, 0) + 1

print("title   :", title)
print("counted :", sum(counts.values()), "letters,", len(counts), "distinct")
print()

print("first-seen order -- a dict remembers arrival")
for letter, n in counts.items():
    print("  ", letter, "x", n)

print()
print("ranked by count")
ranked = []
for letter, n in counts.items():
    ranked.append((-n, letter))       # negate the count so a plain sort ranks it
ranked.sort()

for neg_n, letter in ranked:
    print("  ", letter, "|" + "#" * -neg_n, -neg_n)

print()
repeated = []
for letter, n in counts.items():
    if n > 1:
        repeated.append(letter)
print("repeated:", sorted(repeated))
print("I count :", counts.get("I", 0))
print("Z count :", counts.get("Z", 0))

title   : BLINDING LIGHTS
counted : 14 letters, 9 distinct

first-seen order -- a dict remembers arrival
   B x 1
   L x 2
   I x 3
   N x 2
   D x 1
   G x 2
   H x 1
   T x 1
   S x 1

ranked by count
   I |### 3
   G |## 2
   L |## 2
   N |## 2
   B |# 1
   D |# 1
   H |# 1
   S |# 1
   T |# 1

repeated: ['G', 'I', 'L', 'N']
I count : 3
Z count : 0

# track_lookup.py -- one library dict, six moves, the state printed after each

library = {"Blinding Lights": 200, "Titanium": 245, "Levels": 203}
print("start                    ", library)

library["Faded"] = 212                    # new key -> a new entry at the end
print("library['Faded'] = 212   ", library)

library["Titanium"] = 246                 # key already here -> value replaced
print("library['Titanium'] = 246", library)

library.update({"One Dance": 174, "Levels": 202})
print("update(2 songs)          ", library)

dropped = library.pop("Blinding Lights")  # pop removes AND hands the value back
print("pop('Blinding Lights')   ", library)
print("   it handed back        ", dropped)

del library["Faded"]                      # del is a statement -- nothing returns
print("del library['Faded']     ", library)

print()
print("how long is Levels?      ", library.get("Levels", 0), "s")
print("how long is Nightcall?   ", library.get("Nightcall", 0), "s   <- absent, no crash")
print("is Faded still in there? ", "Faded" in library)
print("songs                    ", len(library))
print("total playtime           ", sum(library.values()), "s")

print()
print("alphabetical running order")
for title in sorted(library):
    secs = library[title]
    print(f"  {title:<10} {secs // 60}:{secs % 60:02d}")

start                     {'Blinding Lights': 200, 'Titanium': 245, 'Levels': 203}
library['Faded'] = 212    {'Blinding Lights': 200, 'Titanium': 245, 'Levels': 203, 'Faded': 212}
library['Titanium'] = 246 {'Blinding Lights': 200, 'Titanium': 246, 'Levels': 203, 'Faded': 212}
update(2 songs)           {'Blinding Lights': 200, 'Titanium': 246, 'Levels': 202, 'Faded': 212, 'One Dance': 174}
pop('Blinding Lights')    {'Titanium': 246, 'Levels': 202, 'Faded': 212, 'One Dance': 174}
   it handed back         200
del library['Faded']      {'Titanium': 246, 'Levels': 202, 'One Dance': 174}

how long is Levels?       202 s
how long is Nightcall?    0 s   <- absent, no crash
is Faded still in there?  False
songs                     3
total playtime            622 s

alphabetical running order
  Levels     3:22
  One Dance  2:54
  Titanium   4:06

import sys

d = {}
print(sys.getsizeof(d))          # 64  — empty, no bucket table allocated yet
for i in range(6):
    d[i] = i
print(sys.getsizeof(d))          # 352 — the 6th key forced an 8→16 slot table

# same keys keep arrival order — a side effect of the compact table (3.7+)
plist = {}
plist["Titanium"]        = 245
plist["Blinding Lights"] = 200
plist["Levels"]          = 203
print(list(plist))            # ['Titanium', 'Blinding Lights', 'Levels']

print(hash(200))              # 200            — an int hashes to itself, every run
print(hash("Levels"))         # a huge int that DIFFERS every run — strings are salted

Step back, and the whole apparatus — the buckets, the load factor, the doubling, the re-hash — rests on a single unspoken promise. hash(key) must give the same answer at lookup time that it gave when the key was inserted. Move a key to a new bucket during a resize and later come back for it, and the only way to find it again is for its hash to be exactly what it was before. Break that promise and the key is simply lost in the table — present, but unfindable.

lengths = {"Blinding Lights": 200, "Titanium": 245, "Levels": 203, "Faded": 212}

# 1 -- THE STRAIGHT FLIP: every value becomes a key, every key becomes a value
by_length = {}
for title, secs in lengths.items():
    by_length[secs] = title

print(by_length)
print(by_length[245])

# 2 -- WHAT IT SILENTLY EATS: two songs can share a length, keys cannot
lengths["One Dance"] = 200          # same 200 seconds as Blinding Lights
naive = {}
for title, secs in lengths.items():
    naive[secs] = title
print(naive[200])                   # only the LAST title survives -- the first is gone

# 3 -- THE HONEST FLIP: each length keeps a LIST of the titles that share it
by_length = {}
for title, secs in lengths.items():
    by_length.setdefault(secs, []).append(title)

print(by_length)
for secs in sorted(by_length):
    print(secs, "->", by_length[secs])

# ------------- what it prints -------------
{200: 'Blinding Lights', 245: 'Titanium', 203: 'Levels', 212: 'Faded'}
Titanium
One Dance
{200: ['Blinding Lights', 'One Dance'], 245: ['Titanium'], 203: ['Levels'], 212: ['Faded']}
200 -> ['Blinding Lights', 'One Dance']
203 -> ['Levels']
212 -> ['Faded']
245 -> ['Titanium']

So the real question isn't how the table works — it's what kind of object can honestly make that promise. Why can a string or a number be a key, but a list never can? →

05Why a list can't be a key

Every entry in a dict is filed by its key — but not by the key you see on the page. Python files it by the key's hash: a single number crunched out of the key's contents, and that number chooses a bucket. File this pair here. Now picture a key that can change its mind after you file it. You store ["Levels", "Avicii"] → 200. Python hashes the list, gets bucket 3, and drops the entry on that shelf. Later you rename a word inside the list. Its contents changed, so its hash changes with them. The next time you reach for it, Python hashes the new contents, computes bucket 6, opens an empty shelf, and swears the key was never there.

The 200 hasn't gone anywhere. It's still sitting in bucket 3. It has simply become unfindable, filed under an address that no longer exists. That is the quiet catastrophe Python refuses to allow: not lost data, but orphaned data, present and unreachable in the same breath.

So Python bans the failure mode before it can start. A dict key must be hashable: its hash must stay fixed for the object's entire life. For the built-in types that collapses to a single word — immutable (chapter 3's photographs, not its whiteboards). str, int, float, tuple, frozenset (plus bool and None) are frozen the moment they're made, so their hash can never drift. They're welcome as keys. (A frozenset is a set welded permanently shut. You'll build both in the very next section — for now just read it as "an immutable collection," and therefore safe to file by.) list, dict and set can mutate in place, so they're turned away the instant you try. And the rule guards keys only: a value can be a list, a dict, a whole nested playlist. Values are cargo. Only keys are addresses.

you type
print(hash("Titanium") == hash("Titanium"))
print(hash(245), hash(2.0), hash(True))

by_pair = {("Titanium", "David Guetta"): 245}
print(by_pair[("Titanium", "David Guetta")])

groups = {frozenset({"Levels", "Faded"}): "edm night"}
print(groups[frozenset({"Faded", "Levels"})])

d = {1: "one"}
d[True] = "same key"
print(d, len(d))

try:
    {["Titanium", "David Guetta"]: 245}
except TypeError as e:
    print("TypeError:", e)

try:
    hash({"artist": "The Weeknd"})
except TypeError as e:
    print("TypeError:", e)

try:
    set().add({"Levels", "Faded"})
except TypeError as e:
    print("TypeError:", e)

you see
True
245 2 1
245
edm night
{1: 'same key'} 1
TypeError: unhashable type: 'list'
TypeError: unhashable type: 'dict'
TypeError: unhashable type: 'set'

# a dict key must be HASHABLE — its hash fixed for the object's whole life
lengths = { ("Blinding Lights", "The Weeknd"): 200 }   # tuple key — frozen, fine
lengths[("Blinding Lights", "The Weeknd")]              # 200 — same hash, found again

# a list can mutate, so Python refuses it the instant you try
{ ["Blinding Lights", "The Weeknd"]: 200 }
# TypeError: unhashable type: 'list'

# only KEYS are addresses — a VALUE can be anything, even a mutable list
plays = { "Blinding Lights": ["2019-11-29", "2020-03-20"] }
plays["Blinding Lights"].append("2026-07-10")          # fine — values face no rule

Below is the exact disaster the rule prevents — made visible. Pretend, just this once, that Python let a list be a key. It hashes to a bucket at insert time and the 200 is filed there. Now edit a word inside the list. Its hash lands on a new bucket, and the arrow — the lookup — walks off to the wrong shelf. Slide it back to the original bucket and the two reunite. Anywhere else, the value is stranded.

class Key:                              # pretend a mutable object were an allowed key
    def __init__(self, n): self.n = n
    def __hash__(self):    return self.n   # hash comes FROM the contents
    def __eq__(self, o):  return self.n == o.n

k = Key(0)
d = { k: "Avicii", Key(1): ..., Key(2): ..., Key(4): ..., Key(5): ... }
k in d        # True  — filed in slot 0
k.n = 3       # mutate: the hash now points at slot 3
k in d        # False — slot 3 is empty; the "Avicii" is orphaned in slot 0

So a dict is really a wall of hashed buckets, each holding a key with a value riding shotgun. Rip the values out and keep only the hashed keys, and you haven't broken anything — you've built Python's other hash structure →

06A set is a dict with the values ripped out

You just built a dict: a hash table that jumps straight to a key's value in a single step. Now do something almost violent to it. Grab the whole value column and rip it clean off. What's left is still a hash table, still jumping straight to a key in one hop, but the keys have nothing left to point at. They just are, or aren't, present. That stripped-down table is a set, and throwing the values away buys you two gifts you never asked for.

First, every element is automatically unique. Add "Titanium" to a set that already holds it, and the newcomer hashes to the exact bucket the old one occupies — the table shrugs and keeps one. Duplicates cannot survive, ever, without you writing a line to stop them. Second, the question a set answers fastest is membership. x in s is the same one-hop hash jump a dict lookup is — O(1), whether the set holds ten songs or ten million. Ask a list the same thing and it walks every element from the front, comparing as it goes — O(n), a scan that slows down in lockstep with your data.

One thing you surrender: order. A set has no positions, no index, no "first" element — songs[0] raises TypeError: 'set' object is not subscriptable. Iterate one and elements emerge in an order dictated by their hashes, not by when you added them. A set answers a single question superbly — is this in here? — and politely declines the rest.

you type
liked = {"Titanium", "Levels", "Titanium"}
print(len(liked))
print(sorted(liked))

empty = set()
print(empty, len(empty), type(empty))
print(type({}))

liked.add("Faded")
liked.add("Levels")            # already in -> nothing changes, no error
print(sorted(liked))

liked.discard("Nightcall")     # missing -> silence
liked.remove("Faded")          # present -> gone
print(sorted(liked), "Titanium" in liked)

print({3, 1, 2, 1})
print(set("LEVELS") == {"L", "E", "V", "S"})

try:
    liked.remove("Nightcall")
except KeyError as e:
    print("KeyError:", e)

you see
2
['Levels', 'Titanium']
set() 0 <class 'set'>
<class 'dict'>
['Faded', 'Levels', 'Titanium']
['Levels', 'Titanium'] True
{1, 2, 3}
True
KeyError: 'Nightcall'

you type
mine  = {"Blinding Lights", "Titanium", "Levels", "Wake Me Up"}
yours = {"Titanium", "Levels", "Sunflower", "Faded"}

print(sorted(mine | yours))
print(sorted(mine & yours))
print(sorted(mine - yours))
print(sorted(yours - mine))
print(sorted(mine ^ yours))

print({"Titanium", "Levels"} <= mine)
print(mine.isdisjoint({"Nightcall"}))
print(len(mine), len(yours), len(mine | yours))

plays = ["Levels", "Titanium", "Levels", "Faded", "Levels"]
print(len(plays), "plays ->", len(set(plays)), "distinct")
print(sorted(set(plays)))

you see
['Blinding Lights', 'Faded', 'Levels', 'Sunflower', 'Titanium', 'Wake Me Up']
['Levels', 'Titanium']
['Blinding Lights', 'Wake Me Up']
['Faded', 'Sunflower']
['Blinding Lights', 'Faded', 'Sunflower', 'Wake Me Up']
True
True
4 4 6
5 plays -> 3 distinct
['Faded', 'Levels', 'Titanium']

That O(1)-versus-O(n) gap sounds abstract until you watch it open. Picture your whole library as N songs and ask one question — is "Titanium" in it? A list has to be ready to check all N. A set checks exactly one bucket, no matter how large N grows. Drag N and watch the two costs pull apart.

In code the whole personality of a set fits in a few lines. Notice the third "Titanium" never lands, that discard forgives a missing element while remove does not, and that frozenset makes an immutable twin:

# bare braces, no colons -> a set; the duplicate never lands
songs = {"Titanium", "Levels", "Titanium"}
print(len(songs))            # 2
print("Levels" in songs)     # True  -> one hash jump, O(1)

songs.add("Faded")
songs.discard("Ghost")       # not there? no complaint
# songs.remove("Ghost")      -> KeyError: 'Ghost'

locked = frozenset(songs)    # immutable, and therefore hashable

Because a set is pure membership, it does the algebra you once drew as overlapping circles — and it's genuinely useful. Say you and a friend each keep a set of liked songs. One operator apiece answers a real question:

mine  = {"Blinding Lights", "Titanium", "Levels", "Wake Me Up"}
yours = {"Titanium", "Levels", "Sunflower", "Faded"}

mine & yours   # {'Titanium', 'Levels'}          -> songs you both like
mine | yours   # all six titles, no repeats      -> everything, deduped
mine - yours   # {'Blinding Lights', 'Wake Me Up'} -> only in mine
mine ^ yours   # the four neither shares         -> symmetric difference

{"Titanium", "Levels"} <= mine   # True -> subset test

Each returns a brand-new set and leaves the originals alone (there's isdisjoint and the <=/>= subset tests too). This is the fastest way in the language to answer "what's shared?", "what's the total, once?", or "what's unique to one side?".

Traceback (most recent call last):
  File "liked.py", line 2, in <module>
    liked.add("Titanium")
    ^^^^^^^^^
AttributeError: 'dict' object has no attribute 'add'

Traceback (most recent call last):
  File "walk.py", line 2, in <module>
    for title, secs in lengths:
        ^^^^^^^^^^^
ValueError: too many values to unpack (expected 2)

Traceback (most recent call last):
  File "tally.py", line 2, in <module>
    plays["Levels"] = plays.get("Levels") + 1
                      ~~~~~~~~~~~~~~~~~~~~^~~
TypeError: unsupported operand type(s) for +: 'NoneType' and 'int'

# hangman_state.py -- the guess-tracking core of Ajai's Hangman, in one set and one dict
# Adapted from his 99-Projects "Hangman Game" (hangman_game.py, main.py).
# His pygame version kept guesses in a LIST; a set does the same job for free.

word = "PYTHONIC"        # straight out of Ajai's own word list
lives = 6

guessed = set()          # every letter tried -- each one only ever once
state = {}               # letter -> "hit" or "miss", in the order they were tried

session = ["P", "A", "T", "H", "P", "O", "E", "N", "Y", "I", "C"]

for letter in session:
    if letter in guessed:                     # one hash jump, not a scan
        print(f"  {letter}  repeat  already tried -- costs you nothing")
        continue

    guessed.add(letter)
    if letter in word:
        state[letter] = "hit"
    else:
        state[letter] = "miss"

    misses = guessed - set(word)              # every wrong letter, in one subtraction
    shown = ""
    for slot in word:
        if slot in guessed:
            shown += slot + " "
        else:
            shown += "_ "

    print(f"  {letter}  {state[letter]:6}  {shown} lives {lives - len(misses)}")

    if len(misses) == lives:
        print("  out of lives")
        break
    if set(word) <= guessed:                  # every letter of the word is in
        print("  word complete")
        break

print()
print("word      :", word)
print("guessed   :", sorted(guessed))
print("hits      :", sorted(guessed & set(word)))
print("misses    :", sorted(guessed - set(word)))
print("still open:", sorted(set(word) - guessed))
print("lives left:", lives - len(guessed - set(word)))
print("won       :", set(word) <= guessed)
print("state     :", state)

  P  hit     P _ _ _ _ _ _ _  lives 6
  A  miss    P _ _ _ _ _ _ _  lives 5
  T  hit     P _ T _ _ _ _ _  lives 5
  H  hit     P _ T H _ _ _ _  lives 5
  P  repeat  already tried -- costs you nothing
  O  hit     P _ T H O _ _ _  lives 5
  E  miss    P _ T H O _ _ _  lives 4
  N  hit     P _ T H O N _ _  lives 4
  Y  hit     P Y T H O N _ _  lives 4
  I  hit     P Y T H O N I _  lives 4
  C  hit     P Y T H O N I C  lives 4
  word complete

word      : PYTHONIC
guessed   : ['A', 'C', 'E', 'H', 'I', 'N', 'O', 'P', 'T', 'Y']
hits      : ['C', 'H', 'I', 'N', 'O', 'P', 'T', 'Y']
misses    : ['A', 'E']
still open: []
lives left: 4
won       : True
state     : {'P': 'hit', 'A': 'miss', 'T': 'hit', 'H': 'hit', 'O': 'hit', 'E': 'miss', 'N': 'hit', 'Y': 'hit', 'I': 'hit', 'C': 'hit'}

titles  = ["Blinding Lights", "Titanium", "Levels"]
seconds = [200, 245, 203]

lengths = dict(zip(titles, seconds))
# {'Blinding Lights': 200, 'Titanium': 245, 'Levels': 203}

for title, secs in lengths.items():
    print(title, "→", secs)

You now hold four containers — list, tuple, dict, set — each blazing at one job and clumsy at another. The next chapter lines them up in one ring: memory cost and Big-O side by side, the specialists (array, deque) that beat them in a pinch, and it opens with the decision map itself — five questions that pick your structure before you type a bracket. →

mine  = ["Levels", "Titanium", "Faded", "Levels", "One Dance"]
yours = ["Titanium", "Closer", "Faded", "Titanium"]

# 1 -- THE LOOP EVERYONE WRITES FIRST: correct, but it re-scans yours every time
shared_slow = []
for song in mine:
    if song in yours and song not in shared_slow:
        shared_slow.append(song)
print(shared_slow)

# 2 -- THE SET VERSION: one operator, and duplicates cannot survive the trip
shared = set(mine) & set(yours)
print(sorted(shared))

print(sorted(set(mine) | set(yours)))
print(sorted(set(mine) - set(yours)))
print(sorted(set(mine) ^ set(yours)))
print(len(mine), "plays ->", len(set(mine)), "distinct")
print(sorted(shared) == sorted(shared_slow))

# ------------- what it prints -------------
['Titanium', 'Faded']
['Faded', 'Titanium']
['Closer', 'Faded', 'Levels', 'One Dance', 'Titanium']
['Levels', 'One Dance']
['Closer', 'Levels', 'One Dance']
5 plays -> 4 distinct
True