Arrays, Dynamic Arrays and Hash Tables: Where O(1) Comes From and What It Costs

Contiguity is the whole argument

An array stores \(n\) elements in one block. Element \(i\) lives at base + i * width, so indexing is arithmetic, \(\Theta(1)\) worst case, no traversal. A linked list stores each element with a pointer to the next, anywhere in memory.

The textbook comparison says the list wins on insertion. In practice it usually does not, for a reason big-O cannot see: hardware moves memory in cache lines (64 bytes on x86-64), so scanning an array fetches many elements per miss. Chasing pointers pays a fresh, unpredictable miss per node. And the list’s celebrated \(\Theta(1)\) insertion assumes you already have the node; finding it costs \(\Theta(n)\) first.

Lists still earn their place when you hold interior positions and splice often, an LRU cache pairing a hash table with a doubly linked list is the standard example.

Why appending is amortised O(1)

A dynamic array keeps spare capacity. When it fills, allocate a bigger block, copy everything, free the old one. That copy is \(\Theta(n)\), so how is append \(O(1)\)?

Grow by a constant factor. Doubling from capacity 1, resizes happen at sizes \(1, 2, 4, \dots, 2^k \le n\), and the total number of elements ever copied over \(n\) appends is

So \(n\) appends cost less than \(3n\) elementary operations in total, \(O(n)\) for the whole sequence, hence \(O(1)\) amortised per append. Any growth factor \(c>1\) works: the copies sum to \(\tfrac{c}{c-1}n\). CPython over-allocates by roughly one-eighth, \(c \approx 1.125\), giving about \(9n\) copies in total, still linear, and it wastes far less memory than doubling.

Additive growth does not work: growing by a fixed 10 slots gives resizes at \(10, 20, 30, \dots\) and copies summing to \(\Theta(n^2/10)\). The geometric factor is load-bearing.

Note what amortised does not say: nothing about an individual append, one of which copies the whole array, the worst-versus-amortised distinction exactly.

Hash tables

A hash table stores key–value pairs in \(m\) slots, placing key \(k\) at index \(h(k) \bmod m\) for a hash function \(h\). If \(h\) scattered keys perfectly and no two collided, lookup would be one array index. Two keys will collide, with \(n\) keys in \(m\) slots and \(n>m\) it is forced, and long before that the birthday bound makes it near-certain, so the design is entirely about collision handling and about the load factor \(\alpha = n/m\).

Chaining puts colliding keys in a per-slot linked list (or small array). Under the simple uniform hashing assumption, an unsuccessful search examines \(1 + \alpha\) slots on average, so as long as \(\alpha\) is held below a constant by resizing, lookup is \(\Theta(1)\) expected. It degrades gracefully and tolerates \(\alpha > 1\).

Open addressing stores everything in the table itself: on collision, probe a deterministic sequence of alternative slots. It needs \(\alpha < 1\) and is more cache-friendly, since probes stay inside one array. Under uniform hashing the expected number of probes for an unsuccessful search is at most \(1/(1-\alpha)\):

That table is the whole design argument: cost is flat until \(\alpha\) approaches 1, then explodes. Implementations therefore resize at a fixed threshold, and deletion cannot simply blank a slot, because that would break probe chains; it writes a tombstone instead.

Worst case is \(\Theta(n)\) either way. If every key hashes to the same slot, lookup is a linear scan. Not hypothetical: it was a real denial-of-service vector against web frameworks, where an attacker sent form fields chosen to collide.

What Python actually gives you

dict and set are open-addressed tables. Since 3.6 dict keeps a compact array of entries in insertion order with a separate index array, order preservation became a language guarantee in 3.7, and it resizes when the used entries exceed two-thirds of the allocated slots. Since 3.3, string and bytes hashing is randomised per process with a seed (SipHash, PEP 456), which is why iteration order of a set of strings can change between runs and why the collision attack is defused.

Three practical consequences:

xs = list(range(1_000_000))
9_999 in xs                 # Theta(n) scan of a list

seen = set(xs)
9_999 in seen               # Theta(1) expected

# keys must be hashable: hashable roughly means immutable
d = {}
d[(1, 2)] = "ok"            # tuple of hashables: fine
try:
    d[[1, 2]] = "boom"      # list is mutable and unhashable
except TypeError as e:
    print(e)                # unhashable type: 'list'

# the canonical use: turn a nested loop into one pass
def two_sum(nums, target):
    """Indices of the first pair summing to target. Theta(n) expected."""
    seen_at = {}
    for i, x in enumerate(nums):
        if target - x in seen_at:
            return seen_at[target - x], i
        seen_at[x] = i
    return None

print(two_sum([2, 7, 11, 15], 26))   # (2, 3), since 11 + 15 = 26

Membership in a list is \(\Theta(n)\) and in a set is \(\Theta(1)\) expected, this single substitution fixes more accidentally quadratic ML data pipelines than any other change.

References

1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to Algorithms, 4th ed. MIT Press, 2022, ch. 11 for hashing, ch. 16 for amortised analysis.
2. Knuth, D. E. The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., §6.4. Addison-Wesley, 1998.
3. CPython source. Objects/listobject.c (over-allocation in list_resize) and Objects/dictobject.c.
4. Python Software Foundation. PEP 456, Secure and Interchangeable Hash Algorithm.
5. Python Software Foundation. TimeComplexity, Python Wiki.
6. Aumasson, J.-P., & Bernstein, D. J. SipHash: A Fast Short-Input PRF. INDOCRYPT 2012.