Visualizing Python's Hash Map implementation. Experience the power of O(1) lookups and nested JSON-like structures.
Overview
What a dict actually is
A dictionary maps keys to values. Internally it is a hash table: Python calls hash(key), reduces the result to an index into an array of slots, and stores the entry there. Looking a key up repeats the computation and goes straight to the slot — no scanning.
That is why lookup is O(1) on average rather than O(n): the cost does not depend on how many items the dict holds. A dict with ten entries and a dict with ten million take about the same time to answer d[k].
Operations
Strings, numbers, lists, or dicts allowed.
Snippet
Data State
my_dict = { ... }
items: 3
Modify keys above or click rows to pop elements.
Logic Insight
Dictionaries map unique keys to values using a hashing function for instant access.
•Key Type: Keys must be immutable (strings, numbers, tuples).
•Collision: Python handles hashing collisions internally to maintain speed.
•Search: Lookups don't scan the list; they calculate the address.
Performance Bar
Current OperationO(1)
Note: .keys(), .values(), and .items() take O(n).
Python Dictionary Lab: A Practical Guide
Python's dict is a hash table with O(1) average lookup and, since 3.7, a guaranteed insertion order. Knowing which operations are cheap and which quietly are not is most of using it well.
The operations, and what they cost
d[k] = v # insert or overwrite — O(1)
d[k] # lookup, KeyError if absent — O(1)
d.get(k, default) # lookup, default if absent — O(1)
The last one catches people out. d.keys() does not build a list; it returns a lightweight view that stays live as the dict changes. Iterating it is O(n), but creating it is free.
The important contrast is with values. k in d checks keys and is O(1); v in d.values() scans and is O(n). They look symmetric and are not.
A hash table with guaranteed order
A Python dictionary maps keys to values with roughly constant-time lookup. Since Python 3.7 it also preserves insertion order, which is a language guarantee rather than an implementation detail.
Operation
Complexity
d[key]
O(1) average
d[key] = value
O(1) average
del d[key]
O(1) average
key in d
O(1) average
len(d)
O(1)
Iteration
O(n), in insertion order
"Average" is doing work in those rows: the worst case is O(n) when every key collides, which requires a pathological hash function or adversarially chosen keys. Python randomises string hashes per process specifically to prevent the latter as a denial-of-service vector.
Accessing keys that might not exist
Four ways, each right in a different situation:
d = {"a": 1}
d["b"] # KeyError
d.get("b") # None
d.get("b", 0) # 0 - a default of your choosing
d.setdefault("b", 0) # returns 0 AND inserts b: 0
if "b" in d: ... # explicit check
setdefault is the one people forget, and it is useful precisely because it inserts — which is also its trap, since reading a key with it modifies the dictionary.
For counting and grouping, the collections module removes the boilerplate entirely:
from collections import Counter, defaultdict
Counter(words).most_common(5) # the five most frequent words
groups = defaultdict(list)
for user in users:
groups[user.country].append(user) # no "if key not in dict" needed
defaultdict(list) creates an empty list on first access to a key, turning a four-line grouping pattern into one line. Note that it also creates the key on a mere read, so use .get() when only inspecting.
What can be a key
A key must be hashable: it must have a hash that never changes, and support equality comparison.
If a list could be a key, mutating it after insertion would change its hash and the entry would become unreachable — stored in a slot the new hash does not point to.
For a custom class, __eq__ and __hash__ must agree:
class Point:
def __init__(self, x, y):
self.x, self.y = x, y
def __eq__(self, other):
return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
def __hash__(self):
return hash((self.x, self.y)) # hash the same fields as __eq__
Defining __eq__ without __hash__ makes the class unhashable in Python 3 — a deliberate safeguard, because equal objects with different hashes would land in different slots and both exist in the dictionary.
What the hash table gives you, and the order it now keeps
A dict is a hash table with one extra promise since Python 3.7: it remembers insertion order. Both halves matter, and both are easy to check -- along with what can be a key, which is a rule about hashing rather than about types.
example_01.pyPython
import time
n = 100000
keys = ["k%d" % i for i in range(n)]
d = {k: i for i, k in enumerate(keys)}
as_list = list(d.items())
print("%d entries" % n)
# A dict lookup is far below the browser clock's resolution, so time a
# large batch of them and divide rather than timing one.
DICT_REPS, SCAN_REPS = 200000, 20
t0 = time.time()
for _ in range(DICT_REPS):
_ = d["k99999"]
t1 = time.time()
for _ in range(SCAN_REPS):
_ = [v for k, v in as_list if k == "k99999"]
t2 = time.time()
per_lookup = (t1 - t0) / DICT_REPS
per_scan = (t2 - t1) / SCAN_REPS
print(" one dict lookup: %10.3f microseconds" % (per_lookup * 1e6))
print(" one list scan: %10.3f microseconds" % (per_scan * 1e6))
print(" the dict is roughly %.0fx faster, and does not read the other %d keys"
% (per_scan / per_lookup, n - 1))
# The dict does not look at the other 99,999 keys. It hashes the one you
# asked for and goes straight to a slot, which is why the cost does not
# grow with the size of the dictionary.
#
# ORDER. Since 3.7 the language guarantees insertion order:
d2 = {}
for word in ["pear", "apple", "fig", "date"]:
d2[word] = len(word)
print()
print("insertion order preserved:", list(d2))
d2["apple"] = 99 # updating a value does NOT reorder
print("after updating 'apple': ", list(d2))
del d2["fig"]
d2["fig"] = 3 # deleting and re-adding DOES
print("after del + re-add 'fig': ", list(d2))
# Updating a value keeps the position; removing and re-inserting moves the
# key to the end. That is worth knowing before relying on the order.
#
# WHAT CAN BE A KEY. The rule is hashability, and the reason is that a
# mutable key could change its hash after being stored and become
# unfindable.
for candidate in [42, "text", (1, 2), 3.14, True, frozenset([1]),
[1, 2], {1: 2}, {1, 2}]:
try:
{candidate: 1}
print(" %-14r hashable" % (candidate,))
except TypeError as e:
print(" %-14r NOT hashable -- %s" % (candidate, e))
# Tuples work, lists do not, and the difference is mutability rather than
# any notion of "simple type". A tuple containing a list is not hashable
# either, because hashability has to hold all the way down:
try:
{(1, [2]): "x"}
except TypeError as e:
print()
print(" (1, [2]) as a key ->", e)
# And the collision that surprises people: True == 1, and equal keys with
# equal hashes are the SAME key.
print()
print(" {1: 'one', True: 'yes'} =", {1: "one", True: "yes"})
print(" hash(1) == hash(True):", hash(1) == hash(True), " 1 == True:", 1 == True)
# One entry, not two. The key stayed as the first one inserted and only
# the value was replaced -- which is exactly what happens when any two
# keys compare equal.
#
# Finally, the safe ways to read a key that may be absent:
stock = {"apples": 3}
print()
print(" stock.get('pears'): ", stock.get("pears"))
print(" stock.get('pears', 0): ", stock.get("pears", 0))
print(" stock.setdefault('pears',0):", stock.setdefault("pears", 0))
print(" stock is now: ", stock)
# get() reads without writing; setdefault() inserts the default and
# returns it, which is convenient and is also a mutation -- the source of
# a surprising number of dictionaries that grew keys nobody meant to add.
Output
Try it yourself
Compare get with direct indexing. Choose Method for a lookup on a missing key and press Execute. Direct indexing raises KeyError; get returns None instead. That difference decides which one belongs in your code.
Overwrite an existing key. Run an insert with a key that is already present. The dict does not grow — assignment on an existing key replaces the value in place, which is why dicts cannot hold duplicate keys.
Watch insertion order hold. Insert several keys in a deliberate order and then iterate. They come back in the order added, not sorted and not hashed — a language guarantee since Python 3.7.
Delete and re-add. Remove a key with Method set to a pop or delete, then add it back. It reappears at the end of the iteration order, because insertion order means the order of the most recent insertion.
Why keys must be hashable
A key must be hashable, which in practice means immutable. Strings, numbers and tuples work; lists, dicts and sets do not, and d[[1,2]] = x raises TypeError: unhashable type: 'list'.
The reason is that the hash determines the storage slot. If a key could change after insertion, its hash would change, and the entry would be sitting in a slot the lookup no longer computes — the value would become unreachable while still occupying memory. Forbidding mutable keys makes that impossible.
A tuple is hashable only if everything inside it is, so (1, 2) works as a key and (1, [2]) does not.
Where this goes wrong
Using try/except KeyError where get belongs. When a missing key is expected rather than exceptional, d.get(k, default) is clearer and faster than catching.
Mutating a dict while iterating it. Adding or deleting during a for k in d loop raises RuntimeError. Iterate over list(d) if the dict must change inside the loop.
Searching values in a loop.if v in d.values() inside a loop over n items is O(n²). If you need lookup by value, build the inverted dict once.
Reinventing defaultdict and Counter. Checking whether a key exists before appending is what collections.defaultdict is for, and counting occurrences is what collections.Counter is for.
What to remember
A Python dict is a hash table giving O(1) average insert, lookup, and delete, with keys required to be hashable so their storage slot cannot move. Since 3.7 it also preserves insertion order. The traps are the asymmetries: keys are O(1) but values are O(n), views are live rather than snapshots, and mutating during iteration is an error rather than undefined behaviour.
The dictionary as an index: the key optimisation
The single most valuable use of dictionaries in practical code is replacing a repeated scan.
# O(n*m) - for each order, scan every customer
for order in orders:
for c in customers:
if c.id == order.customer_id:
...
# O(n+m) - build the index once, then constant-time lookups
by_id = {c.id: c for c in customers}
for order in orders:
c = by_id[order.customer_id]
With 10,000 orders and 10,000 customers that is 100 million comparisons against 20,000 operations — and the second version is shorter.
The pattern generalises: whenever a loop contains a search, a dictionary built beforehand usually eliminates it. Recognising it is worth more than most algorithmic knowledge in everyday work.
Comprehensions, merging and views
lengths = {word: len(word) for word in words}
inverted = {v: k for k, v in original.items()}
filtered = {k: v for k, v in prices.items() if v > 1.00}
merged = defaults | overrides # Python 3.9+, right side wins
defaults |= overrides # in place
Iteration returns views, not copies:
for key in d: ... # keys
for key, value in d.items(): ... # the usual choice
for value in d.values(): ...
Views are live, which is why modifying a dictionary while iterating it raises RuntimeError: dictionary changed size during iteration. To delete while looping, iterate over a snapshot: for k in list(d):.
Sorting a dictionary produces a new one, since dictionaries have no sort method:
The dataclass row is worth emphasising. A dictionary with fixed keys — {"name": ..., "email": ..., "age": ...} — is better as a dataclass: attribute access, type hints, autocompletion, and a typo becomes an error rather than a silent KeyError at runtime.
Questions people ask
Are dictionaries ordered? Yes, by insertion, guaranteed since Python 3.7. That is not sorted order.
Why can a list not be a key? Mutating it would change its hash and orphan the entry. Use a tuple.
How much memory does a dictionary use? More than a list of the same values — it stores hashes and spare capacity. Lookup speed is what you are buying.
Is dict.get() slower than d[key]? Marginally, because it is a method call. Both are O(1).
How do I merge dictionaries?a | b in Python 3.9+, or {**a, **b} in earlier versions.
Why do my string hashes change between runs? Deliberate per-process randomisation, to prevent collision-based denial-of-service attacks. Set PYTHONHASHSEED to fix it.
Recap in one screen
A hash table with O(1) average lookup, and insertion order preserved as a language guarantee.
.get() for a safe read, defaultdict and Counter for grouping and counting.
Keys must be immutable, and __eq__ and __hash__ must agree for custom classes.
Building a dictionary to replace a repeated scan is the highest-value optimisation in ordinary Python.
Iteration yields live views, so modify a snapshot rather than the dictionary you are looping over.
Run it in Python
A dict is a hash table with the sharp edges filed off. This program times a lookup against a list scan, shows the four idioms worth knowing, and then demonstrates the two rules people trip over: keys must be hashable, and equal keys are the same key.
dictionaries.pyPython 3
# A dict is a hash table: keys hashed to slots, so lookup does not scan.
from collections import Counter, defaultdict
import time
stock = {"apple": 12, "banana": 3, "cherry": 40}
print("dict :", stock)
print("stock['apple'] :", stock["apple"], "- one hash, one probe")
print("'fig' in stock :", "fig" in stock)
print("stock.get('fig', 0):", stock.get("fig", 0), "- no KeyError")
# --- why it matters ----------------------------------------------------
N = 200_000
haystack_list = list(range(N))
haystack_set = set(haystack_list)
for label, container in (("list", haystack_list), ("set/dict", haystack_set)):
start = time.time()
for probe in (0, N // 2, N - 1, -1):
probe in container
print(f"{label:>9}: 4 membership tests in {time.time() - start:.4f}s")
print("The list scans. The hash table computes where the answer would be.")
# --- the idioms worth knowing -----------------------------------------
words = "the quick brown fox jumps over the lazy dog the fox".split()
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1 # 1. get with a default
groups = defaultdict(list)
for w in words:
groups[len(w)].append(w) # 2. defaultdict, no setup
print()
print("counts :", Counter(words).most_common(3)) # 3. Counter does it for you
print("by length:", dict(groups))
print("inverted :", {v: k for k, v in stock.items()}) # 4. comprehension
# --- the two rules ----------------------------------------------------
print()
try:
{[1, 2]: "x"} # a list can change; its hash cannot
except TypeError as e:
print("list as key ->", e)
print("tuple as key ->", {(1, 2): "fine"})
print()
d = {1: "int one", 1.0: "float one", True: "bool one"}
print("{1: ..., 1.0: ..., True: ...} ->", d)
print("hash(1) == hash(1.0) == hash(True):", hash(1) == hash(1.0) == hash(True))
print("They are equal AND hash the same, so they are one key with one value.")
Output
How the code works
stock["apple"]Hash the key, go to the slot, compare. No part of that depends on how many keys there are, which is the whole reason dictionaries are everywhere — see hash tables for the machinery.
probe in haystack_listA list has to compare against every element until it finds one, so in is O(n). Swapping a list for a set is the single highest-value optimisation in most beginner Python.
counts.get(w, 0) + 1The default avoids a KeyError on the first sight of a word without needing an if. defaultdict and Counter are the same idea, pre-packaged.
{[1, 2]: "x"}Keys must be hashable, which in practice means immutable. If a key could change after insertion, its hash would no longer point at the slot it lives in and it would become unreachable.
{1: ..., 1.0: ..., True: ...}One entry, not three. 1 == 1.0 == True and they hash identically, so each assignment overwrites the previous value while keeping the first key object.
Change one thing
Time -1 in haystack_list alone. The miss is the worst case: the entire list, every time.
Insert keys in a scrambled order and print the dict. Since Python 3.7 insertion order is preserved — a guarantee, not an accident.
Use a tuple (row, col) as a key to build a sparse grid. That is how you store a large mostly-empty matrix without allocating it.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.
Check yourself
0 of 3
Answer without scrolling back up.
Why must dictionary keys be hashable?
It would become unreachable. In practice this means immutable: tuples work as keys, lists do not.
{1: 'a', 1.0: 'b', True: 'c'} produces a dict with how many entries?
1 == 1.0 == True and all three hash identically, so each assignment overwrites the previous value while the first key object stays.
Replacing 'x in a_big_list' with 'x in a_big_set' changes the cost from:
The list compares against every element; the hash table computes where the answer would be. It is the highest-value one-line optimisation in most beginner Python.
Cheat sheet
Python Dictionary Lab
A dictionary maps keys to values. Internally it is a hash table: Python calls hash(key), reduces the result to an index into an array of slots, and stores the entry there. Looking a key up repeats the computation and goes straight to the slot — no scanning.
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.