C06: Data structures, representation, and amortized cost

A. Prerequisites and observable goals#

Level: Degree core.

B. The central question: which operations should this representation make easy?#

A data structure is a representation together with supported operations and invariants. Start with a workload: indexed reads, append, search by key, insertion near a known element, minimum extraction, range queries, or sequential scanning. “Which structure is fastest?” has no answer until the operations, sizes, distributions, memory limits, and latency requirements are specified.

An array stores fixed-size elements contiguously. With base address $B$ and element size $s$, element $i$ begins at $B+is$ within the valid range. This explains constant-time indexing in the usual machine model. It does not mean every indexed access has the same wall time: cache state, paging, and memory dependencies affect execution. Inserting in the middle of a packed array generally shifts later elements. A dynamic array adds a capacity policy to support growth while retaining contiguity.

A singly linked list stores nodes with a value and a next reference. Finding the $i$th node requires traversal from an available starting node, usually $O(i)$. Inserting after a known node can be constant time, excluding allocation; finding that node is a separate cost. Removing an arbitrary singly linked node generally requires its predecessor. Doubly linked lists store previous links too, increasing bookkeeping and space but supporting more local operations. Their addresses may be scattered, which can make traversal expensive despite simple asymptotic counts.

C. Abstract behavior is not the same as one implementation#

A stack is last-in, first-out: push adds the next item, pop removes the most recently added remaining item. It supports nested work such as call processing, undo histories, and depth-first exploration. A queue is first-in, first-out and supports breadth-first exploration or ordered work arrival. Either abstraction can have several representations. A dynamic array often implements a stack well. A circular buffer or deque avoids repeatedly shifting every element when a queue removes from its front.

For a bounded circular queue with capacity $c$, a logical position can map to physical slot $i\bmod c$. Read and write indices alone can make empty and full states ambiguous if both are equal; use an explicit count, a reserved slot, or another documented encoding. A wraparound arithmetic trick does not prove thread safety. C10 adds synchronization to a bounded queue, keeping the abstract FIFO contract distinct from the concurrent implementation.

D. Why a costly resize can coexist with cheap amortized append#

Suppose a dynamic array doubles capacity when full. Individual append operations without growth cost constant time in the simplified model; a growth operation copies all existing elements and may cost $\Theta(n)$. Across $n$ appends from empty, copied element counts follow $1+2+4+\cdots<2n$. Adding $n$ ordinary writes gives less than a constant multiple of $n$ total operations. The amortized cost is therefore $O(1)$ per append.

This is not an average over a probability distribution. It bounds every allowed sequence of $n$ appends under the stated growth policy. It also does not promise low latency for each append: a single resize still causes a burst. A real-time system may preallocate or use another representation when the worst individual pause matters. If an array shrinks immediately whenever it becomes half full and grows at full capacity, alternating insertions and deletions can cause repeated large copies. Hysteresis, such as shrinking at one-quarter occupancy, separates the thresholds and avoids this simple thrashing pattern.

A potential-method proof makes the accounting explicit. One common dynamic-array analysis stores credit in the unused capacity or in a function of size and capacity; cheap operations accumulate credit that pays for a later copy. Credits are a mathematical accounting device, not a claim that the allocator literally saves CPU time for later.

E. Hashing maps keys to candidate locations, not unique identities#

A hash function maps a key to a hash value, which is mapped to a bucket. Equal keys must produce compatible hashes; different keys may collide. A collision is not a correctness failure if the structure compares actual keys and resolves it correctly. Separate chaining stores several key–value pairs in each bucket. Open addressing searches a sequence of slots inside a table. Deletion in open addressing often needs a tombstone or a carefully repaired probe sequence: replacing a removed slot with an ordinary empty marker can cause later searches to stop before a displaced key.

The load factor is $\alpha=n/m$ for $n$ stored items and $m$ buckets. Under suitable uniform-hashing assumptions, chaining has expected lookup cost $O(1+\alpha)$. A malicious or unlucky collection that all hashes to one bucket can require $\Theta(n)$ comparisons. Resizing controls load factor, not every possible collision pattern. A custom hash table handling untrusted keys may need additional defenses; the integer-key lab is not a hardened adversarial map.

With capacity four and keys $0,4,8$, the simple bucket rule $k\bmod4$ sends all three to bucket zero. Looking up 8 checks the stored key identities in that chain. Deleting 4 must retain 0 and 8; changing a value for an existing key must not increase the size. These are representation invariants that tests should target. A mutable key whose hash-relevant state changes while stored can become unreachable through its new hash; stable key semantics matter.

F. Choosing under realistic constraints#

For a small table scanned every frame, a contiguous vector may beat a hash table despite linear lookup, because the constant factors and locality favor it. For millions of independent key lookups, a suitable hash map may be preferable. For ordered range queries, a balanced search tree or sorted array may be more appropriate. For minimum-priority work, a heap supplies a different contract. C08 develops these alternatives.

Write an operation budget: item count, key size, read/write ratio, maximum burst, memory budget, and required ordering. Then compare correct implementations with the same workload. Distinguish construction time, steady-state lookup, resizing, and destruction. A benchmark that excludes all updates cannot justify a claim about an update-heavy engine system.

G. Independent practice#

F foundation C standard course work T transfer S optional stretch L runnable lab or project. Attempt the complete set before opening its solutions.

H. Complete solutions: C06#

Compare the first step where your work differs. A corrected answer is not yet an independent success.

Open every solution

"""C06.05: separate-chaining map with integer keys; educational only."""
class IntMap:
    def __init__(self, capacity: int = 4):
        if type(capacity) is not int or capacity < 1:
            raise ValueError("positive integer capacity required")
        self._buckets: list[list[tuple[int, object]]] = [
            [] for _ in range(capacity)]
        self._size = 0

    def __len__(self) -> int:
        return self._size

    def _bucket(self, key: int) -> list[tuple[int, object]]:
        if type(key) is not int:
            raise TypeError("integer keys only")
        return self._buckets[key % len(self._buckets)]

    def __setitem__(self, key: int, value: object) -> None:
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))
        self._size += 1
        if self._size > 2 * len(self._buckets):
            old = self._buckets
            self._buckets = [[] for _ in range(2 * len(old))]
            self._size = 0
            for chain in old:
                for k, v in chain:
                    self[k] = v

    def __getitem__(self, key: int) -> object:
        for k, value in self._bucket(key):
            if k == key:
                return value
        raise KeyError(key)

    def __delitem__(self, key: int) -> None:
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self._size -= 1
                return
        raise KeyError(key)

if __name__ == "__main__":
    m = IntMap()
    m[2], m[6] = "a", "b"
    del m[2]
    print(m[6], len(m))

I. Retention and readiness#

Retrieve the pigeonhole principle and the difference between an abstract contract and a representation. Advance when you can choose a structure from an operation budget, draw a collision or invalidation failure, and explain why amortized constant time does not promise constant latency.