Data Structures

Every program of the last lesson held a bounded number of values at once: a guess, a counter, a running total, the string being built up. A program that has to keep many values, for example to sort a list of numbers or to remember which candidates have been ruled out, needs somewhere to store them and a way to reach any one of them. A data structure is such a place together with the operations for using it.

We compare algorithms by explicit models of cost, and refine an implementation only once the broad algorithmic choice has been made. For every algorithm there are two things to prove: that it terminates, and that it is correct, meaning that the output it returns is a correct output for its input in the sense of a computational problem.

Functions

From here on an algorithm is usually written as a function: a named piece of code that takes inputs, called its arguments, and returns an output.

def square(x):
    return x * x

print(square(7))       # 49
print(square(-3) + 1)  # 10

The line def square(x): names the function and its parameter x; the indented body is its code. A call square(7) binds the parameter x to the argument 7, runs the body, and evaluates to the value named by return, which ends the call at once. A function whose body finishes without reaching a return returns None. Names bound inside the body are local: they exist only while that call runs and do not disturb names of the same spelling elsewhere.

def smallest(a, b, c):
    target = a
    if b < target:
        target = b
    if c < target:
        target = c
    return target

target = 100
print(smallest(4, -2, 9))   # -2
print(target)              # 100, untouched by the call

A function may return several values at once as a tuple, and the caller may unpack them by multiple assignment: return p, q and then p, q = f(p, q).

In pseudocode we give a function a name and write its arguments in brackets, as in Fact(n), and return has its Python meaning.

Recursion

A function may call itself. The call f(n) then waits while f(n - 1) runs, and that call has its own local names, separate from those of the call that made it. The part of memory that keeps track of this is organised as a stack: each call places a frame holding its local names on top, and returning removes the top frame, so the most recent call is always the first to finish. The number of frames present at once is the depth of the recursion.

Recursion needs a case that does not call the function again, reached after finitely many calls; otherwise the stack grows until Python stops the program with a RecursionError.

def count_down(n):
    if n == 0:
        print('done')
    else:
        print(n)
        count_down(n - 1)

count_down(3)   # 3, 2, 1, done

Induction and Loop Invariants

For a statement $P(n)$ about every nonnegative integer, proof by induction has two parts: prove $P(0)$, then assume $P(n)$ for an arbitrary $n$ and use that assumption to prove $P(n+1)$. If the statement begins at $n = 1$, start with $P(1)$. The base case gives $P(0)$, and the step then gives $P(1)$, $P(2)$ and so on. The last lesson used this pattern for the closed forms of recurrences; we now use it for recursive algorithms and for loops.

An invariant plays the part of the induction hypothesis: initialisation is the base case, and maintenance is the step. It says nothing about whether the loop stops. That is proved separately by a decrementing function, often called a variant in this context.

One full round can be implemented as a loop: check whether Player One has received $(1, 1)$, let Player One move, check whether the opponent has received $(1, 1)$, then let the opponent move. Player One’s move is the square-producing cut:

Player One's Move
Input:  the numbers p, q of rows and columns of the retained rectangle.
Output: the rectangle after the move.

    if p > q then p ≝ q
    else if q > p then q ≝ p
    else p ≝ p − 1
    return p, q

def player(p, q):
    if p > q:
        p = q
    elif q > p:
        q = p
    else:
        p = p - 1   # reached only from a square
    return p, q

For a nonsquare starting position, the last branch is never reached under the winning strategy. The opponent may choose any legal cut; the proof above covers all such choices.

Recursive and Iterative Factorials

Recursive and iterative factorial functions show the connection between induction and invariants. Define $0! = 1$ and $n! = n \cdot (n-1)!$ for $n > 0$.

Recursive Factorial                    Iterative Factorial
Input:  n ∈ N₀.                        Input:  n ∈ N₀.
Output: n!.                            Output: n!.

    Fact(n):                               r ≝ 1
        if n = 0 then return 1             for j ≝ 1 to n do r ≝ r · j
        else return n · Fact(n − 1)        return r

The recursive version returns $1$ at $n = 0$ and otherwise returns $n \cdot \mathrm{Fact}(n-1)$; induction on $n$ proves it correct, the base case being the first branch and the step the second. The iterative version begins with $r = 1$ and multiplies $r$ by $j$ for $j = 1, \ldots, n$. Before iteration $j$ the invariant is $r = (j-1)!$; after the multiplication it becomes $r = j!$, so at exit $r = n!$. The variant $n - j + 1$ decreases to zero.

def fact_recursive(n):
    if n == 0:
        return 1
    return n * fact_recursive(n - 1)

def fact_iterative(n):
    r = 1
    for j in range(1, n + 1):
        r = r * j
    return r

print(fact_recursive(10), fact_iterative(10))   # 3628800 3628800

The recursive version has depth $n + 1$: the call for $n$ waits on the call for $n - 1$, down to $0$. The iterative version uses a single frame. Python integers have no fixed size, so both return $n!$ exactly however large it is. A product of large integers is then not an elementary operation, and costs what the schoolbook bound says.

def power(a, n):
    result, base, e = 1, a, n
    while e > 0:
        if e % 2 == 1:
            result = result * base
        base = base * base
        e = e // 2
    return result

Measuring Cost

A program can spend most of its running time in a small part of its code. Choosing a better algorithm for that part usually does more than rewriting individual instructions, and much of the low-level rewriting is done automatically in any case by the software that translates a program into machine instructions. Costs other than time and memory can matter too, energy and money among them. For example, a “Penny Sort” measure asks how many externally stored records can be sorted for a US cent, after the purchase cost of a fixed machine is spread over an assumed working life. That measure combines hardware cost and algorithm throughput.

The running time of the last lesson counted elementary operations. We also measure memory.

Storage may be released and reused later, which is why the footprint is a maximum and not a cumulative total. In a conventional model allocating or touching a memory cell costs at least one operation, so an algorithm’s footprint cannot exceed a constant multiple of its running time. This claim depends on the model, and it does not say that every algorithm uses as much space as time.

The unit-cost assumption has to be stated with care. A comparison of two strings is not necessarily a single operation: it may inspect many characters. A comparison of two integers of bounded size is commonly counted as one operation, but for arbitrarily large integers or variable-length records the cost must be stated.

Lower and Two-Sided Bounds

Landau’s $O$ from the last lesson is an upper bound. It has a lower counterpart, and the two together give a two-sided bound.

As with $O$, the equals sign is shorthand for membership of a set of functions, not equality of functions. The last lesson wrote $f = o(g)$, read ”$f$ grows strictly more slowly than $g$”, when $f(n)/g(n)$ tends to zero. Written out without limits: $g(n) > 0$ from some point on, and for every $\varepsilon > 0$ there is an $n_0$ with $f(n) \leqslant \varepsilon\, g(n)$ for every $n \geqslant n_0$. This is stronger than $f = O(g)$, since the constant multiplier can be made as small as we wish by taking $n$ large enough.

The growth rates met most often are, from slowest to fastest,

Logarithm bases differ only by a constant factor, since $\log_a n = \log_b n / \log_b a$ by the change of base; so $\Theta(\log_2 n)$ and $\Theta(\log_{10} n)$ are the same class and the base is usually left off.

Lower Bounds

The comparison model of computation acts on a set of comparable objects. The objects are treated as black boxes supporting only binary tests called comparisons, namely $<$, $\leqslant$, $>$, $\geqslant$, $=$ and $\neq$: each takes two objects and returns True or False according to their relative order. Nothing else about the objects may be inspected, so an algorithm in this model learns about its input only through the answers to comparisons, and its cost is counted as the number of comparisons it makes.

An upper bound is about one algorithm, and a lower bound is about every algorithm for the problem. A lower bound therefore has to fix a model, which lists the operations an algorithm may use.

A second proof uses an adversary, an imagined opponent who may change the input as long as every answer already given stays true.

The scan in pseudocode and in Python:

Position of the Maximum
Input:  a sequence T[0], …, T[n − 1] of comparable elements, n ⩾ 1.
Output: an index k with T[k] maximal.

    k ≝ 0
    for i ≝ 1 to n − 1 do
        if T[i] > T[k] then k ≝ i
    return k

def arg_max(T):
    k = 0
    for i in range(1, len(T)):
        if T[i] > T[k]:
            k = i
    return k

print(arg_max((3, 9, 2, 9, 4)))   # 1

Python’s len(T) gives the length of a tuple, as it does for a string, and T[i] its entry at position i.

The Word-RAM Model

To calculate the resources an algorithm uses we need to say how long a computer takes to perform basic operations. Fixing such a set of operations gives a model of computation, on which the analysis is then based. We use the $w$-bit Word-RAM model, which treats a computer as a random-access array of machine words called memory, together with a processor that performs operations on that memory.

A machine word of $w$ bits can name at most $2^w$ addresses, so the processor can read and write at most $2^w$ locations of memory. When a problem’s input occupies $n$ machine words we therefore always assume a word size of $w > \log_2 n$ bits, or the machine could not reach all of its input. For comparison, a Word-RAM model of a byte-addressable $64$-bit machine allows inputs of up to about $10^{10}$ gigabytes.

Arrays

An array is a fixed number of storage slots in a row, numbered from $0$, any of which may be read or written in a single elementary operation. The $i$th slot of an array $p$ is written $p[i]$. In the Word-RAM an array of $n$ words is a block of $n$ consecutive addresses, and reaching $p[i]$ means reading the address of $p[0]$ plus $i$: one addition and one read, whatever $i$ is and whatever the length of $p$.

Python Lists

Python’s counterpart of an array is a list, written in square brackets. A list is a sequence like a tuple, but its entries may be changed.

p = [3, 1, 4, 1, 5]
print(len(p), p[0], p[4])   # 5 3 5
p[1] = 9
print(p)                    # [3, 9, 4, 1, 5]

q = [True] * 4              # [True, True, True, True]
r = [None] * 3              # [None, None, None]

Positions are numbered from $0$, as they are for strings, and p[i] = x writes to position i. The expression [x] * n builds a list of n copies of x. Several further operations will be used below.

1. p.append(x) adds x at the end, and p.pop() removes the last entry and returns it; p.pop(i) removes and returns the entry at position i.
2. The slice p[i:j] is a new list holding the entries at positions i up to but not including j, with the same convention as for strings; p[i:] runs to the end and p[:j] starts at the beginning. Building a slice copies its $j - i$ entries.
3. p + q is a new list holding the entries of p followed by those of q.
4. The comprehension [f(a) for a in X] builds the list of values f(a) as a runs through X.
5. x is None tests whether x is the object None.

Unlike a tuple, a list can grow and shrink; how Python does this is described under dynamic arrays below. Used with a fixed length it behaves as an array.

Listing the Primes

Deciding whether one number is prime was a decision problem; listing the primes up to a bound is a general discrete computational problem. It is the first problem here whose best algorithm uses an array, and it has a much faster algorithm than testing each number for primality.

List of Prime Numbers
Input: n ∈ N.
Task:  compute all prime numbers p with p ⩽ n.

Running the trial-division test on each of $2, \ldots, n$ in turn settles it in $O(n\sqrt{n})$ operations. The sieve of Eratosthenes does better by never testing divisibility at all: it writes down every candidate, then crosses out the multiples of each survivor in turn. It uses an array $p$ indexed by $0, \ldots, n$.

The Sieve of Eratosthenes
Input:  n ∈ N.
Output: all prime numbers less than or equal to n.

    for i ≝ 2 to n do p[i] ≝ "yes"
    for i ≝ 2 to n do
        if p[i] = "yes" then
            output i
            for j ≝ i to ⌊n / i⌋ do p[i · j] ≝ "no"

The running time depends on the total work of the inner loops, which is a sum of harmonic numbers, which have no closed form. What we need instead is a bound on them. The lower bound is not needed for the sieve; it is used for quicksort in the next lesson.

In Python the array $p$ is a list of n + 1 entries, True for “yes” and False for “no”; positions $0$ and $1$ are never read.

def sieve(n):
    p = [True] * (n + 1)
    primes = []
    for i in range(2, n + 1):
        if p[i]:
            primes.append(i)
            for j in range(i, n // i + 1):
                p[i * j] = False
    return primes

print(sieve(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Data Structures and Interfaces

A data structure is a way to store a non-constant amount of data, supporting a set of operations to interact with that data. The set of operations a data structure supports is its interface. Many data structures may support the same interface and differ in the cost of each operation, and many problems become easy once the data are stored in a suitable structure.

The most primitive data structure native to the Word-RAM is the static array: a contiguous sequence of words reserved in memory, supporting the static sequence interface.

1. StaticArray(n): allocate a new static array of size $n$, every entry initialised to $0$, in $\Theta(n)$ time.
2. get_at(i): return the word stored at index $i$, in $\Theta(1)$ time.
3. set_at(i, x): write the word $x$ to index $i$, in $\Theta(1)$ time.

The operations get_at(i) and set_at(i, x) run in constant time because every item of the array has the same size, one machine word. To store a larger object at an index, the machine word there is read as the memory address of a larger piece of memory holding the object. A Python tuple is like a static array without set_at(i, x).

Classes

Python writes a data structure as a class: a bundle of stored values, called attributes, together with the functions that act on them, called methods.

class Counter:
    def __init__(self, start):
        self.value = start

    def increment(self):
        self.value = self.value + 1

    def __len__(self):
        return self.value

c = Counter(5)
c.increment()
print(c.value, len(c))   # 6 6

Calling Counter(5) creates a new object of the class and runs __init__ on it, with self bound to the new object and start to 5; the assignment self.value = start creates the attribute value. A call c.increment() runs the method with self bound to c. A few method names are special: len(c) calls c.__len__(), and a for loop over c calls c.__iter__().

Inside a method, yield x hands x to the for loop that is running over the object, then carries on from the same point when the loop asks for the next value; yield from X hands on every value of X in turn. This is how range produces its entries one at a time. The statement raise IndexError stops the program with an error naming a bad index, and assert test stops it with an error if test is False.

A class may be built on another: class B(A): gives B every method of A, and any method B defines with the same name replaces the one from A. Inside B, super().__init__() runs the __init__ of A.

A Static Array in Python

Python has no static array, so we imitate one with a list whose length we never change.

class StaticArray:
    def __init__(self, n):
        self.data = [None] * n

    def get_at(self, i):
        if not (0 <= i < len(self.data)): raise IndexError
        return self.data[i]

    def set_at(self, i, x):
        if not (0 <= i < len(self.data)): raise IndexError
        self.data[i] = x

Birthday Matching

Given the students of a class, each with a name and a birthday, we want two students who share a birthday, or a report that there are none. The algorithm keeps a record of the students seen so far, and checks each new student against it before adding them.

Birthday Match
Input:  n students, each a pair (name, birthday).
Output: the names of two students with the same birthday, or None.

    record ≝ a static array of length n
    for k ≝ 0 to n − 1 do
        (name₁, bday₁) ≝ student k
        for i ≝ 0 to k − 1 do
            (name₂, bday₂) ≝ record[i]
            if bday₁ = bday₂ then return (name₁, name₂)
        record[k] ≝ (name₁, bday₁)
    return None

def birthday_match(students):
    # students: tuple of (name, bday) tuples
    n = len(students)                          # O(1)
    record = StaticArray(n)                    # O(n)
    for k in range(n):                         # n passes
        (name1, bday1) = students[k]           # O(1)
        for i in range(k):                     # k passes: check the record
            (name2, bday2) = record.get_at(i)  # O(1)
            if bday1 == bday2:                 # O(1)
                return (name1, name2)          # O(1)
        record.set_at(k, (name1, bday1))       # O(1)
    return None                                # O(1)

print(birthday_match((('Ada', 'Dec 10'), ('Alan', 'Jun 23'), ('Emmy', 'Mar 23'), ('Kurt', 'Jun 23'))))
# ('Kurt', 'Alan')

We assume that each name and each birthday fits into a constant number of machine words, so that one student’s information can be read and compared in constant time. This allows names and birthdays of $O(w)$ characters from a fixed alphabet, and since $w > \log_2 n$ it still allows every student’s information to be distinct.

Every line then takes constant time except three. Building record takes $\Theta(n)$ time; the outer loop makes at most $n$ passes; and the inner loop on pass $k$ runs through the $k$ entries already in the record. The running time is therefore at most

using the sum of an arithmetic progression. This is quadratic in $n$. A different data structure for the record does better, and the hashing section at the end of this chapter gives one.

Sequences and Sets

We use two interfaces, which differ in what decides the order of the stored items.

Sequences maintain a collection of items in an extrinsic order: each stored item has a rank in the sequence, including a first item and a last item. Extrinsic means that the first item is first not because of what the item is, but because some external party put it there. An iterable below is anything a for loop can run over, such as a tuple, a string, a list or a range.

The insert and delete operations change the rank of every item after the one inserted or deleted. Two restricted forms of a sequence have names of their own.

The call stack of the functions section is a stack in this sense. With a Python list, append and pop() are insert_last and delete_last.

Sets, by contrast, maintain a collection of items based on an intrinsic property of what the items are, usually a unique key x.key attached to each item x. Sets generalise dictionaries and other databases queried by content.

The find operations return None if no qualifying item exists. In Python an item with a key can be an object of a small class:

class Item:
    def __init__(self, key, value):
        self.key = key
        self.value = value

We now give three data structures for the sequence interface. None of them supports insertion or deletion at an arbitrary rank in less than linear time.

Array Sequences

Computer memory is a finite resource. On a modern computer many running programs share the same main memory, so the operating system assigns a fixed range of memory addresses to each of them. When a program asks to store a variable it must say how much memory, how many bits, the variable needs; the operating system finds that much free memory in the program’s assigned range and reserves it, or allocates it, until it is no longer needed. Python hides memory management from the programmer, but whenever Python is asked to store something it makes such a request, for a fixed amount of memory, behind the scenes.

Now suppose a program wants to store two arrays, each of ten $64$-bit words. It makes two requests, for $640$ bits each, and the operating system might reserve the first ten words of the program’s range for the first array $A$ and the next ten for the second array $B$. Later an eleventh word $w$ has to be added to $A$, and there is no room next to $A$: the start of the range is to its left, and $B$ is to its right. One could shift $B$ right to make room, but much other data may already be reserved beyond $B$ and would have to move too. It is better to request eleven new words, copy $A$ into the start of the new allocation, store $w$ at the end, and release the old ten words for later requests.

Memory itself is one large fixed-length array, from which the operating system allocates. Implementing a sequence with an array, so that index $i$ of the array holds the item of rank $i$, makes get_at and set_at take $O(1)$ time by random access. Inserting or deleting, however, means moving items and resizing the array, and these operations take linear time in the worst case.

class Array_Seq:
    def __init__(self):                     # O(1)
        self.A = []
        self.size = 0

    def __len__(self): return self.size     # O(1)
    def __iter__(self): yield from self.A   # O(n) iter_seq

    def build(self, X):                     # O(n)
        self.A = [a for a in X]             # stands in for a static array
        self.size = len(self.A)

    def get_at(self, i): return self.A[i]   # O(1)
    def set_at(self, i, x): self.A[i] = x   # O(1)

    def _copy_forward(self, i, n, A, j):    # O(n)
        for k in range(n):
            A[j + k] = self.A[i + k]

    def _copy_backward(self, i, n, A, j):   # O(n)
        for k in range(n - 1, -1, -1):
            A[j + k] = self.A[i + k]

    def insert_at(self, i, x):              # O(n)
        n = len(self)
        A = [None] * (n + 1)
        self._copy_forward(0, i, A, 0)
        A[i] = x
        self._copy_forward(i, n - i, A, i + 1)
        self.build(A)

    def delete_at(self, i):                 # O(n)
        n = len(self)
        A = [None] * (n - 1)
        self._copy_forward(0, i, A, 0)
        x = self.A[i]
        self._copy_forward(i + 1, n - i - 1, A, i)
        self.build(A)
        return x

    def insert_first(self, x): self.insert_at(0, x)             # O(n)
    def delete_first(self): return self.delete_at(0)            # O(n)
    def insert_last(self, x): self.insert_at(len(self), x)      # O(n)
    def delete_last(self): return self.delete_at(len(self) - 1) # O(n)

_copy_forward(i, n, A, j) copies the $n$ items starting at index $i$ into the array A starting at index $j$, from left to right; _copy_backward copies the same items from right to left, which matters when source and destination overlap. A method name starting with an underscore is a convention for “used only inside the class”.

In a sorted array, whose items are arranged in the order of their keys, an item can be found far faster than by scanning, by the bisection of the last lesson; binary search in the next lesson makes this precise. Inserting an object while preserving the order is then harder, and costs $O(n)$ time. Deleting an element, even when its index is known, also costs $O(n)$ time if the array is to have no gaps and keep the order of the remaining elements.

Linked Lists

In a linked list, inserting or deleting an item does not move the others. Its items are kept in a certain order, as in an array, but they can be stored anywhere in memory, in places independent of one another. With each item we store a reference to the place of the next item, its successor; for the last item this reference is None, which marks the end of the list. One further reference to the first item, the head, is needed to reach the list at all.

Linked lists can be singly or doubly linked. In a doubly linked list each item also stores a reference to its predecessor, and the list keeps a reference to its last item, the tail. This allows an item whose place is known to be deleted with a number of steps bounded by a constant independent of the length of the list: the running time is $O(1)$.

The Python below is a singly linked list. A node holds an item and a reference next; later_node(i) walks $i$ steps along the list.

class Linked_List_Node:
    def __init__(self, x):                  # O(1)
        self.item = x
        self.next = None

    def later_node(self, i):                # O(i)
        if i == 0: return self
        assert self.next
        return self.next.later_node(i - 1)

class Linked_List_Seq:
    def __init__(self):                     # O(1)
        self.head = None
        self.size = 0

    def __len__(self): return self.size     # O(1)

    def __iter__(self):                     # O(n) iter_seq
        node = self.head
        while node:
            yield node.item
            node = node.next

    def build(self, X):                     # O(n)
        for a in reversed(X):
            self.insert_first(a)

    def get_at(self, i):                    # O(i)
        node = self.head.later_node(i)
        return node.item

    def set_at(self, i, x):                 # O(i)
        node = self.head.later_node(i)
        node.item = x

    def insert_first(self, x):              # O(1)
        new_node = Linked_List_Node(x)
        new_node.next = self.head
        self.head = new_node
        self.size += 1

    def delete_first(self):                 # O(1)
        x = self.head.item
        self.head = self.head.next
        self.size -= 1
        return x

    def insert_at(self, i, x):              # O(i)
        if i == 0:
            self.insert_first(x)
            return
        new_node = Linked_List_Node(x)
        node = self.head.later_node(i - 1)
        new_node.next = node.next
        node.next = new_node
        self.size += 1

    def delete_at(self, i):                 # O(i)
        if i == 0:
            return self.delete_first()
        node = self.head.later_node(i - 1)
        x = node.next.item
        node.next = node.next.next
        self.size -= 1
        return x

    def insert_last(self, x): self.insert_at(len(self), x)       # O(n)
    def delete_last(self): return self.delete_at(len(self) - 1)  # O(n)

reversed(X) runs through X from its last entry to its first, so that inserting each at the front leaves them in their original order; a test while node: holds as long as node is not None.

Linked lists have a disadvantage: bisection cannot be applied to them, since reaching the middle item means walking to it. Scanning a linked list is also slower than scanning an array, by a constant factor only, because today’s computers reach consecutive storage places substantially faster than places far apart.

Dynamic Arrays

The array sequence’s dynamic operations take time linear in the length of the array. One way to add items without paying a linear transfer cost every time is to over-allocate: request more space than the array currently needs, so that inserting an item means writing it into the next empty slot. This trades a little extra space for constant-time insertion. Any extra allocation is bounded, however; repeated insertions eventually fill it, and the array must be reallocated and copied again. Extra space reserved also means less space for the rest of the program.

Python does not append to the end of a list in worst-case $O(1)$ time. Sometimes appending to a Python list requires $O(n)$ time to transfer the array to a larger allocation, so sometimes appending takes linear time. Allocating extra space in the right way guarantees that any sequence of $n$ insertions takes $O(n)$ time in total, because the linear-time transfers happen rarely, so insertion takes $O(1)$ time per insertion on average over the sequence.

The cost of an expensive operation is amortized, that is spread, across the many cheap ones. To achieve amortized constant-time insertion at the end of an array, the strategy is to allocate extra space in proportion to the size of the array stored. Allocating $\Theta(n)$ extra space ensures that a linear number of insertions must occur before an insertion overflows the allocation. A typical implementation allocates double the space needed for the current array, which is called table doubling; any constant fraction of extra space achieves the same bound. The list implementation of CPython, the standard Python interpreter, has used the rule

new_allocated = newsize // 8 + (3 if newsize < 9 else 6)   # extra slots

when a list must grow to newsize items, translated here from C; recent versions use a rule of the same shape. The extra allocation is modest, about one eighth of the size of the array, but it is still linear in that size, so on average $n/8$ insertions are performed for every linear-time reallocation: amortized constant time.

Now consider removing items from the end. Popping the last item can be done in constant time by decrementing a stored length, which Python does. But if many items are removed from a large list, the unused allocation can hold a large amount of memory that is not available for other purposes. Once the array is small enough we transfer its contents to a smaller allocation and release the larger one. The new allocation cannot be exactly the size of the array, since an immediate insertion would then trigger another reallocation. For constant amortized time over any sequence of appends and pops, there must remain a linear fraction of unused space whenever we rebuild into a smaller array, which guarantees that $\Omega(n)$ further operations must occur before the next reallocation.

The implementation below does both with table-doubling proportions. When an append would pass the end of the allocation, the contents move to an allocation twice as large. When removals bring the array down to a quarter of its allocation, the contents move to an allocation half as large. Python lists already work this way; the code shows how amortized constant-time append and pop can be implemented.

class Dynamic_Array_Seq(Array_Seq):
    def __init__(self, r = 2):              # O(1)
        super().__init__()
        self.size = 0
        self.r = r
        self._compute_bounds()
        self._resize(0)

    def __len__(self): return self.size     # O(1)

    def __iter__(self):                     # O(n)
        for i in range(len(self)): yield self.A[i]

    def build(self, X):                     # O(n)
        for a in X: self.insert_last(a)

    def _compute_bounds(self):              # O(1)
        self.upper = len(self.A)
        self.lower = len(self.A) // (self.r * self.r)

    def _resize(self, n):                   # O(1) or O(n)
        if (self.lower < n < self.upper): return
        m = max(n, 1) * self.r
        A = [None] * m
        self._copy_forward(0, self.size, A, 0)
        self.A = A
        self._compute_bounds()

    def insert_last(self, x):               # O(1) amortized
        self._resize(self.size + 1)
        self.A[self.size] = x
        self.size += 1

    def delete_last(self):                  # O(1) amortized
        self.A[self.size - 1] = None
        self.size -= 1
        self._resize(self.size)

    def insert_at(self, i, x):              # O(n)
        self.insert_last(None)
        self._copy_backward(i, self.size - (i + 1), self.A, i + 1)
        self.A[i] = x

    def delete_at(self, i):                 # O(n)
        x = self.A[i]
        self._copy_forward(i + 1, self.size - (i + 1), self.A, i)
        self.delete_last()
        return x

    def insert_first(self, x): self.insert_at(0, x)       # O(n)
    def delete_first(self): return self.delete_at(0)      # O(n)

def __init__(self, r = 2) gives the parameter r a default value: Dynamic_Array_Seq() uses r = 2, and Dynamic_Array_Seq(3) uses r = 3. The class inherits get_at, set_at and the two copying methods from Array_Seq.

The worst-case costs of the three sequence structures are collected below, with (a) marking an amortized bound.

Each entry is the $O(\cdot)$ bound as a function of the number $n$ of stored items.

Hashing

The set interface asks for find(k). Stored in an array in no particular order, a set answers find(k) by scanning, in $O(n)$ time. With comparisons alone we cannot do much better: the lower bound for searching in the next lesson shows that $\Omega(\log n)$ comparisons are needed for a search among $n$ items. Reading memory at an address computed from the key is not a comparison, and it reaches any memory cell in one step. Hashing uses this.

Direct Access Arrays

A direct access array is a static array with a meaning attached to each index: an item $x$ with key $k$ is stored at index $k$. This makes sense only when keys are integers. Anything stored in a computer can be associated with an integer, for example its sequence of bits read as a binary number, or its address in memory, so from now on keys are integers.

Suppose we want to store a set of $n$ items whose unique integer keys lie in the range $0, \ldots, u - 1$. We store them in a direct access array of length $u$, whose slot $i$ holds the item with key $i$ if there is one. To find the item with key $i$, look in slot $i$: worst-case constant time. The order operations are slow: the first, last or next item could be in any slot, so they may take $u$ time.

class DirectAccessArray:
    def __init__(self, u): self.A = [None] * u   # O(u)
    def find(self, k): return self.A[k]          # O(1)
    def insert(self, x): self.A[x.key] = x       # O(1)
    def delete(self, k): self.A[k] = None        # O(1)

    def find_next(self, k):                      # O(u)
        for i in range(k + 1, len(self.A)):
            if self.A[i] is not None:
                return self.A[i]

    def find_max(self):                          # O(u)
        for i in range(len(self.A) - 1, -1, -1):
            if self.A[i] is not None:
                return self.A[i]

    def delete_max(self):                        # O(u)
        for i in range(len(self.A) - 1, -1, -1):
            x = self.A[i]
            if x is not None:
                self.A[i] = None
                return x

A direct access array needs a slot for every possible key in the range. When $u$ is very large compared with the number of items stored, the array is wasteful, or impossible to store at all. Suppose we wanted find(k) on ten-letter names with a direct access array. There are $u = 26^{10} \approx 1.4 \times 10^{14}$ possible names, and even an array of one bit per name would need $17.6$ terabytes.

The following counting principle is used below to show that collisions cannot be avoided.

Hash Functions

To keep fast search while using only $O(n)$ space when $n$ is much smaller than $u$, we store the items in a smaller direct access array of $m = O(n)$ slots, growing and shrinking it like a dynamic array according to the number of items stored. This needs a way to send each key to one of the $m$ slots.

If $h$ happens to be injective on the $n$ keys being stored, so that no two of them collide, the hash table acts as a direct access array over the smaller range $\{0, \ldots, m-1\}$ and supports worst-case constant-time search. When $m < u$, however, the pigeonhole principle puts at least two of the $u$ possible keys in some slot, and when the keys to be stored are not known in advance it is very unlikely that a chosen hash function avoids collisions among them. (If all the keys are known in advance, a scheme called perfect hashing can be designed to avoid collisions between them.)

A slot can hold one item, so colliding items must be stored somewhere. Either they are stored elsewhere in the same array, which is called open addressing and is how most hash tables are implemented in practice, though it is harder to analyse; or they are stored in a separate structure, which is called chaining and is the strategy we adopt.

Chaining

In chaining each slot of the hash table holds a reference to a chain, a separate data structure supporting the dynamic set operations find(k), insert(x) and delete(k). A chain is usually a linked list or a dynamic array, and any implementation will do provided each operation takes at most linear time in the length of the chain. To insert an item $x$, insert it into the chain at slot $h(x.\mathrm{key})$; to find or delete a key $k$, find or delete it in the chain at slot $h(k)$.

A chain in Python can be a list of items searched from the front:

class Chain:
    def __init__(self): self.items = []          # O(1)
    def __iter__(self): yield from self.items    # O(length)

    def find(self, k):                           # O(length)
        for x in self.items:
            if x.key == k: return x
        return None

    def insert(self, x):                         # O(length)
        for i in range(len(self.items)):
            if self.items[i].key == x.key:
                self.items[i] = x                # replace, nothing added
                return False
        self.items.append(x)
        return True

    def delete(self, k):                         # O(length)
        for i in range(len(self.items)):
            if self.items[i].key == k:
                return self.items.pop(i)
        return None

We want chains to be short: if every chain holds a constant number of items, the dynamic set operations run in constant time. If instead the hash function sends every stored key to the same slot, one chain has linear length and the operations can take linear time. A good hash function keeps collisions rare, so that no chain grows long.

Choosing a Hash Function

The simplest map from keys in $\{0, \ldots, u-1\}$ to $\{0, \ldots, m-1\}$ is the division method: $h(k) = k \bmod m$, in Python k % m. If the keys stored are spread evenly over the range, it spreads them roughly evenly among the slots and the chains stay short. But if all of them happen to leave the same remainder on division by $m$, every one lands in one chain. We want performance that does not depend on which keys are stored, and no single hash function gives that.

Instead we choose the hash function at random, from a large family, after the keys are fixed. Then no set of keys is bad for most of the family, and we can bound the cost on average over the choice of function. The averages we need are over a finite set of equally likely choices.

Two facts follow from the laws of summation. Expectation is linear: $\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]$ and $\mathbb{E}[cX] = c\,\mathbb{E}[X]$, because the sum defining the left side splits into the sums defining the right. And the expectation of an Iverson bracket is a probability: $\mathbb{E}\bigl[[P(h)]\bigr] = \Pr[P(h)]$, since the bracket contributes $1$ for each $h$ with $P(h)$ and $0$ otherwise. The expectation here is over the choice of hash function, which is made independently of the input. It is not an average over possible input keys.

A family that performs well is

where $p$ is a prime larger than $u$. A single function of the family is specified by choosing concrete values of $a$ and $b$. This family is universal. The proof uses arithmetic modulo a prime, which these notes have not developed, and we take it as given.