Appearance
3.13.3 — Built-in Types From the Inside
An order service checks whether each incoming product code is in a list of 100,000 banned codes. With a list, each check takes almost a millisecond. Change one character, so the codes live in a set instead, and each check takes 35 nanoseconds. That is about 25,000 times faster, and nothing else in the code changed. You can only make choices like that if you know what each built-in type is made of. This page opens up every core type in turn: numbers, text, bytes, lists, tuples, dicts and sets. For each one you will see how it is built, what each operation costs, and the traps that come with it. Then it covers the syntax that works across all of them: slicing, unpacking and comprehensions.
1. int: integers that never overflow
In C, Java or Go, an integer has a fixed size, usually 64 bits. If a calculation goes past about nine quintillion, the number silently wraps around to a negative value. JavaScript's numbers lose precision past 2⁵³. Python integers do neither. They simply grow.
python
print(2 ** 100) # (1)
import sys
print(sys.int_info.bits_per_digit) # (2)
print(sys.getsizeof(2 ** 30 - 1), sys.getsizeof(2 ** 30), sys.getsizeof(2 ** 60)) # (3)text
1267650600228229401496703205376
30
28 32 36(1)A 31-digit number, computed exactly.(2)CPython stores an integer as an array of "digits", where each digit holds 30 bits. It is long multiplication from school, but in base 2³⁰ instead of base 10.(3)Up to 2³⁰ − 1 fits in one digit (28 bytes). One more and a second digit is added (32 bytes). Each extra 30 bits costs 4 more bytes.
This is why Python is popular for cryptography teaching and for problems with huge numbers. You never think about overflow. The price is speed: big-number maths runs in software, digit by digit, rather than in one CPU instruction. Small numbers use a fast path, which is why BINARY_OP_ADD_INT from 3.13.1 helps so much.
One safety limit exists. Converting a string with thousands of digits into an int takes time that grows with the square of the length. Attackers once used that to freeze servers by sending a single giant number in a JSON request. So since 2022, Python refuses to convert more than 4,300 digits unless you raise the limit.
python
try:
int("9" * 5000)
except ValueError as error:
print(error)text
Exceeds the limit (4300 digits) for integer string conversion: value has 5000 digits; use sys.set_int_max_str_digits() to increase the limitDivision: /, // and %
Python has two division operators, and they never confuse each other.
python
print(7 / 2) # (1)
print(7 // 2, -7 // 2) # (2)
print(int(-7 / 2)) # (3)
print(-7 % 2, divmod(-7, 2)) # (4)text
3.5
3 -4
-3
1 (-4, 1)(1)/is always true division and always returns a float, even for8 / 2, which gives4.0.(2)//is floor division. It rounds down, towards minus infinity. So-7 // 2is-4, not-3.(3)Converting the float result withint()cuts towards zero instead and gives-3. C, Java and JavaScript'sMath.truncall cut towards zero. This difference bites people who port algorithms between languages, and the DSA pages in Part 4 point it out where it matters.(4)%matches//. The remainder always has the sign of the divisor, so-7 % 2is1. This is handy:index % lengthis always a valid index, even whenindexis negative.
bool is a subclass of int. True behaves like 1 and False like 0, so sum(order.paid for order in orders) counts paid orders. That is a feature, but it also means True == 1, which matters for dict keys in section 6.
2. float, Decimal and Fraction
A Python float is a standard 64-bit IEEE 754 floating-point number, exactly like a JavaScript number or a C double. It stores a number as a binary fraction times a power of two. Most decimal fractions, such as 0.1, have no exact binary form, in the same way that 1/3 has no exact decimal form. So the stored value is the nearest one available.
python
print(0.1 + 0.2) # (1)
print(0.1 + 0.2 == 0.3)
import math
print(math.isclose(0.1 + 0.2, 0.3)) # (2)
from decimal import Decimal
print(Decimal(0.1)) # (3)text
0.30000000000000004
False
True
0.1000000000000000055511151231257827021181583404541015625(1)Two tiny representation errors add up and become visible.(2)Never compare floats with==. Compare with a tolerance usingmath.isclose.(3)Converting the float0.1toDecimalshows its exact stored value. It was never really 0.1.
round also has a surprise. It uses banker's rounding, which rounds a value exactly halfway between two choices to the nearest even one.
python
print(round(2.5), round(3.5)) # (1)
print(round(0.125, 2)) # (2)text
2 4
0.12(1)2.5 rounds to 2 and 3.5 rounds to 4. Rounding to even avoids pushing totals upward when you round many numbers.(2)0.125 is stored as a value slightly below 0.125, so it rounds down.
Money: use Decimal
For prices and totals, binary floats are the wrong tool. The decimal module stores numbers in base 10 and lets you choose the rounding rule.
python
from decimal import Decimal, ROUND_HALF_UP
subtotal = Decimal("19.995") # (1)
total = subtotal.quantize(Decimal("0.01"), rounding=ROUND_HALF_UP) # (2)
print(total)
print(Decimal("0.1") + Decimal("0.2")) # (3)text
20.00
0.3(1)Always build aDecimalfrom a string. Building it from the float19.995would copy the float's error into it.(2)quantizerounds to two decimal places using the rule your finance team expects, here "halves go up".(3)Exact decimal arithmetic.
Many payment systems go one step further and store amounts as whole numbers of the smallest unit, such as paise or cents. 1999 paise cannot have a rounding error. fractions.Fraction also exists, for exact ratios like one third, but you will rarely need it outside maths code.
3. str and bytes: text and raw data
Python 3's biggest break from Python 2 was here. There are two completely separate types.
stris text: a sequence of Unicode characters. Strictly, it is a sequence of code points, the numbers Unicode assigns to characters.bytesis raw data: a sequence of numbers from 0 to 255, such as the contents of an image file or a network packet.
You move between them by encoding text into bytes and decoding bytes back into text, and you must name the encoding, almost always UTF-8.
python
name = "café"
data = name.encode("utf-8") # (1)
print(len(name), len(data)) # (2)
print(data)
print(data.decode("utf-8") == name) # (3)text
4 5
b'caf\xc3\xa9'
True(1)Encoding turns the text into bytes.(2)Four characters, but five bytes, because UTF-8 spends two bytes oné.(3)Decoding with the same encoding gives back the same text.
Python 3 refuses to mix them: "abc" + b"abc" raises a TypeError. That strictness ended a whole family of Python 2 bugs, where text worked fine in English and crashed the first time a customer typed an accented name.
How a str is stored: one, two or four bytes per character
Since Python 3.3, CPython stores each string using the smallest width that fits its widest character. This design is PEP 393, the flexible string representation.
python
import sys
print(sys.getsizeof("abc")) # (1)
print(sys.getsizeof("abc€")) # (2)
print(sys.getsizeof("abc😀")) # (3)text
44
66
76(1)Pure ASCII text: one byte per character, plus a header.(2)The euro sign does not fit in one byte, so every character now uses two.(3)The emoji needs four bytes, so every character uses four.
The design gives you two things at once. Most text stays compact. And text[i] is always a fast jump straight to character i, because every character in a given string has the same width. UTF-8, by contrast, would have to count from the start.
len() counts code points, not what a human sees as a character. A thumbs-up with a skin tone is two code points, so len("👍🏽") is 2. 3.6.7 explains these "grapheme clusters", and the same idea applies here.
Strings are immutable, so build them with join
You cannot change a string. Every + builds a new one. Inside a loop, that can mean copying a longer and longer string again and again.
python
lines = ["mug x2", "pen x5", "notebook x1"]
receipt = ""
for line in lines:
receipt += line + "\n" # (1)
receipt = "\n".join(lines) # (2)
print(receipt)text
mug x2
pen x5
notebook x1(1)Correct, but each step may copy everything built so far. CPython has a trick that often makes this fast for a local variable with a single reference, but you should not rely on it.(2)joinmeasures all the pieces first, allocates the final string once, and copies each piece once. This is the idiom.
bytearray: the mutable version
bytes is immutable. bytearray is its mutable twin, for building or editing binary data in place.
python
packet = bytearray(b"abc")
packet[0] = 65 # (1)
print(packet, list(packet))text
bytearray(b'Abc') [65, 98, 99](1)Indexing a bytes-like object gives a number from 0 to 255. Setting slot 0 to 65 writes the byte forA.
4. list: a dynamic array of pointers
A Python list is not a linked list. It is a dynamic array: one block of memory holding pointers to objects, side by side, plus a count. That layout explains every cost.
items[i]is instant. It is one multiplication to find the slot.items.append(x)is usually instant, because the list keeps spare room at the end.items.insert(0, x)is slow for big lists. Every pointer must shift one place to the right.x in itemsis slow for big lists. Python checks every slot in turn.
Watching the spare room
When a list runs out of room, it does not grow by one slot. It allocates a bigger block with extra space and copies the pointers over. This is called over-allocation. We can watch the hidden capacity change.
python
import sys
items = []
empty_size = sys.getsizeof(items)
last_size = empty_size
for n in range(1, 21):
items.append(n)
size = sys.getsizeof(items)
if size != last_size: # (1)
print(f"len={len(items):2} capacity={(size - empty_size) // 8}") # (2)
last_size = sizetext
len= 1 capacity=4
len= 5 capacity=8
len= 9 capacity=16
len=17 capacity=24(1)We only print when the memory size changes, which is when the list re-allocates.(2)Each slot is an 8-byte pointer, so the extra bytes divided by 8 is the number of slots.
The first append reserves four slots. Appends two, three and four cost nothing extra. The fifth append triggers a re-allocation to eight slots, and so on. Each growth adds roughly an eighth of the current size plus a small constant.
Because the extra room grows with the list, the total copying work stays proportional to the number of appends. One append occasionally costs a big copy, but averaged over all appends each one costs a constant amount. That is what amortised O(1) means. Part 4's chapter on arrays derives this properly.
When a list is the wrong tool
For a queue, where you add at one end and remove from the other, a list makes every removal from the front cost O(n). Use collections.deque, a double-ended queue built from linked blocks. It adds and removes at both ends in O(1).
python
import timeit
front_list = timeit.timeit("q.insert(0, 1)", setup="q = list(range(100_000))", number=10_000)
front_deque = timeit.timeit("q.appendleft(1)",
setup="from collections import deque; q = deque(range(100_000))",
number=10_000)
print(f"list.insert(0): {front_list:.3f}s deque.appendleft: {front_deque:.5f}s")text
list.insert(0): 0.352s deque.appendleft: 0.00025sYour exact times will differ, but the ratio, over a thousand times, will not. And for "is this value present?" checks on a big collection, use a set. That is the opening story, and section 6 explains why.
5. tuple: the fixed record
A tuple is like a list that cannot change: a fixed-size array of pointers. Use it for a small group of values that belong together and will not change, such as a coordinate or a database row.
Because it is immutable, a tuple has real advantages.
- It can be a dict key or a set member, as long as everything inside it is hashable too (3.13.2).
- It is slightly smaller and faster to create than a list.
- It tells the reader "this is a record, not a growing collection".
The comma makes the tuple, not the brackets. point = 3, 4 is a tuple. single = ("mug",) needs that trailing comma, because ("mug") is just a string in brackets.
For records with named fields, typing.NamedTuple gives you a tuple whose positions have names. 3.13.8 compares it with dataclasses.
6. dict: the hash table that runs Python
The dict is the most important type in Python, because Python itself is built from dicts. Every module's global variables live in a dict. Most objects keep their attributes in a dict called __dict__. Every keyword argument passes through one. So dicts have been tuned harder than anything else in CPython.
A dict is a hash table. Here is how a lookup like stock["mug"] works.
- Python calls
hash("mug"), which turns the key into a large integer. - It uses some of that number's bits to pick a slot in a table.
- If the slot is empty, the key is not there.
- If the slot holds an entry, Python checks that the entry's key is the same object, or has the same hash and compares
==equal. If so, it has found the value. - If the slot holds a different key, which is called a collision, Python probes another slot chosen by a fixed formula and repeats step 4.
Because step 2 jumps straight to roughly the right place, a lookup costs about the same whether the dict has ten entries or ten million. That is O(1) on average, and it is why the set version of the opening story was 25,000 times faster: set is built the same way.
The compact layout and guaranteed order
Before Python 3.6, the dict's table held the full entries directly, with many empty slots wasting space. In 2012, core developer Raymond Hettinger proposed splitting it into two arrays, and PyPy proved the idea first. Figure 1 shows the result.
The indices array is the actual hash table, but each slot holds only a tiny integer, often one byte. The entries array holds the real hash, key and value, packed together in the order they were inserted. Walk through looking up "mug": its hash lands on slot 3, slot 3 says "entry 0", and entry 0 holds the key and its value 12.
This design uses much less memory, and it has a lovely side effect. Since entries are appended in order, looping over a dict naturally visits keys in insertion order. That started as a CPython detail in 3.6 and became an official language guarantee in Python 3.7. You can now rely on dict keeping order. collections.OrderedDict still exists, mainly for its move_to_end method, which is useful for LRU caches.
When the table gets about two-thirds full, collisions become frequent. So the dict allocates bigger arrays and re-inserts everything. Like list growth, the cost is amortised O(1) per insertion.
The hash and equality contract
For a dict to work, keys must obey one rule:
If
a == b, thenhash(a) == hash(b)must also be true.
If two equal keys had different hashes, they would land in different slots, and the dict would treat them as different keys. Python's own numbers follow this rule carefully, with a surprising result.
python
print(hash(1), hash(1.0), hash(True)) # (1)
print({1: "int", 1.0: "float", True: "bool"}) # (2)text
1 1 1
{1: 'bool'}(1)1 == 1.0 == True, so all three must hash the same.(2)So they are the same key. The first key inserted,1, is kept, and each later assignment only replaces the value.
When you define __eq__ on your own class, Python sets __hash__ to None and makes your objects unhashable, unless you also define __hash__. That protects you from breaking the contract by accident. 3.13.6 shows how to do it correctly.
One more security detail. The hash of a str is randomised each time Python starts, controlled by PYTHONHASHSEED. Without that, an attacker could send thousands of form fields whose names all collide, turning every lookup into a slow probe chain and freezing the server. This attack was demonstrated against many languages in 2011, and randomised hashing has been the default in Python since 3.3.
7. set and frozenset
A set is a dict with keys and no values: an unordered collection of unique, hashable items. Membership tests are O(1) on average, which is the opening story. Sets also support the operations you know from school maths.
python
in_stock = {"mug", "pen", "notebook"}
on_sale = {"pen", "lamp"}
print(in_stock & on_sale) # (1)
print(in_stock | on_sale) # (2)
print(in_stock - on_sale) # (3)
print(in_stock ^ on_sale) # (4)text
{'pen'}
{'mug', 'lamp', 'notebook', 'pen'}
{'mug', 'notebook'}
{'mug', 'lamp', 'notebook'}(1)Intersection: in both sets.(2)Union: in either set.(3)Difference: in the first set but not the second.(4)Symmetric difference: in exactly one of the two.
The order of printed items may differ on your machine, because string hashes are randomised. Never rely on set order. A frozenset is the immutable version, so it can itself be a dict key or a member of another set.
8. The cost table
This is the table a senior engineer carries in their head. "n" is the number of items.
| Operation | list | dict / set | deque |
|---|---|---|---|
| Get by index | O(1) | — | O(n) |
x in c | O(n) | O(1) avg | O(n) |
| Append at end | O(1) amortised | O(1) avg | O(1) |
| Add or remove at front | O(n) | — | O(1) |
| Delete by key or value | O(n) | O(1) avg | O(n) |
| Sort | O(n log n) | — | — |
The word "avg" matters. A dict lookup is O(1) on average, but a terrible hash function that sends every key to the same slot makes it O(n). Python's built-in hashes are good, so in practice you only hit this with a badly written __hash__ of your own.
9. Syntax that works across every type
Slicing
sequence[start:stop:step] takes a piece of any sequence. start is included and stop is excluded. A missing value means "from the beginning" or "to the end". A negative number counts from the end.
python
code = "ORD-2026-0042"
print(code[4:8]) # (1)
print(code[-4:]) # (2)
print(code[::-1]) # (3)
items = [0, 1, 2, 3, 4, 5]
print(items[::2]) # (4)text
2026
0042
2400-6202-DRO
[0, 2, 4](1)Characters 4 to 7, which is the year.(2)The last four characters.(3)A step of −1 walks backwards, giving a reversed copy.(4)Every second item.
A slice of a list or string is a new object, a shallow copy. That is why items[:] is a common way to copy a list. Slicing never raises an error for out-of-range positions. items[10:20] just returns an empty list.
Unpacking
Python can pull a sequence apart into names in one line.
python
first, *middle, last = [10, 20, 30, 40] # (1)
print(first, middle, last)
price, discount = 500, 50 # (2)
price, discount = discount, price # (3)
print(price, discount)text
10 [20, 30] 40
50 500(1)The starred name collects everything left over, always as a list.(2)The right side builds a tuple, and the left side unpacks it.(3)The classic swap. The right side is evaluated completely into a tuple first, then unpacked, so no temporary variable is needed.
Comprehensions
A comprehension builds a new collection from an existing one in a single expression. There are four kinds.
python
prices = [120, 80, 300]
with_tax = [p * 1.18 for p in prices if p > 100] # (1)
lengths = {sku: len(sku) for sku in ["mug", "pen"]} # (2)
remainders = {p % 3 for p in prices} # (3)
total = sum(p * 2 for p in prices) # (4)
print(with_tax, lengths, remainders, total)text
[141.6, 354.0] {'mug': 3, 'pen': 3} {0, 2} 1000(1)A list comprehension with a filter: for each price over 100, add tax.(2)A dict comprehension builds key-value pairs.(3)A set comprehension removes duplicates automatically.(4)A generator expression uses round brackets. It does not build a list at all. It produces values one at a time assumasks for them, so it uses almost no memory even for a billion items. 3.13.9 explains how.
Comprehensions are faster than the equivalent for loop with append, because the loop runs in tighter bytecode. They also have their own scope, so the loop variable p does not leak into the surrounding code. Keep them to one simple idea. A comprehension with two loops and two conditions is harder to read than a plain loop.
The walrus operator :=
Python 3.8 added the assignment expression, nicknamed the walrus because := looks like a walrus's eyes and tusks. It assigns a value and uses it in the same expression. This was the change whose argument led Guido to step down (3.13.1).
python
import re
lines = ["sku=mug qty=2", "corrupt line", "sku=pen qty=5"]
quantities = [
int(match.group(1))
for line in lines
if (match := re.search(r"qty=(\d+)", line)) # (1)
]
print(quantities)text
[2, 5](1)The search runs once per line. Its result is saved inmatchand tested in the same step. Without the walrus you would have to run the search twice, once to filter and once to read the group.
What the interviewer will push on
"What is the time complexity of x in my_list versus x in my_set, and why?" They are checking that you know the mechanism. A list is an array scanned one item at a time, so O(n). A set is a hash table that jumps to the right slot, so O(1) on average. The tell is saying average and knowing the worst case is O(n) with a bad hash.
"How is a Python list implemented? What does append cost?" A dynamic array of pointers with over-allocation. append is amortised O(1), insert(0, x) and pop(0) are O(n). The good answer names collections.deque as the fix for queues. The common wrong answer is "a linked list".
"Are dicts ordered?" Yes, insertion order has been guaranteed since 3.7. The strong answer explains why: the compact dict stores entries in a dense array in insertion order, which was added in 3.6 to save memory, and the ordering came free.
"Why can't you use float for money?" Because 0.1 has no exact binary form, so totals drift. Use Decimal built from strings, or store integer cents. Bonus for knowing that round uses banker's rounding.
"What does -7 // 2 return?" -4, because // floors towards minus infinity. Mention that C and Java truncate towards zero, so ported code can differ by one.
Something to volunteer that nobody asks for: {1: "a", 1.0: "b", True: "c"} has a single key. Equal values must hash equally, and 1 == 1.0 == True. Explaining that shows you understand the hash–equality contract rather than just using dicts.
Recall
inthas unlimited size, stored as base-2³⁰ digits.//floors towards minus infinity, and%follows it.boolis a subclass ofint. String-to-int conversion is capped at 4,300 digits.floatis IEEE 754, so0.1 + 0.2 != 0.3. Compare withmath.isclose.rounduses banker's rounding. UseDecimal("…")or integer cents for money.stris Unicode text, stored at 1, 2 or 4 bytes per character (PEP 393).bytesis raw data. Convert with.encode()and.decode(). Build strings with"".join(parts).listis a dynamic array of pointers with over-allocation. Append is amortised O(1), front insert is O(n). Usedequefor queues.dictis a compact hash table. Lookups are O(1) on average. Insertion order is guaranteed since 3.7. Keys must obey: equal implies equal hash.strhashes are randomised to stop collision attacks.setis the same table without values.- Slices are shallow copies.
first, *rest = itemsunpacks. Comprehensions build collections. A generator expression builds nothing and yields lazily.:=assigns inside an expression.
Self-test: Why is x in big_set fast and x in big_list slow? What happens to a list's memory on its fifth append? Why did dicts become ordered? Why is {1: "a", True: "b"} a one-key dict? What does -7 // 2 return in Python and in C?
Quiz Bank
FoundationalWhy does a Python string with one emoji in it use more memory per character than a plain ASCII string?
CPython stores each string using one fixed width for all of its characters, chosen by its widest character (PEP 393). Pure ASCII fits in one byte per character. One character outside the first 65,536 code points, such as most emoji, needs four bytes, so the whole string switches to four bytes per character. The benefit is that indexing stays a single fast jump, because every character in a given string has the same width.
AppliedA job reads a queue of 200,000 tasks with tasks.pop(0) in a loop and takes minutes. Explain and fix.
pop(0) removes the first slot of a dynamic array, so every remaining pointer is shifted one place left. That is O(n) per pop and O(n²) for the whole loop, about twenty billion pointer moves here. Replace the list with collections.deque and use popleft(), which is O(1) because a deque is built from linked blocks of slots. If order does not matter, pop() from the end of the list is also O(1).
InterviewExplain how a dict lookup works, step by step, including collisions.
Python calls hash(key) to get an integer and uses some of its bits to choose a slot in the sparse indices array. An empty slot means the key is absent. Otherwise the slot gives a position in the dense entries array. Python compares the stored key to the requested one: first by identity, then by hash, then by ==. On a match it returns the value. If the slot holds a different key, a collision, it computes the next slot to try using a probe formula that mixes in more bits of the hash, and repeats. The table resizes when it is about two-thirds full, so probe chains stay short and lookups stay O(1) on average.
StaffAn API is being slowed down by requests containing tens of thousands of form fields. What attack might this be, and what protects Python?
It may be a hash-flooding attack. If an attacker can choose keys that all hash to the same slot, every insertion into a dict probes through all previous colliding keys, turning O(1) inserts into O(n), and parsing one request becomes O(n²). Python has randomised str and bytes hashes since 3.3 using a secret per-process seed and the SipHash family of functions, so attackers cannot predict collisions. Defence in depth still matters: limit the number of fields and the request body size at the web framework or proxy, and cap integer string lengths, which Python does by default at 4,300 digits.
Next: the types hold your data. 3.13.4 turns to the code: how Python finds a name, every kind of parameter a function can take, and how closures remember variables after their function has returned.