How Data Structures Live in Memory
Why this exists
Big-O counts operations. The machine does not execute operations; it moves bytes between a CPU and a memory system that is roughly a hundred times slower than the CPU for anything that is not already close by. A linked list and an array both give you traversal. On the machine this lesson was written on, traversing four million integers in order took 2.9 ms and traversing the same integers in a random order took 23.5 ms — an 8x gap for identical Big-O and an identical number of additions. The gap is not noise and it is not an implementation detail. It is the shape of modern hardware showing through, and it decides interviews, benchmarks and production incidents alike.
The history matters because it explains why textbooks are quiet about this. In the 1970s and 1980s, when CLRS-style analysis crystallised, a memory access cost roughly the same as an arithmetic instruction. The random-access machine (RAM) model — every memory cell reachable in unit time — was a reasonable approximation. Since then CPU speed has grown far faster than DRAM latency. A main-memory access today costs on the order of 60–100 ns; the CPU can execute a few hundred simple instructions in that time. To hide the gap, hardware grew a hierarchy of caches, and the price of an algorithm became dominated by how many times it misses those caches rather than how many instructions it executes.
This lesson gives you the model you need to predict that price. You will learn how arrays, linked structures, hash maps and trees are laid out in bytes; what a cache line is and why 64 bytes is the real unit of memory traffic; why vector beats list in C++ even for insertions in the middle; why Python's dict is a pair of arrays rather than a tree of nodes; and how much an "integer" actually costs in Python, Java, C++ and JavaScript. Every number in it was measured with a script or verified against the implementation's source, and every number that depends on hardware is marked as such.
It sits in Module 0 between Complexity Analysis, which teaches the counting model, and Your Language's Data Structures, which catalogues what each standard library gives you. The capstone asks you to measure everything claimed here on your own machine. Treat that as the real test of understanding: if you can predict the curve before you run the benchmark, you have the model.
When memory layout decides the winner
Two solutions with the same Big-O are not equal, and some problems hint that layout is the whole point. Learn to read the signals.
| If the problem or situation says… | Think of… |
|---|---|
| "in place", " extra space", "without allocating a new array" | Rotating, reversing or compacting a contiguous block; cyclic replacements; the first row/column as scratch space |
| "the array is huge", "millions of elements", "streaming" | Sequential access patterns, cache-friendly scans, avoiding pointer-per-element structures |
| "matrix", "grid", "2-D array" | Row-major vs column-major traversal; blocking/tiling; a flat n*m array instead of a list of lists |
| "design a hash map / hash set / LRU cache" | Open addressing vs chaining; load factor; the array-plus-linked-list combination and its pointer cost |
| "your solution is too slow" / a TLE with the right complexity | Constant factors: boxing, pointer chasing, random access, allocation inside the loop |
| "insert into the middle of a sorted sequence many times" | Shift cost of an array vs walk cost of a linked list — the array usually wins (Stroustrup's experiment, below) |
| "tiny ", "at most 16 elements", "inner loop of a hot path" | Linear scan over a few cache lines beats binary search, hashing and trees |
| "many threads update counters" | False sharing on one cache line; pad or shard the counters |
| "memory limit is tight", "out of memory with 10 million objects" | Per-object overhead: 28 bytes per Python int, 16 bytes per Java Integer; use typed/primitive arrays |
| "sort then scan is fast enough" | Sorting is cache-friendly; a sorted array plus a single pass can beat a hash set at scale |
Intuition and first principles
Bytes, words and addresses
Memory is one long array of bytes, numbered from zero. The number of a byte is its address. On a 64-bit machine addresses are 64-bit integers, which is why a pointer costs 8 bytes. A word is the natural unit the CPU moves in one register: 8 bytes on today's mainstream machines. An int32 occupies 4 consecutive bytes; a double occupies 8; a pointer occupies 8.
Everything a program stores lives at some address, and every data structure is a convention about which addresses hold what. The CPU can do two things with an address: load the bytes there into a register, or store a register's bytes there. There is no "follow the list" instruction and no "find the key" instruction; those are sequences of loads, and the time they take is the time the loads take.
Stack versus heap
The stack is a region that grows and shrinks with function calls. Local variables of known size live there; allocation is a single subtraction from the stack pointer and deallocation is free when the function returns. Because the stack is reused constantly, its top is almost always in the L1 cache. The heap is everything you allocate dynamically: new, malloc, every Python object, every Java object, every JavaScript object that escapes a function. Heap allocation is a call into an allocator that must find a free block, which costs tens to hundreds of nanoseconds, and heap objects can land anywhere, which is the root of the pointer-chasing problem below. The allocator itself is an algorithmic topic covered in Memory Allocators.
The practical rule: a structure whose elements are all in one heap block (an array) is one allocation and one address range; a structure with one heap block per element (a linked list, a tree of nodes, a list of boxed objects) is allocations scattered over the address space.
The array: address arithmetic
An array stores elements of a fixed size bytes contiguously starting at a base address . The address of element is
This single formula is why array indexing is and why it is also fast : a multiply and an add, then one load. Element 0 of a 6-element int32 array at base 0x1000 lives at 0x1000, element 5 at 0x1014; the whole array occupies 24 bytes. Because they are adjacent, loading element 0 brings elements 1 to 15 along for free, as the cache-line section shows.
The formula also explains the costs. Insertion at position must move elements one slot to the right so that the formula still holds for them: moves, in the worst case, but each move is a copy of adjacent bytes that the hardware handles very efficiently (memmove copies gigabytes per second). Deletion is the mirror image. Append is if there is spare capacity and when the block must be reallocated and copied.
Dynamic arrays and growth factors
A dynamic array (std::vector, ArrayList, Python list, a JavaScript Array) keeps a capacity larger than its size and grows the capacity geometrically when it runs out. Geometric growth is what makes appends amortised : if the capacity multiplies by a factor on each reallocation, the total bytes copied over appends is a geometric series bounded by . Arithmetic growth (add a fixed 100 slots each time) would copy bytes in total. The proof is in the Correctness section.
The factor is an implementation detail, and it varies more than people assume. These are the values in the current sources at the time of writing; all of them can change between versions:
| Implementation | Growth rule | Effective factor | Source |
|---|---|---|---|
CPython list | new_allocated = (newsize + (newsize >> 3) + 6) & ~3 | about 1.125x for large lists; pattern 0, 4, 8, 16, 24, 32, 40, 52, 64, 76, … | Objects/listobject.c, list_resize |
OpenJDK ArrayList | newLength(oldCapacity, minGrowth, oldCapacity >> 1) | 1.5x | java/util/ArrayList.java, grow |
libstdc++ std::vector | _M_check_len: grow by at least size() | 2x | bits/stl_vector.h |
MSVC STL std::vector | _Geometric = _Oldcapacity + _Oldcapacity / 2 | 1.5x | stl/inc/vector, _Calculate_growth |
V8 JSArray elements | old_capacity + (old_capacity >> 1) + 16 | 1.5x plus 16 slots | src/objects/js-objects.h, NewElementsCapacity |
Measured on CPython 3.14.6, an empty list that receives appends one at a time passes through capacities 4, 8, 16, 24, 32, 40, 52, 64, 76, 92, 108, 128, 148, 172, 200, 232, 268, 308 — the ratio between consecutive capacities settles around 1.15 and converges to 1.125. CPython's mild factor trades a little more copying for less wasted memory, which fits a language where every list slot is only a pointer. The 2x of libstdc++ minimises copies; the 1.5x of MSVC and Java is a compromise, sometimes justified by the observation that with a factor below the golden ratio, freed blocks from earlier reallocations can be coalesced to fit a later one.
Why you still call `reserve`
Amortised hides a constant: with factor 2 every element is copied on average once more after its first write, with factor 1.125 about eight times. When you know in advance, vector.reserve(n), new ArrayList<>(n) and [None] * n in Python turn those copies into zero and, more importantly, give you one contiguous block whose address never changes.
Pointers, references and pointer chasing
A pointer is an address stored as data. A reference in Java, Python or JavaScript is a pointer that the language manages for you — you cannot do arithmetic on it, but it costs the same 8 bytes (or 4 with compression) and it incurs the same load. A linked list node holds a value and a pointer to the next node; a tree node holds a value and two or more pointers; a Python list holds pointers to int objects that live elsewhere.
Pointer chasing is following a chain of such pointers: load node, read its next field, load that node, read its next, and so on. Each step depends on the result of the previous load, so the CPU cannot start the next load until the current one returns. If each node lives on a different cache line that is not in cache, each step pays a full memory latency. A sequential array scan, by contrast, has no such dependency: the addresses are known in advance, the hardware prefetcher streams them, and several loads are in flight at once.
This is the single most important mechanism in this lesson. pointer chasing with a cache miss per step costs about ns; sequential scanning costs about ns. That is the 30x–100x gap behind "same Big-O, different speed".
Mechanics
The cache hierarchy
Between the CPU core and DRAM sit several levels of cache: small, fast memories holding copies of recently used lines. Typical latencies for a current desktop or server core — typical and machine-dependent, so measure yours — are:
| Level | Typical size | Typical latency | Notes |
|---|---|---|---|
| L1 data | 32–64 KB per core | about 1 ns (4–5 cycles) | Split instruction/data; the stack top lives here |
| L2 | 0.5–2 MB per core | about 4 ns (12–16 cycles) | Private per core |
| L3 | 8–96 MB shared | about 10–20 ns (30–60 cycles) | Shared by all cores on a die |
| DRAM | gigabytes | about 60–100 ns | Plus queuing under load; worse across NUMA nodes |
The ratio from L1 to DRAM is around 100x. How Computers Work covers the hardware; here we care only about the consequence: the cost of a memory access depends on where the data is right now, and where it is depends on what you touched recently.
flowchart LR
CPU["Core<br/>registers"] -->|"~1 ns"| L1["L1 data<br/>32-64 KB"]
L1 -->|"~4 ns"| L2["L2<br/>0.5-2 MB"]
L2 -->|"~10-20 ns"| L3["L3 (shared)<br/>8-96 MB"]
L3 -->|"~60-100 ns"| DRAM["DRAM<br/>gigabytes"]
DRAM -->|"~100 us"| SSD["SSD / disk<br/>(virtual memory)"]
Cache lines and locality
Caches do not move single bytes. They move cache lines of 64 bytes (on all mainstream x86 and most ARM designs; a few Apple and IBM parts use 128). When you load the 4-byte int32 at 0x1004, the hardware fetches all 64 bytes from 0x1000 to 0x103F into L1. The next 15 integers of the array are now free.
Two kinds of locality make caches work. Spatial locality: if you touched address , you will probably touch soon — true for array scans, false for pointer chasing. Temporal locality: if you touched , you will probably touch again soon — true for loop counters, small lookup tables and the top of the stack. Data structures that respect both run at cache speed; structures that respect neither run at DRAM speed.
Rule of thumb
Think of every memory access as fetching 64 bytes. The question to ask of a data structure is: of the 64 bytes I just paid for, how many will I use before they are evicted? An int32 array uses 64 of 64. A linked list of int32 with two 8-byte pointers uses at most 20 of 64 and usually only one node per line.
Prefetching and strided access
Modern cores include a hardware prefetcher that recognises sequential and constant-stride access patterns and fetches the next lines before the program asks for them. This is why a sequential scan can run faster than the DRAM latency would suggest: the loads overlap. The prefetcher is defeated by patterns it cannot predict — random indices, pointer chasing, and strides larger than a page (4 KB), where it typically stops.
A stride experiment shows the cache line directly. Summing every -th int32 of a 256 MB array on the test machine gave:
| Stride (ints) | Bytes per step | Elements touched | Time | ns per touch |
|---|---|---|---|---|
| 1 | 4 | 67.1 M | 69 ms | 1.0 |
| 2 | 8 | 33.6 M | 42 ms | 1.3 |
| 4 | 16 | 16.8 M | 31 ms | 1.9 |
| 8 | 32 | 8.4 M | 27 ms | 3.2 |
| 16 | 64 | 4.2 M | 24 ms | 5.7 |
| 32 | 128 | 2.1 M | 22 ms | 10.6 |
Touching 16x fewer elements (stride 16, exactly one per cache line) made the loop less than 3x faster, because every cache line still had to be fetched. Once the stride reaches 64 bytes, each touch costs a whole line; the time is set by memory bandwidth, not by the number of additions. These values are indicative for one machine; the shape — flat cost per line, not per element — is universal.
Row-major versus column-major traversal
A 2-D array must be stored as a 1-D block. Row-major order (C, C++, Python lists of lists, NumPy default, JavaScript arrays of arrays) stores row 0 then row 1; element of an matrix sits at . Column-major (Fortran, MATLAB, Julia, most BLAS libraries) stores column 0 first. Traversing in the stored order touches consecutive addresses; traversing against it jumps bytes per step — one cache line per element once , and one TLB miss per element once exceeds a page.
Measured with a compiled C++ loop summing an int32 matrix both ways (best of three, MSVC /O2):
| N | Matrix size | Row-major | Column-major | Ratio |
|---|---|---|---|---|
| 1024 | 4 MB | 0.60 ms | 5.4 ms | 8.9x |
| 2048 | 16 MB | 2.5 ms | 48 ms | 19x |
| 4096 | 64 MB | 10.7 ms | 329 ms | 31x |
| 8192 | 256 MB | 47 ms | 1342 ms | 29x |
The ratio grows while the matrix stops fitting in each cache level and then saturates near 30x on this machine. Treat the number as indicative; the mechanism — same arithmetic, same Big-O, one version fetching 64 useful bytes per line and the other fetching 4 — is what you should remember. The classical fix is loop interchange (traverse in storage order) or tiling: process the matrix in blocks small enough that a block of both operands fits in cache. Matrix transposition and multiplication in every serious numeric library are tiled for exactly this reason.
Trace table: addresses and cache lines
Take a 6-element int32 array at base 0x1000. Each element is 4 bytes; the cache line is 64 bytes, so the line index is and the line starts at . Computed by script:
| i | address | line start | offset in line | line index |
|---|---|---|---|---|
| 0 | 0x1000 | 0x1000 | 0 | 64 |
| 1 | 0x1004 | 0x1000 | 4 | 64 |
| 2 | 0x1008 | 0x1000 | 8 | 64 |
| 3 | 0x100C | 0x1000 | 12 | 64 |
| 4 | 0x1010 | 0x1000 | 16 | 64 |
| 5 | 0x1014 | 0x1000 | 20 | 64 |
All six elements share one line: a scan costs one memory fetch. The same array at base 0x1038 — an alignment the allocator is free to give you — straddles two lines:
| i | address | line start | offset in line | line index |
|---|---|---|---|---|
| 0 | 0x1038 | 0x1000 | 56 | 64 |
| 1 | 0x103C | 0x1000 | 60 | 64 |
| 2 | 0x1040 | 0x1040 | 0 | 65 |
| 3 | 0x1044 | 0x1040 | 4 | 65 |
| 4 | 0x1048 | 0x1040 | 8 | 65 |
| 5 | 0x104C | 0x1040 | 12 | 65 |
Two fetches instead of one for the same data. This is why performance-sensitive code aligns hot arrays to 64 bytes (alignas(64) in C++, aligned_alloc, or a padded allocation).
Memory layout of hash maps
A hash map is an array plus a policy for collisions, and the two policies have very different layouts. Chaining keeps an array of bucket heads, each pointing to a linked list of entries: one allocation per entry, one pointer chase per collision, and a lookup touches at least two cache lines (bucket slot, then the node). Open addressing stores entries directly in the slot array and resolves collisions by probing to another slot: no per-entry allocation, and with linear probing the probe sequence stays inside one or two cache lines. The Hash Tables lesson covers the algorithms; here is what the four standard libraries actually lay out.
Python dict (CPython 3.6+) uses a compact layout: a small indices array of integers (1, 2, 4 or 8 bytes each depending on table size) that is probed with open addressing, plus a dense entries array of (hash, key, value) triples in insertion order. Lookup hashes the key, probes indices to find an entry number, then reads that entry. The compact layout is why dict preserves insertion order (guaranteed since Python 3.7), why iteration is a sequential scan of entries, and why memory dropped by roughly 20–25% compared with the pre-3.6 layout. The table resizes when two-thirds full.
Java HashMap uses chaining: a Node<K,V>[] table of power-of-two size, each Node holding int hash, K key, V value, Node next. The default load factor is 0.75. When a bucket's chain exceeds TREEIFY_THRESHOLD = 8 entries and the table has at least MIN_TREEIFY_CAPACITY = 64 slots, the chain is converted into a red-black tree of TreeNodes so that a flooded bucket costs instead of ; it reverts to a list below UNTREEIFY_THRESHOLD = 6. (Constants verified in OpenJDK java/util/HashMap.java.) Every entry is a separate heap object, so a lookup is at least two dependent loads plus the key object itself.
C++ std::unordered_map is required by the standard to expose buckets and to keep references to elements stable across rehashing, which in practice forces a node-based chaining design in libstdc++, libc++ and MSVC alike: a bucket array of pointers plus one heap node per element. Default max_load_factor is 1.0. It is the slowest of the four layouts per lookup and the reason "flat" open-addressing maps (Abseil flat_hash_map, Boost unordered_flat_map, Rust's hashbrown) exist.
V8 Map and Set use an ordered hash table: one flat backing array holding a bucket region followed by entries stored in insertion order as [key, value, chain-link] triples; deleted entries are tombstoned and compacted on rehash. The design (after Tyler Close's deterministic hash table) gives average operations and insertion-order iteration, which the ECMAScript specification requires for Map.
Trace table: slot layout for five keys
Insert keys 12, 20, 5, 29, 7 into a table of 8 slots with , computed by script.
Open addressing with linear probing:
| Insert | Home slot | Probes | Landed in | Table after insert |
|---|---|---|---|---|
| 12 | 4 | 0 | 4 | [_, _, _, _, 12, _, _, _] |
| 20 | 4 | 1 | 5 | [_, _, _, _, 12, 20, _, _] |
| 5 | 5 | 1 | 6 | [_, _, _, _, 12, 20, 5, _] |
| 29 | 5 | 2 | 7 | [_, _, _, _, 12, 20, 5, 29] |
| 7 | 7 | 1 | 0 | [7, _, _, _, 12, 20, 5, 29] |
The cluster in slots 4–7 shows primary clustering: 29 had to probe twice, and 7 had to wrap around. Every probe here stays inside one 64-byte line (8 slots of 8 bytes), so even the longest probe sequence is one cache fetch.
Chaining, same keys: bucket 4 → 12 → 20, bucket 5 → 5 → 29, bucket 7 → 7, the rest empty. Looking up 29 costs the bucket load, the 5 node load, then the 29 node load: three dependent memory accesses to three different heap addresses.
CPython-style compact dict, same keys and the same probing over the indices array:
| Structure | Contents |
|---|---|
indices (8 slots) | [4, _, _, _, 0, 1, 2, 3] |
entries (dense, insertion order) | (12, v12), (20, v20), (5, v5), (29, v29), (7, v7) |
The indices array carries only small integers (one byte each at this size), so the probe sequence is tiny, and the entries array is read sequentially during iteration.
flowchart LR
subgraph IDX["indices (open addressing, 1-byte each)"]
I0["0: 4"] ~~~ I1["1: _"] ~~~ I2["2: _"] ~~~ I3["3: _"] ~~~ I4["4: 0"] ~~~ I5["5: 1"] ~~~ I6["6: 2"] ~~~ I7["7: 3"]
end
subgraph ENT["entries (dense, insertion order, 24 bytes each)"]
E0["0: hash, 12, v12"] ~~~ E1["1: hash, 20, v20"] ~~~ E2["2: hash, 5, v5"] ~~~ E3["3: hash, 29, v29"] ~~~ E4["4: hash, 7, v7"]
end
I4 --> E0
I5 --> E1
I6 --> E2
I7 --> E3
I0 --> E4
Memory layout of trees
A binary search tree node holds a key, a value and two child pointers (plus a parent pointer and a colour bit in a red-black tree). Each node is a separate allocation of 32–48 bytes, so a tree of a million keys is a million scattered heap blocks, and a lookup is dependent loads. If the tree does not fit in cache, that is 20 memory latencies, well over a microsecond, versus one or two for a hash lookup. Measured on the test machine, std::map lookups cost 80 ns at and 915 ns at — the growth is the tree falling out of L2, then L3 — against 6 ns and 59 ns for std::unordered_map.
B-trees exist to fix exactly this. A B-tree node packs many keys — hundreds in a database page — into one contiguous block, so one memory (or disk) fetch narrows the search by a factor of hundreds instead of two. The height of a B-tree over a billion keys is 3 or 4. The in-memory relatives (B+-trees with cache-line-sized nodes, "cache-sensitive" search trees) apply the same idea at 64-byte granularity. See Indexing Deep Dive for how databases exploit this and Storage Engines for the LSM alternative.
flowchart TD
subgraph BST["Binary tree: 1 key per node, 20 pointer chases for 1M keys"]
A["50"] --> B["25"]
A --> C["75"]
B --> D["12"]
B --> E["37"]
end
subgraph BT["B-tree: hundreds of keys per node, 3-4 fetches for 1B keys"]
N1["12 | 25 | 37 | 50 | 62 | 75 | 87 ..."]
N1 --> N2["0..11 (block)"]
N1 --> N3["13..24 (block)"]
end
Object overhead per language
The "same" integer costs very different amounts of memory depending on the runtime. Measured on CPython 3.14.6 (64-bit Windows build) with sys.getsizeof:
| Python object | Bytes | Notes |
|---|---|---|
0, 1, any int below | 28 | 16-byte object header + size field + one 30-bit digit (4 bytes), padded |
| to | 32 | Two digits |
| 36 | Three digits | |
1.0 | 24 | Header + one C double |
[] | 56 | Header, size, capacity, pointer to the item buffer |
list(range(n)) | 56 + 8n | Exactly, when built from a known length; the item buffer holds 8-byte pointers only |
[] after appending 1000 items | 8856 | Over-allocated: 1100 slots for 1000 items |
() | 48; (1, 2, 3) is 72 | Tuples store items inline: 48 + 8 per item, no spare capacity |
{} | 64; 1000 int→int items is 36,952 | About 37 bytes per entry including the indices array |
set() | 216; 1000 ints is 32,984 | Open addressing, 16-byte slots, load factor 3/5 |
"", "a", "hello" | 41, 42, 46 | Compact ASCII: 41-byte header + 1 byte per character |
So a Python list of one million small ints costs bytes for the list plus bytes for the int objects — about 36 MB for 4 MB of information, a 9x overhead — except that CPython caches the ints from −5 to 256, so a list of a million small ints shares 262 objects. array('i') and NumPy store raw 4-byte values and remove the overhead entirely.
Java: every object has a header — 12 bytes on 64-bit HotSpot with compressed class pointers (the default), 16 without — and is padded to a multiple of 8 bytes. An Integer is 16 bytes (12 header + 4 payload); an int[] of is ; an Integer[] of is for the compressed references plus for the boxes, five times the primitive array. Integer.valueOf caches −128 to 127, so small boxed values are shared, and ArrayList<Integer> pays the boxing on every add and get. Project Lilliput (JEP 450, experimental compact headers, JDK 24+) shrinks the header to 8 bytes; check your JDK before quoting a number.
C++: std::vector<int> is 24 bytes of header (three pointers: begin, end, end-of-capacity; verified sizeof on MSVC) plus exactly 4 bytes per element and whatever spare capacity the growth policy left. A std::list<int> node is 24 bytes (two pointers + 4-byte value + 4 padding) plus allocator overhead of typically 16 bytes, so each 4-byte value costs around 40 bytes and one allocation.
JavaScript (V8): a Smi ("small integer", 31-bit with pointer compression) is stored directly in the slot; any other number is a boxed HeapNumber (a separate 8-byte double plus header). Arrays have elements kinds: PACKED_SMI_ELEMENTS (contiguous Smis, the fastest), PACKED_DOUBLE_ELEMENTS (unboxed doubles), PACKED_ELEMENTS (tagged pointers), and the HOLEY_ variants once an array has a gap. Transitions go one way — write a double into a Smi array and it stays a double array; create a hole with new Array(n) or arr[100] = x and it stays holey. Int32Array and the other typed arrays are raw contiguous buffers with none of this.
Struct of arrays versus array of structs
Store a million particles as an array of structs ({x, y, z, mass, velocity…} each) and a loop that updates only x loads every field of every particle: if the struct is 64 bytes, you use 4 of every 64 fetched. Store them as a struct of arrays (xs[], ys[], zs[]…) and the same loop streams a dense array of x values at full bandwidth and vectorises trivially. This is the design of columnar databases (Parquet, ClickHouse, DuckDB), of entity-component systems in game engines, and of NumPy and Pandas internally. The reverse holds too: a loop that uses every field of one record prefers array of structs, because one line brings the whole record. The question is always the same — of the 64 bytes fetched, how many will be used?
False sharing
Caches keep cores coherent at cache-line granularity: when core A writes a line, every other core's copy of that line is invalidated. If two threads increment two different counters that happen to share a 64-byte line, the line bounces between cores on every write and both threads slow to the speed of the coherence protocol — often 10x–50x slower than independent counters. This is false sharing. The fix is to pad each thread's hot variable to its own line (alignas(64) or std::hardware_destructive_interference_size in C++, @jdk.internal.vm.annotation.Contended in the JDK, striped counters such as Java's LongAdder). It is the first thing to suspect when a "lock-free" structure scales worse than a locked one; see Lock-Free Programming.
Alignment and padding
Hardware prefers an -byte scalar to live at an address divisible by : a 4-byte int at a multiple of 4, an 8-byte double at a multiple of 8. Compilers enforce this by inserting padding between struct fields and at the end, and the struct's own alignment is the largest alignment of its members. Field order therefore changes size. These sizes were verified by compiling with MSVC (/std:c++20); GCC and Clang on x86-64 Linux give the same values for these examples:
#include <cstdint>
#include <cstdio>
struct Padded { char tag; std::int32_t id; char flag; }; // 1 + 3 pad + 4 + 1 + 3 pad = 12
struct Packed { std::int32_t id; char tag; char flag; }; // 4 + 1 + 1 + 2 pad = 8
struct Mixed { char tag; double x; std::int32_t id; }; // 1 + 7 pad + 8 + 4 + 4 pad = 24
struct Reorder { double x; std::int32_t id; char tag; }; // 8 + 4 + 1 + 3 pad = 16
int main() {
static_assert(sizeof(Padded) == 12);
static_assert(sizeof(Packed) == 8);
static_assert(sizeof(Mixed) == 24);
static_assert(sizeof(Reorder) == 16);
static_assert(alignof(Mixed) == 8);
std::printf("Padded=%zu Packed=%zu Mixed=%zu Reorder=%zu\n", sizeof(Padded), sizeof(Packed), sizeof(Mixed), sizeof(Reorder));
return 0;
}
Ordering fields from largest to smallest alignment removes the interior padding. A 12-byte struct fits 5 per cache line; the 8-byte reordering fits 8. In an array of a hundred million records that is the difference between 1.2 GB and 800 MB and, more importantly, 60% more records per memory fetch.
What this means for algorithm choice
The lessons in the rest of this course state complexities. Here is how layout bends them in practice:
- Linear scan beats binary search for tiny . A sorted array of 16
int32s is one cache line. A linear scan is 16 predictable compares; a binary search is 4 compares with unpredictable branches. Measured in compiled C++ on the test machine, linear search won up to about and binary search won from (indicative; the crossover depends on element size, branch predictor and whether the compiler vectorises). This is whystd::sortand Timsort switch to insertion sort for small runs and why B-tree nodes are searched linearly or with SIMD. - Sort then scan can beat a hash set. Deduplicating or intersecting a hundred million integers with a hash set means a hundred million random probes into a table that does not fit in cache: one DRAM miss each. Sorting them is but every pass is sequential; a merge-sort pass streams at bandwidth. Databases pick hash join or sort-merge join based on exactly this trade-off (Query Planning).
- Timsort's design is cache design. Its minrun insertion sort works on 32–64 elements — a few cache lines — and its galloping merge mode skips ahead through a run with exponential then binary search, touching few lines when one run dominates. Both exploit the fact that runs are contiguous memory (Sorting & Searching).
insert(0, x)on a Python list is but it is amemmoveof pointers: measured 44x slower thanappendat , not the thousands-of-times you might expect from "20,000 operations versus 1", because moving 160 KB of adjacent pointers is nearly free compared with 20,000 scattered accesses.- An
ArrayDequebeats aLinkedListfor queues. Both are per operation; the ring buffer touches one line per 16 elements and the list touches one line and one allocation per element.
The ladder: linked list → array → array with binary search
The classic demonstration is Stroustrup's experiment (Bjarne Stroustrup, "Software Development for Infrastructure", IEEE Computer, January 2012, and his GoingNative 2012 keynote): generate random integers and insert each into its sorted position in a sequence, then remove them one by one at random positions. The textbook says the linked list should win — insertion once the position is found — and the vector should lose because of the shift. Measured here with MSVC /O2, inserting random integers in sorted order:
| n | vector, binary search + shift | vector, linear walk + shift | list, linear walk + link | list / vector (both walking) |
|---|---|---|---|---|
| 1,000 | 0.1 ms | 0.2 ms | 0.8 ms | 3.7x |
| 10,000 | 2.8 ms | 13.6 ms | 175 ms | 13x |
| 50,000 | 72 ms | 577 ms | 11,005 ms | 19x |
| 100,000 | 454 ms | 1,459 ms | 61,439 ms | 42x |
Rung 1 — linked list. Walk from the head comparing values ( pointer chases, each a likely cache miss), then splice a node in (, but a heap allocation). Total chases for inserts, each chase a dependent load.
Rung 2 — vector, linear walk. Same number of comparisons, but they stream through contiguous memory with the prefetcher ahead of you; then a memmove of the tail, which is a bandwidth-bound copy. The Big-O is identical to rung 1. The measured time is 13x–42x lower.
Rung 3 — vector, binary search + shift. std::lower_bound finds the position in ; the shift is still but is the only linear part left. Three to five times faster again than rung 2 at large . The remaining cost is pure memmove and could be attacked only by changing the structure (a B-tree-like blocked list, or a skip list).
| Rung | Finding the slot | Making room | Allocations | Cache behaviour |
|---|---|---|---|---|
| Linked list | dependent loads | relink | one per insert | one miss per visited node |
| Vector, linear | streamed compares | memmove | amortised | prefetched, bandwidth-bound |
| Vector, binary search | memmove | amortised | a few misses, then bandwidth |
The removal half of Stroustrup's experiment behaves the same way, for the same reason: finding the -th element of a list is a walk; finding it in a vector is address arithmetic.
The lesson is not "never use linked lists"
Linked lists win when you already hold a pointer to the position (an LRU cache's node, an intrusive list in a kernel), when elements are large and must not move, or when you need to splice whole sequences in . They lose whenever finding the position dominates, which is nearly every interview and most application code.
Correctness
Two claims in this lesson deserve proofs rather than assertions.
Claim 1: geometric growth gives amortised append; arithmetic growth does not.
Let the capacity multiply by at each reallocation and suppose appends have been performed, so the final capacity satisfies . The reallocations copied elements in total (each reallocation copies the previous capacity). This is a geometric series bounded by . Dividing by appends gives at most copies per append: 2 for , 3 for , 9 for . Each append therefore costs amortised, with a constant that grows as approaches 1 — exactly the trade-off the growth-factor table shows.
Equivalently, with the potential method of Complexity Analysis: define clamped at 0; a cheap append raises by a constant and a reallocation's copying is paid by the drop in .
Now let the capacity grow by a constant instead. The -th reallocation copies elements, and there are of them, so the total copying is , i.e. per append. Arithmetic growth is quadratic; this is not a constant-factor difference.
Claim 2: the address formula is an invariant, and insertion preserves it.
The array invariant is: for all , element is stored at . Insertion at position moves elements to positions — necessarily from the back to the front so no element is overwritten before it is read (memmove handles the overlap) — then writes the new element at . After the move, every old element is at , which is its new index times plus the base; elements below are untouched; the new element is at index . The invariant holds for all elements. Deletion is the reverse. Because the invariant holds, indexing remains a single multiply-add, and the cache analysis of a scan — consecutive indices, consecutive addresses — remains valid.
Complexity: counting cache misses, not just operations
Big-O in the RAM model counts operations. The external-memory model (Aggarwal and Vitter, 1988) counts block transfers of size between a fast memory of size and a slow memory. Replace "disk block" with "cache line" and int32s, and the model predicts everything measured above:
| Operation | RAM-model cost | Cache-line transfers (cold) | Why |
|---|---|---|---|
| Sequential scan of ints | 16 ints per 64-byte line, prefetched | ||
| Random-order scan of ints | (when cache) | every access a new line | |
| Linked-list traversal | one node per line, dependent loads | ||
| Binary search, sorted array | about | last 4 halvings are inside one line | |
| B-tree search, keys per node | compares | each node fetch narrows by | |
| Hash lookup, open addressing | expected | 1–2 | probe sequence stays in a line |
| Hash lookup, chaining | expected | 2–3 | bucket, node, key object |
| Row-major matrix sum | storage order | ||
| Column-major matrix sum (row-major storage) | one line per element, TLB misses too |
Space complexity has the same two faces. space for a million ints is 4 MB as int32[], 36 MB as a Python list of ints, 20 MB as Integer[], 40 MB as std::list<int>. Whether the structure fits in L2, L3 or only DRAM decides which column of the latency table applies — and, as the row-major measurements show, the ratio between good and bad layouts grows as the data falls out of each cache level. Constants matter most precisely when is large, which is where people assume Big-O takes over.
Implementation: measure sequential versus random access
The canonical experiment. Fill an array with integers, traverse it in index order, then traverse it again in a random permutation of the indices. Same , same additions, same result — only the order of addresses changes. The programs assert that both sums are equal (correctness) and print the timing ratio (which depends on your machine and is deliberately not asserted).
import random
import time
def traverse(data: list[int], order) -> int:
total = 0
for i in order:
total += data[i]
return total
def main() -> None:
n = 2_000_000
data = list(range(n)) # contiguous array of pointers to int objects
perm = list(range(n))
random.Random(42).shuffle(perm) # same n, same work, different order
traverse(data, range(n)) # warm-up
t0 = time.perf_counter()
s_seq = traverse(data, range(n))
t1 = time.perf_counter()
s_rand = traverse(data, perm)
t2 = time.perf_counter()
assert s_seq == s_rand == n * (n - 1) // 2
seq_ms, rand_ms = (t1 - t0) * 1e3, (t2 - t1) * 1e3
print(f"n={n}: sequential {seq_ms:.0f} ms, random {rand_ms:.0f} ms, ratio {rand_ms / seq_ms:.1f}x")
if __name__ == "__main__":
main()
import java.util.Random;
public class SeqVsRandom {
static long traverse(int[] data, int[] order) {
long total = 0;
for (int i : order) total += data[i];
return total;
}
public static void main(String[] args) {
int n = 4_000_000;
int[] data = new int[n];
int[] seq = new int[n];
int[] perm = new int[n];
for (int i = 0; i < n; i++) { data[i] = i; seq[i] = i; perm[i] = i; }
Random rng = new Random(42);
for (int i = n - 1; i > 0; i--) { // Fisher-Yates shuffle
int j = rng.nextInt(i + 1);
int t = perm[i]; perm[i] = perm[j]; perm[j] = t;
}
for (int w = 0; w < 3; w++) { traverse(data, seq); traverse(data, perm); } // JIT warm-up
long t0 = System.nanoTime();
long sSeq = traverse(data, seq);
long t1 = System.nanoTime();
long sRand = traverse(data, perm);
long t2 = System.nanoTime();
long expected = (long) n * (n - 1) / 2;
if (sSeq != expected || sRand != expected) throw new AssertionError("sums differ");
double seqMs = (t1 - t0) / 1e6, randMs = (t2 - t1) / 1e6;
System.out.printf("n=%d: sequential %.1f ms, random %.1f ms, ratio %.1fx%n", n, seqMs, randMs, randMs / seqMs);
}
}
#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <numeric>
#include <random>
#include <vector>
static std::int64_t traverse(const std::vector<std::int32_t>& data, const std::vector<std::uint32_t>& order) {
std::int64_t total = 0;
for (std::uint32_t i : order) total += data[i];
return total;
}
int main() {
const std::uint32_t n = 4'000'000;
std::vector<std::int32_t> data(n);
std::iota(data.begin(), data.end(), 0);
std::vector<std::uint32_t> seq(n), perm(n);
std::iota(seq.begin(), seq.end(), 0u);
perm = seq;
std::mt19937 rng(42);
std::shuffle(perm.begin(), perm.end(), rng);
using clk = std::chrono::steady_clock;
traverse(data, seq); traverse(data, perm); // warm-up
auto t0 = clk::now();
std::int64_t s_seq = traverse(data, seq);
auto t1 = clk::now();
std::int64_t s_rand = traverse(data, perm);
auto t2 = clk::now();
const std::int64_t expected = static_cast<std::int64_t>(n) * (n - 1) / 2;
assert(s_seq == expected && s_rand == expected);
double seq_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();
double rand_ms = std::chrono::duration<double, std::milli>(t2 - t1).count();
std::printf("n=%u: sequential %.1f ms, random %.1f ms, ratio %.1fx\n", n, seq_ms, rand_ms, rand_ms / seq_ms);
return 0;
}
import assert from "node:assert/strict";
function traverse(data: Int32Array, order: Uint32Array): number {
let total = 0;
for (let k = 0; k < order.length; k++) total += data[order[k]];
return total;
}
function main(): void {
const n = 4_000_000;
const data = new Int32Array(n);
const seq = new Uint32Array(n);
const perm = new Uint32Array(n);
for (let i = 0; i < n; i++) { data[i] = i; seq[i] = i; perm[i] = i; }
let state = 42; // small deterministic LCG for the shuffle
const next = () => (state = (state * 1664525 + 1013904223) >>> 0);
for (let i = n - 1; i > 0; i--) {
const j = next() % (i + 1);
const t = perm[i]; perm[i] = perm[j]; perm[j] = t;
}
for (let w = 0; w < 3; w++) { traverse(data, seq); traverse(data, perm); } // JIT warm-up
const t0 = performance.now();
const sSeq = traverse(data, seq);
const t1 = performance.now();
const sRand = traverse(data, perm);
const t2 = performance.now();
const expected = (n * (n - 1)) / 2; // 8e12 < 2^53, exact in a double
assert.equal(sSeq, expected);
assert.equal(sRand, expected);
const seqMs = t1 - t0, randMs = t2 - t1;
console.log(`n=${n}: sequential ${seqMs.toFixed(1)} ms, random ${randMs.toFixed(1)} ms, ratio ${(randMs / seqMs).toFixed(1)}x`);
}
main();
On the test machine the four programs printed ratios of 8.0x (Python, ), 6.8x (Java), 8.1x (C++) and 11.8x (TypeScript with typed arrays), all with for the compiled and JIT-compiled languages. Python's ratio is diluted by interpreter overhead on every iteration; its random traversal also chases a pointer from the list slot to the int object, which the sequential version does too but with the objects allocated in order. Expect different absolute numbers and a similar shape on your machine; the capstone makes this systematic.
Real-world uses
- Database indexes and pages. B-trees pack hundreds of keys per 4–16 KB page so that a lookup on a billion rows costs three or four page fetches; the same reasoning at cache-line scale drives in-memory index designs. Indexing Deep Dive, How Databases Work.
- Columnar storage and vectorised execution. Parquet, ClickHouse and DuckDB store each column contiguously (struct of arrays) so that scans and aggregates stream at memory bandwidth and vectorise; row stores (array of structs) win for point lookups that need a whole record. Storage Engines.
- Redis. Small hashes, lists and sorted sets are stored as compact contiguous encodings (listpack, formerly ziplist) and converted to pointer-based structures only past a size threshold, trading operations on tiny collections for far better cache behaviour and memory. Redis Internals.
- Language runtimes. CPython's compact dict, V8's elements kinds and Smi tagging, HotSpot's compressed oops and the JDK's
ArrayDequerecommendation overLinkedListare all layout decisions made for cache reasons. Memory Allocators covers howmalloctries to keep sequential allocations adjacent. - Operating systems. The Linux kernel's intrusive
list_headembeds list pointers inside the object so that a traversal that already touches the object pays no extra line; the page cache and the scheduler's run queues are tuned around cache-line and NUMA locality. CPU Scheduling, Virtual Memory. - Game engines and simulations. Entity-component systems store components in dense arrays per type (struct of arrays) so that "update all positions" is a linear scan.
- Concurrency. Padding to avoid false sharing is standard in lock-free queues, per-core counters and the JDK's
LongAdder. Lock-Free Programming, Concurrency Patterns. - Benchmarking methodology. Warm-up, medians and cache-state control exist because of everything above. Benchmarks.
Pitfalls and edge cases
- Benchmarking the first run. The first traversal pays page faults and cold caches; the JIT in Java and V8 has not compiled yet. Always warm up and report a median — see the capstone harness.
- Assuming
getsizeofis the whole story.sys.getsizeof([1, 2, 3])returns 80 (56 + 3 × 8) and says nothing about the three 28-byte ints. Usetracemallocor sum recursively for the true footprint. list(range(n))versus appending. The former allocates exactly slots; the latter over-allocates by up to about 12.5%. Neither is wrong, but memory measurements differ.- Holey JavaScript arrays.
new Array(1000)andarr[arr.length + 5] = xcreate holes; the array becomesHOLEY_ELEMENTSand every read must check for the hole. PreferArray.from({length: n}, ...),new Array(n).fill(0), or a typed array. - Doubles poisoning Smi arrays. One
1.5written into an integer array transitions it to double elements permanently; one object transitions it to tagged elements. Keep arrays monomorphic. - Java
LinkedListas a queue. It allocates a node per element and chases pointers;ArrayDequeis a ring buffer and is faster in every measured case.LinkedList.get(i)is . - C++
std::listandstd::unordered_mapby default. Usestd::vectorunless you need stable addresses or splicing, and consider a flat open-addressing map when lookups are hot. - Pointer-size assumptions. 8 bytes on 64-bit, 4 with JVM compressed oops or V8 pointer compression. Do not hard-code either.
- Iterating a 2-D structure the wrong way.
for c in range(cols): for r in range(rows): m[r][c]is the 30x trap in every language. Loop over the inner dimension innermost. - Alignment and SIMD. Unaligned loads are legal and usually cheap on x86, but a vector load that straddles a cache line costs two line fetches, and some ARM and older SIMD instructions require alignment.
- False sharing in "independent" counters.
counts[threadId]++with adjacentlongs is the textbook case: eight threads, one cache line. - Trusting a growth factor. CPython's was
newsize >> 3 + 3(3.8) and is now+ 6rounded to a multiple of 4 (3.9+); Java's was(oldCapacity * 3) / 2 + 1before Java 7. Cite the version if you quote a factor. - Measuring with the wrong . 4 MB of data fits in a modern L2 or L3; random access over it may look harmless. The cliff appears when the working set exceeds the last-level cache.
Variations
- Blocked and unrolled lists. Store 16–64 elements per node (an unrolled linked list) to get most of the cache behaviour of an array with cheap splicing;
std::dequeuses fixed-size blocks plus an index array, which is why it has indexing and push at both ends but worse locality thanvector. - B-trees and B+-trees. The blocked idea applied to search trees; the dominant disk and in-memory ordered index (Indexing Deep Dive).
- Open addressing variants. Linear probing (best locality, clustering), quadratic probing, Robin Hood hashing, Swiss tables (Abseil, hashbrown) that store 1-byte metadata per slot in a separate contiguous array and probe 16 slots per SIMD instruction — the direct descendants of the compact-dict idea.
- Struct of arrays, array of structs, and hybrids (array of structs of arrays, "AoSoA") used by SIMD code to get both locality within a record and vectorisation across records.
- Cache-oblivious algorithms (Frigo, Leiserson, Prokop, Ramachandran, 1999): recursive layouts such as the van Emde Boas tree layout that achieve optimal cache-line transfers without knowing the line size.
- Arena and slab allocation. Allocating all nodes of a tree or graph from one contiguous arena restores locality to pointer-based structures and makes freeing them a single operation; see Memory Allocators.
- Succinct and implicit structures. A binary heap stores a complete tree in an array with children at and — no pointers at all (Heaps); Eytzinger layout stores a sorted array in heap order so that binary search touches adjacent lines.
- Bit-packing. Bitsets and bitmaps store one element per bit, 512 per cache line (Bit Manipulation, Bloom Filters).
Practice ladder
Problems where the layout is the point. Each description is in our own words.
1. Move Zeroes (LeetCode 283) — easy. Push all zeros of an array to the end in place, preserving the order of the other elements. Teaches the write-pointer compaction idiom: one sequential pass, no extra array.
Hint
Keep an index w of where the next non-zero should go. Scan with r; when nums[r] != 0, swap it into w and advance w. Both pointers only move forward, so the pass is sequential.
2. Rotate Array (LeetCode 189) — medium. Rotate an array right by positions using extra space. Teaches that an in-place reversal is three cache-friendly sequential passes, while the "cyclic replacement" alternative jumps around.
Hint
Reverse the whole array, then reverse the first elements, then reverse the rest. Reduce modulo first.
Solution
def rotate(nums: list[int], k: int) -> None:
n = len(nums)
if n == 0:
return
k %= n
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
a = [1, 2, 3, 4, 5, 6, 7]
rotate(a, 3)
assert a == [5, 6, 7, 1, 2, 3, 4]
b = [1, 2]
rotate(b, 5)
assert b == [2, 1]
c: list[int] = []
rotate(c, 4)
assert c == []
print("rotate ok")
Time — exactly swaps across three passes — space . Each pass walks two pointers inward, so it touches each cache line twice at most.
3. Transpose Matrix (LeetCode 867) — easy. Return the transpose of an matrix. Teaches the row-major/column-major conflict head-on: one of the two matrices is necessarily traversed against its storage order, and large transposes are tiled.
Hint
Allocate the result and write out[c][r] = m[r][c]. Then ask: which side is strided? For a cache-friendly version, transpose in blocks.
Solution
def transpose(m: list[list[int]]) -> list[list[int]]:
rows, cols = len(m), len(m[0])
out = [[0] * rows for _ in range(cols)]
for r in range(rows): # read m sequentially, write out strided
for c in range(cols):
out[c][r] = m[r][c]
return out
def transpose_blocked(m: list[list[int]], block: int = 2) -> list[list[int]]:
"""Same result; each block of m and the matching block of out fit together in cache."""
rows, cols = len(m), len(m[0])
out = [[0] * rows for _ in range(cols)]
for r0 in range(0, rows, block):
for c0 in range(0, cols, block):
for r in range(r0, min(r0 + block, rows)):
for c in range(c0, min(c0 + block, cols)):
out[c][r] = m[r][c]
return out
m = [[1, 2, 3], [4, 5, 6]]
assert transpose(m) == [[1, 4], [2, 5], [3, 6]]
assert transpose_blocked(m) == transpose(m)
big = [[r * 7 + c for c in range(7)] for r in range(5)]
assert transpose_blocked(big, 3) == transpose(big)
print("transpose ok")
Time , space for the result. In Python the lists of lists add a pointer chase per row, so the blocked version only pays off in compiled code or NumPy; the idea is what matters.
4. Merge Sorted Array (LeetCode 88) — easy. Merge nums2 into nums1, which has enough trailing capacity, in place. Teaches filling from the back so that no element is shifted twice.
Hint
Three indices: the last valid element of each input and the last slot of nums1. Write the larger of the two tails into the last slot and move backwards.
5. Design HashSet (LeetCode 705) — easy. Build a set of integers in with add, remove and contains. Teaches that with a bounded key range a bitset or boolean array is the fastest hash table there is.
Hint
A bytearray(10**6 + 1) is a perfect hash with no collisions; a bitset is 125 KB. Then implement the general version with buckets to show you know the difference.
6. Design HashMap (LeetCode 706) — easy. Implement put, get and remove for integer keys without using the built-in map. Teaches the two layouts; implement open addressing with tombstones and explain why it is cache-friendlier than chaining.
Hint
Slot arrays keys, vals, state (empty, full, deleted). Probe linearly from hash(key) % capacity. Resize at load 0.5 by rebuilding without tombstones.
Solution
EMPTY, FULL, DELETED = 0, 1, 2
class MyHashMap:
"""Open addressing with linear probing; slots live in three parallel arrays."""
def __init__(self, capacity: int = 8) -> None:
self.cap = capacity
self.keys = [0] * capacity
self.vals = [0] * capacity
self.state = [EMPTY] * capacity
self.used = 0 # FULL + DELETED slots, controls resize
def _find(self, key: int) -> int:
"""Index of key if present, else index of the first EMPTY/DELETED slot on the probe path."""
i = (key * 2654435761) % self.cap # Knuth multiplicative hash
first_free = -1
while True:
s = self.state[i]
if s == FULL and self.keys[i] == key:
return i
if s == EMPTY:
return first_free if first_free != -1 else i
if s == DELETED and first_free == -1:
first_free = i
i = (i + 1) % self.cap
def _resize(self) -> None:
old = [(k, v) for k, v, s in zip(self.keys, self.vals, self.state) if s == FULL]
self.__init__(self.cap * 2)
for k, v in old:
self.put(k, v)
def put(self, key: int, value: int) -> None:
if (self.used + 1) * 2 > self.cap:
self._resize()
i = self._find(key)
if self.state[i] != FULL:
self.used += 1
self.keys[i], self.vals[i], self.state[i] = key, value, FULL
def get(self, key: int) -> int:
i = self._find(key)
return self.vals[i] if self.state[i] == FULL and self.keys[i] == key else -1
def remove(self, key: int) -> None:
i = self._find(key)
if self.state[i] == FULL and self.keys[i] == key:
self.state[i] = DELETED
m = MyHashMap()
m.put(1, 1)
m.put(2, 2)
assert m.get(1) == 1 and m.get(3) == -1
m.put(2, 1)
assert m.get(2) == 1
m.remove(2)
assert m.get(2) == -1
for k in range(1000):
m.put(k, k * k)
assert all(m.get(k) == k * k for k in range(1000))
for k in range(0, 1000, 2):
m.remove(k)
assert m.get(500) == -1 and m.get(501) == 501 * 501
print("hashmap ok")
Expected per operation at load factor at most 0.5; worst case for an adversarial key set. Every probe sequence walks adjacent slots, so it stays within one or two cache lines.
7. Spiral Matrix (LeetCode 54) — medium. Return the elements of an matrix in clockwise spiral order. Teaches boundary bookkeeping and that two of the four sides of each ring are traversed against storage order.
Hint
Maintain top, bottom, left, right. Walk the top row left to right, the right column top to bottom, then — only if rows remain — the bottom row right to left, and — only if columns remain — the left column bottom to top. Shrink the bounds.
Solution
def spiral_order(m: list[list[int]]) -> list[int]:
if not m or not m[0]:
return []
out: list[int] = []
top, bottom, left, right = 0, len(m) - 1, 0, len(m[0]) - 1
while top <= bottom and left <= right:
for c in range(left, right + 1): # top row: sequential
out.append(m[top][c])
for r in range(top + 1, bottom + 1): # right column: strided
out.append(m[r][right])
if top < bottom:
for c in range(right - 1, left - 1, -1): # bottom row, reversed
out.append(m[bottom][c])
if left < right:
for r in range(bottom - 1, top, -1): # left column, upwards
out.append(m[r][left])
top, bottom, left, right = top + 1, bottom - 1, left + 1, right - 1
return out
assert spiral_order([[1, 2, 3], [4, 5, 6], [7, 8, 9]]) == [1, 2, 3, 6, 9, 8, 7, 4, 5]
assert spiral_order([[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12]]) == [1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]
assert spiral_order([[7]]) == [7]
assert spiral_order([[1], [2], [3]]) == [1, 2, 3]
assert spiral_order([]) == []
print("spiral ok")
Time , each element visited once; space beyond the output. The two if guards prevent double-visiting the middle row or column of an odd-sized ring.
8. Set Matrix Zeroes (LeetCode 73) — medium. If a cell is zero, zero its entire row and column, in place with extra space. Teaches using the matrix's own first row and column as the marker arrays.
Hint
Record whether the first row and first column themselves need zeroing. Then use m[r][0] and m[0][c] as flags for the rest. Zero the interior from the flags, and finally handle the first row and column.
Solution
def set_zeroes(m: list[list[int]]) -> None:
rows, cols = len(m), len(m[0])
first_row_zero = any(m[0][c] == 0 for c in range(cols))
first_col_zero = any(m[r][0] == 0 for r in range(rows))
for r in range(1, rows): # mark: m[r][0] and m[0][c] become flags
for c in range(1, cols):
if m[r][c] == 0:
m[r][0] = 0
m[0][c] = 0
for r in range(1, rows): # apply to the interior, row-major
for c in range(1, cols):
if m[r][0] == 0 or m[0][c] == 0:
m[r][c] = 0
if first_row_zero:
for c in range(cols):
m[0][c] = 0
if first_col_zero:
for r in range(rows):
m[r][0] = 0
a = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
set_zeroes(a)
assert a == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]
b = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
set_zeroes(b)
assert b == [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]
c = [[1, 2], [3, 4]]
set_zeroes(c)
assert c == [[1, 2], [3, 4]]
print("set zeroes ok")
Time in two row-major passes, space . The two booleans exist because the cell m[0][0] would otherwise have to serve as the flag for both the first row and the first column.
9. Rotate Image (LeetCode 48) — medium. Rotate an matrix 90 degrees clockwise in place. Teaches that rotation = transpose + reverse rows, two passes that each stay close to storage order, versus the four-way cell swap that jumps between distant rows.
Hint
Transpose in place (swap m[i][j] with m[j][i] for j > i), then reverse each row.
10. LRU Cache (LeetCode 146) — medium. Get and put in with eviction of the least recently used key. Teaches the one place a linked list is the right answer — you already hold the node — and how a hash map and a list combine.
Hint
Hash map from key to node; doubly linked list in recency order with sentinel head and tail. get unlinks the node and relinks it at the front. In Python OrderedDict.move_to_end does exactly this.
Solution
class Node:
__slots__ = ("key", "val", "prev", "next")
def __init__(self, key: int = 0, val: int = 0) -> None:
self.key, self.val = key, val
self.prev: "Node | None" = None
self.next: "Node | None" = None
class LRUCache:
def __init__(self, capacity: int) -> None:
self.cap = capacity
self.map: dict[int, Node] = {}
self.head, self.tail = Node(), Node() # sentinels: head.next is most recent
self.head.next, self.tail.prev = self.tail, self.head
def _unlink(self, n: Node) -> None:
n.prev.next, n.next.prev = n.next, n.prev
def _push_front(self, n: Node) -> None:
n.next, n.prev = self.head.next, self.head
self.head.next.prev = n
self.head.next = n
def get(self, key: int) -> int:
n = self.map.get(key)
if n is None:
return -1
self._unlink(n)
self._push_front(n)
return n.val
def put(self, key: int, value: int) -> None:
n = self.map.get(key)
if n is not None:
n.val = value
self._unlink(n)
self._push_front(n)
return
if len(self.map) == self.cap:
lru = self.tail.prev
self._unlink(lru)
del self.map[lru.key]
n = Node(key, value)
self.map[key] = n
self._push_front(n)
c = LRUCache(2)
c.put(1, 1)
c.put(2, 2)
assert c.get(1) == 1
c.put(3, 3) # evicts 2
assert c.get(2) == -1
c.put(4, 4) # evicts 1
assert c.get(1) == -1 and c.get(3) == 3 and c.get(4) == 4
print("lru ok")
per operation. Memory: one dict entry plus one node (about 100 bytes in CPython even with __slots__) per key, so a cache of ten million small ints costs about a gigabyte — the kind of number this lesson should let you estimate before running out of RAM.
Common mistakes and interview follow-ups
"Your solution is . Why is it slow?" The expected answer names a constant factor with a mechanism: boxing (ArrayList<Integer>, Python ints), pointer chasing (linked structures, lists of lists), random access over a working set larger than cache, allocation inside the loop, or a strided traversal. Then propose the fix: a primitive/typed array, a flat matrix, loop interchange, reserve, or an open-addressing map.
"Why not a linked list? Insertion in the middle is ." Only after finding the position, which is pointer chases and dominates. A vector's shift is a memmove of adjacent bytes and is cheaper in practice for moderate (Stroustrup's experiment). Linked lists win when you already hold the node — LRU caches, intrusive kernel lists — or when elements must never move.
"How much memory does your Python solution use for integers?" About bytes for the list plus for the ints, roughly 360 MB; array('q') or NumPy brings it to 80 MB; a set of them is around 400–500 MB. Showing the arithmetic is the point.
"What if the matrix is ?" It does not fit in RAM (40 GB of int32), so you are now in external memory: tile the computation so that blocks fit in cache and in RAM, and traverse in storage order. Same reasoning as the 30x row/column ratio, one level down the hierarchy.
"Why does Java's HashMap convert buckets to trees?" To bound the worst case at under hash flooding, at the price of a heavier node. Follow-up: why is Python's dict not vulnerable in the same way? Randomised string hashing (SipHash) since 3.3 plus open addressing with perturbation.
"Would a hash set or sorting be faster to deduplicate a billion 32-bit integers?" A hash set of a billion entries is 8–16 GB and every insert is a cache miss; sorting (radix or in-place) streams the data a handful of times at bandwidth, then one pass removes duplicates. Sorting typically wins, and it is the approach a database's planner would pick for a large distinct.
"Design an array that supports push at both ends." A ring buffer (ArrayDeque, collections.deque uses 64-slot blocks) — not a linked list. Discuss growth (copy into a larger ring) and why indexing stays .
"How would you measure this rather than argue about it?" Warm up, repeat, take a median, vary across cache sizes, assert correctness, and pin the thread if you can. Then explain the curve you see — the capstone.
Quick quiz
1. A 6-element int32 array starts at address 0x1038. How many 64-byte cache lines does a full scan touch?
Answer
Two. Elements 0–1 occupy 0x1038–0x103F in the line starting at 0x1000; elements 2–5 occupy 0x1040–0x104F in the line starting at 0x1040. Aligning the array to 0x1040 would make it one.
2. Why is appending to a dynamic array amortised with geometric growth but with "add 100 slots each time"?
Answer
With geometric growth factor the total elements copied over appends is a geometric series bounded by , so each append pays a constant on average. With constant growth , the -th reallocation copies elements and there are of them, giving total copying, per append.
3. Two loops sum a 4096 × 4096 int32 matrix, one row by row, one column by column. Which is faster, by roughly how much, and why?
Answer
Row by row, by an order of magnitude (about 30x in our measurement, machine-dependent). Row-major storage makes the row loop touch 16 useful integers per 64-byte line with the prefetcher ahead of it; the column loop touches one integer per line and jumps 16 KB between accesses, defeating the prefetcher and thrashing the TLB.
4. In CPython, how many bytes do [], [0], and list(range(1000)) occupy, excluding the integers themselves?
Answer
56, 64 (56 + one 8-byte pointer slot — though appending one element to an empty list over-allocates to 4 slots, 88 bytes), and 8056 (56 + 1000 × 8) because list(range(n)) allocates exactly slots. Measured with sys.getsizeof on CPython 3.14.6.
5. Two threads each increment their own counter a billion times; the counters are adjacent longs in one array. Why is this slow and how do you fix it?
Answer
False sharing: both counters live in the same 64-byte line, so each write invalidates the other core's copy and the line ping-pongs through the coherence protocol. Pad each counter to its own cache line (alignas(64), @Contended) or use per-thread striped counters such as LongAdder.
Further reading and sources
- Ulrich Drepper, What Every Programmer Should Know About Memory (2007) — the definitive long-form treatment of caches, lines, prefetching and NUMA.
- Bjarne Stroustrup, "Software Development for Infrastructure", IEEE Computer, January 2012, and the GoingNative 2012 keynote "Why you should avoid linked lists" — the vector-versus-list experiment.
- Alok Aggarwal and Jeffrey Vitter, "The Input/Output Complexity of Sorting and Related Problems", Communications of the ACM, 1988 — the external-memory model.
- Matteo Frigo, Charles Leiserson, Harald Prokop, Sridhar Ramachandran, "Cache-Oblivious Algorithms", FOCS 1999.
- CPython source:
Objects/listobject.c(list_resize, growth pattern),Objects/dictobject.c(compact layout notes at the top of the file),Objects/listsort.txt(Timsort: minrun and galloping). - OpenJDK source:
java/util/ArrayList.java(grow),java/util/HashMap.java(treeify constants); JEP 450 (Compact Object Headers). - GCC libstdc++
bits/stl_vector.h(_M_check_len); Microsoft STLstl/inc/vector(_Calculate_growth). - V8 blog: "Elements kinds in V8" (Mathias Bynens, 2017) and "Pointer compression in V8" (2020);
src/objects/js-objects.h(NewElementsCapacity). - CLRS, Introduction to Algorithms, 4th ed., Chapter 17 (amortised analysis) and Chapter 18 (B-trees); Sedgewick & Wayne, Algorithms, 4th ed., §1.4 (resizing arrays).
- Agner Fog, Optimizing Software in C++, chapter on memory and cache; Intel 64 and IA-32 Architectures Optimization Reference Manual (prefetching, false sharing).
Module 0: Module overview · How to Use This Course · Complexity Analysis · Recursion & Induction · How Data Structures Live in Memory · Your Language's Data Structures · How to Solve Any Problem · Testing & Debugging Algorithms · Capstone · Course home
Previous: Recursion & Mathematical Induction · Next: Your Language's Data Structures
Related: Arrays & Strings · Linked Lists · Hash Tables · Trees · Advanced Data Structures · How Computers Work · Benchmarks