03 - Search: Linear, Binary, and Hash Tables

You have a million customer codes and for every request that arrives you need to know whether one of them is present. You can scan the list, you can keep it sorted and halve the search space at every step, or you can compute directly where the code should be. These are three very different costs, and the difference does not lie in the skill of whoever writes the code but in two things you can check: is the input sorted? How much memory are you willing to spend for faster answers?

This is the third article in the Algorithms and Data Structures series; to read it you need the counting analysis of the first article and, for binary search, the idea of a sorted list seen in the second. The listings are in Python 3.14 with the standard library only (python3 -I); every cost is a count (probes, comparisons, cells examined), and each formula is compared with a measurement. You have already seen linear search in the first article, with its n comparisons in the worst case: here I start from binary search.

Binary search: the invariant before the code

Binary search works because, at every step, you know two things: everything to the left of lo is smaller than the sought value, and everything from hi onward is greater than or equal to it. This pair of facts is the invariant of the loop: true before every iteration, preserved by every iteration, and at the end (lo == hi) it tells you that lo is the first place where the value could be. The listing checks it at every iteration with an assert, on all sorted lists with values from 0 to 5 and length up to 8, duplicates included.

# Binary search (variant "first index with a[i] >= x"), with the invariant checked at every step
import math, random
from bisect import bisect_left

def binary_search(a, x, check=False):
    lo, hi, probes = 0, len(a), 0
    while lo < hi:
        if check:                            # invariant: everything left of lo is < x, everything from hi onward is >= x
            assert all(v < x for v in a[:lo]) and all(v >= x for v in a[hi:])
        mid = (lo + hi) // 2
        probes += 1
        if a[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo, probes                        # lo is the insertion point; found if a[lo] == x

# correctness: all sorted lists with values in 0..5 up to length 8 (with duplicates), every x from -1 to 6
import itertools
for n in range(0, 9):
    for a in itertools.combinations_with_replacement(range(6), n):
        for x in range(-1, 7):
            pos, probes = binary_search(list(a), x, check=True)
            assert pos == bisect_left(a, x)                          # reference: standard library
            assert pos == next((i for i, v in enumerate(a) if v >= x), n)   # reference: linear scan
            assert probes <= (math.floor(math.log2(n)) + 1 if n else 0)
print("binary search: correct, invariant checked at every step, probes <= floor(log2 n)+1")

print(f"{'n':>9} {'worst-case probes':>24} {'floor(log2 n)+1':>16} {'linear search':>16}")
for n in (10, 1000, 10**6, 10**9):
    worst = max(binary_search(range(n), x)[1] for x in (-1, 0, n // 3, n - 1, n))   # range(): no list of 10^9 elements
    print(f"{n:>9} {worst:>24} {math.floor(math.log2(n)) + 1:>16} {n:>16}")

# if the list is NOT sorted the result is meaningless: 2000 random lists of 8 distinct elements
rng = random.Random(7)
missed = 0
for _ in range(2000):
    a = rng.sample(range(100), 8)
    x = rng.choice(a)
    pos, _ = binary_search(a, x)
    missed += not (pos < len(a) and a[pos] == x)
print("on an unsorted list, a present element reported as absent:", missed, "times out of 2000")

# in languages with 32-bit integers, (lo + hi) // 2 can exceed the maximum: simulation of 32-bit arithmetic
to_int32 = lambda v: (v + 2**31) % 2**32 - 2**31
lo, hi = 1_500_000_000, 2_000_000_000
print("(lo + hi) / 2 in 32 bits:", to_int32(lo + hi) // 2, "| lo + (hi - lo) / 2:", to_int32(lo + (hi - lo) // 2))

# Output:
# binary search: correct, invariant checked at every step, probes <= floor(log2 n)+1
#         n        worst-case probes  floor(log2 n)+1    linear search
#        10                        4                4               10
#      1000                       10               10             1000
#   1000000                       20               20          1000000
# 1000000000                       30               30       1000000000
# on an unsorted list, a present element reported as absent: 1522 times out of 2000
# (lo + hi) / 2 in 32 bits: -397483648 | lo + (hi - lo) / 2: 1750000000

The variant returns the insertion point, not just "found / not found", and it has the same semantics as bisect_left in Python's standard library (pos == bisect_left(a, x) is one of the two independent references, the other is a linear scan). The number of probes in the worst case is ⌊log₂ n⌋ + 1 in every row: 10 for a thousand elements, 20 for a million, 30 for a billion. To scan a billion elements you need a billion comparisons; to halve them you need thirty. That is the advantage of order.

The last two lines are the two ways in which binary search breaks. If the list is not sorted, the result is not "slightly wrong": on 2,000 random lists it reported a present element as absent 1,522 times, 76%. And in languages with 32-bit integers the computation (lo + hi) / 2 can exceed the maximum representable value: with lo = 1.5 billion and hi = 2 billion the sum becomes negative and the midpoint falls outside the list (−397,483,648), while lo + (hi − lo) / 2 gives 1,750,000,000. In Python integers have no limit and the problem does not arise; I simulated it with 32-bit arithmetic to show you the shape of the error.

Hash table: computing where the key is

A hash table uses a function to turn the key into an index of an array of m positions. Two different keys can end up in the same position, which is a collision: it has to be handled. The simplest solution is to keep a list in every position (chaining). The listing implements insertion, search and deletion, and verifies them against dict on 20,000 random operations with a fixed seed. The cost is the number of key comparisons along the list.

# Hash table with collision lists (chaining): cost = key comparisons along the list
import random

class ChainedTable:
    def __init__(self, m, hash_fn):
        self.m, self.hash_fn = m, hash_fn
        self.buckets = [[] for _ in range(m)]
        self.compares = 0
    def _chain(self, key):
        return self.buckets[self.hash_fn(key) % self.m]
    def put(self, key, value):
        chain = self._chain(key)
        for pair in chain:
            if pair[0] == key:
                pair[1] = value
                return
        chain.append([key, value])
    def get(self, key):
        for k, v in self._chain(key):
            self.compares += 1
            if k == key:
                return v
        return None
    def delete(self, key):
        chain = self._chain(key)
        for i, pair in enumerate(chain):
            if pair[0] == key:
                del chain[i]
                return True
        return False

good = lambda k: (k * 2654435761) & 0xFFFFFFFF      # Knuth's multiplicative hash
bad = lambda k: 0                                    # all keys in the same bucket

# correctness against dict: 20000 random operations, fixed seed
rng = random.Random(8)
t, ref = ChainedTable(64, good), {}
for _ in range(20000):
    k, op = rng.randrange(500), rng.randrange(3)
    if op == 0:
        t.put(k, k * 2); ref[k] = k * 2
    elif op == 1:
        assert t.get(k) == ref.get(k)
    else:
        assert t.delete(k) == (ref.pop(k, None) is not None)
print("table with lists: consistent with dict on 20000 operations")

M = 1024
print(f"{'alpha':>6} {'found: measured':>16} {'1 + alpha/2':>12} | {'absent: measured':>16} {'alpha':>7}")
for alpha in (0.5, 1, 2, 4):
    n = int(alpha * M)
    keys = rng.sample(range(10**9), n)
    t = ChainedTable(M, good)
    for k in keys:
        t.put(k, 0)
    t.compares = 0
    for k in keys:
        t.get(k)
    hit = t.compares / n
    absent = rng.sample(range(10**9, 2 * 10**9), 5000)
    t.compares = 0
    for k in absent:
        t.get(k)
    miss = t.compares / 5000
    print(f"{alpha:>6} {hit:>16.2f} {1 + alpha / 2:>12.2f} | {miss:>16.2f} {alpha:>7}")

keys = rng.sample(range(10**9), 1000)
for name, fn in (("good", good), ("constant", bad)):
    t = ChainedTable(1024, fn)
    for k in keys:
        t.put(k, 0)
    t.compares = 0
    for k in keys:
        t.get(k)
    print(f"{name} function: mean comparisons per lookup of 1000 keys = {t.compares / 1000:.1f}")

# Output:
# table with lists: consistent with dict on 20000 operations
#  alpha  found: measured  1 + alpha/2 | absent: measured   alpha
#    0.5             1.26         1.25 |             0.48     0.5
#      1             1.50         1.50 |             1.00       1
#      2             2.00         2.00 |             2.01       2
#      4             3.01         3.00 |             3.96       4
# good function: mean comparisons per lookup of 1000 keys = 1.5
# constant function: mean comparisons per lookup of 1000 keys = 500.5

The parameter that governs everything is the load factor α = n/m, the average number of elements per list. A successful search costs on average 1 + α/2 comparisons: you find the key halfway along a list of length α, plus the comparison that identifies it; an unsuccessful search scans the whole list, that is α. The measurements match: 1.26 against 1.25, 1.50, 2.00 and 3.01 against 3.00 for the successful searches, and 0.48, 1.00, 2.01 and 3.96 against α for the unsuccessful ones. The cost does not depend on n but on the ratio n/m, so if you keep α bounded the cost is constant.

The hidden condition is that the hash function spreads the keys uniformly: it is the assumption of Sedgewick and Wayne's text, Algorithms, in the page on hash tables (Assumption J, "uniform hashing assumption"). The last two lines show what happens when it does not hold: with the same table and the same 1,000 keys, a constant function sends everything into the same bucket and the search costs on average 500.5 comparisons, that is (n + 1)/2, a linear search on a list. "O(1)" is a property of the hash function as much as of the structure.

Open addressing and resizing

The alternative to lists is to keep everything in the array: if the position is occupied you try the next one (linear probing). No pointers are needed, but the table cannot fill up completely and the collisions accumulate in "clusters". The listing counts the cells examined for a search, and compares the measurement with the formulas of Proposition M on Sedgewick and Wayne's page: ½(1 + 1/(1 − α)) for successful searches and ½(1 + 1/(1 − α)²) for unsuccessful ones.

# Open addressing with linear probing: cost = cells examined (probes)
import random

class ProbingTable:
    def __init__(self, m, grow=False):
        self.m, self.n, self.slots, self.grow = m, 0, [None] * m, grow
        self.moves = 0                      # elements moved by resizes
        self.worst_insert = 0
    def _index(self, key, m):
        return ((key * 2654435761) & 0xFFFFFFFF) % m
    def put(self, key):
        cost = 1
        if self.grow and self.n + 1 > self.m // 2:    # maximum load factor 1/2
            cost += self._resize(2 * self.m)
        i = self._index(key, self.m)
        while self.slots[i] is not None:
            i = (i + 1) % self.m
        self.slots[i] = key
        self.n += 1
        self.worst_insert = max(self.worst_insert, cost)
    def _resize(self, new_m):
        old, self.slots, self.m, self.n = [k for k in self.slots if k is not None], [None] * new_m, new_m, 0
        for k in old:
            i = self._index(k, self.m)
            while self.slots[i] is not None:
                i = (i + 1) % self.m
            self.slots[i] = k
            self.n += 1
        self.moves += len(old)
        return len(old)
    def probes(self, key):
        i, count = self._index(key, self.m), 1
        while self.slots[i] is not None and self.slots[i] != key:
            i = (i + 1) % self.m
            count += 1
        return count

rng = random.Random(9)
M = 65536
print(f"{'alpha':>6} {'found: measured':>16} {'1/2(1+1/(1-a))':>15} | {'absent: measured':>16} {'1/2(1+1/(1-a)^2)':>17}")
for alpha in (0.25, 0.5, 0.75, 0.9):
    n = int(alpha * M)
    keys = rng.sample(range(10**9), n)
    t = ProbingTable(M)
    for k in keys:
        t.put(k)
    hit = sum(t.probes(k) for k in keys) / n
    absent = rng.sample(range(10**9, 2 * 10**9), 20000)
    miss = sum(t.probes(k) for k in absent) / 20000
    a = n / M
    print(f"{a:>6.2f} {hit:>16.2f} {0.5 * (1 + 1 / (1 - a)):>15.2f} | {miss:>16.2f} {0.5 * (1 + 1 / (1 - a) ** 2):>17.2f}")

print()
print(f"{'insertions':>12} {'total moves':>19} {'per insertion':>16} {'worst single':>17}")
for N in (1000, 10000, 100000):
    t = ProbingTable(8, grow=True)
    for k in rng.sample(range(10**9), N):
        t.put(k)
    print(f"{N:>12} {t.moves:>19} {t.moves / N:>16.2f} {t.worst_insert:>17}")

# Output:
#  alpha  found: measured  1/2(1+1/(1-a)) | absent: measured  1/2(1+1/(1-a)^2)
#   0.25             1.17            1.17 |             1.38              1.39
#   0.50             1.50            1.50 |             2.47              2.50
#   0.75             2.46            2.50 |             8.21              8.50
#   0.90             5.06            5.50 |            41.92             50.49
#
#   insertions         total moves    per insertion      worst single
#         1000                1020             1.02               513
#        10000               16380             1.64              8193
#       100000              131068             1.31             65537

At α = 0.25 and 0.5 the measurements coincide with the formulas (1.17 and 1.50 for successful searches; 1.38 and 2.47 against 1.39 and 2.50 for unsuccessful ones). But when α approaches 1 the cost explodes: at 0.9 an unsuccessful search costs about 42 probes in the table of 65,536 positions, and the formula predicts 50.5. The difference is not a measurement error: the formulas are asymptotic for large tables, and with a table of 2,048 positions (change M in the listing) the same experiment gave me 3.94 and 24.10 at α = 0.9. Hence the practical rule: do not take an open-addressing table beyond a load factor of about one half.

To keep α low the table is resized: when it exceeds the maximum load (here 1/2) it doubles the positions and reinserts every key. The second table of the output shows the cost of this operation. Over 100,000 insertions the total moves are 131,068, that is 1.31 per insertion (and between 1.02 and 1.64 over the three sizes), while the single most expensive insertion requires 65,537: it is the same pattern as the dynamic array of the first article. Insertion is amortized O(1), not worst-case O(1), and if you have a maximum latency to respect that peak is the number that matters.

Why Python's string hash changes at every start

Whoever knows the hash function can build keys that all end up in the same bucket, and it is exactly the experiment with the constant function: a table that receives those keys becomes quadratic in construction time. Python's data model documentation says that for this reason the hashes of str and bytes are "salted" with an unpredictable random value, constant within a process but different from one start to the next, as protection against denial-of-service attacks that exploit the worst case of insertion into a dictionary. The listing verifies it by starting three child processes with PYTHONHASHSEED fixed.

# Python's string hash is "salted" at every start: you can see it from two processes with different seeds
import os, subprocess, sys

def hash_in_new_process(seed):
    env = dict(os.environ, PYTHONHASHSEED=str(seed))
    out = subprocess.run([sys.executable, "-c", "print(hash('algorithms'))"],
                         env=env, capture_output=True, text=True, check=True).stdout
    return int(out)

a1, a2, b1 = hash_in_new_process(1), hash_in_new_process(2), hash_in_new_process(1)
print("same string, seeds 1 and 2: equal hashes?", a1 == a2)
print("same string, seed 1 twice: equal hashes?", a1 == b1)
print("the hash of a small integer is not salted: hash(12345) =", hash(12345))

# Output:
# same string, seeds 1 and 2: equal hashes? False
# same string, seed 1 twice: equal hashes? True
# the hash of a small integer is not salted: hash(12345) = 12345

With different seeds the same string has different hashes; with the same seed, the same hash; and the hash of a small integer is not salted (hash(12345) is 12345). The consequences are practical: never save hash(s) on disk or in a database expecting to find it again, and do not depend on the iteration order of a set of strings across different runs, unless you fix the seed (which in tests is a good idea). For the hash table listings I chose hand-written hash functions, and for the Bloom filter blake2b, which is deterministic, precisely so that the output would be the same at every run.

Bloom filter: saying "certainly absent" with very little memory

A Bloom filter is an array of m bits and k hash functions. You insert a key by turning on k bits; you ask whether a key is present by checking whether all its k bits are on. If one is off the key is certainly absent; if they are all on it is probably present. There are no false negatives, but there are false positives, and they can be predicted: with n keys the probability is about (1 − e^−kn/m)^k. The listing inserts 10,000 keys, checks 50,000 keys never inserted and compares the measured rate with the formula, for five combinations of bits per key and k.

# Bloom filter: m bits, k hash functions derived from a single digest (blake2b) with double hashing
import hashlib, math

class Bloom:
    def __init__(self, m, k):
        self.m, self.k, self.bits = m, k, bytearray((m + 7) // 8)
    def _positions(self, key):
        d = hashlib.blake2b(str(key).encode(), digest_size=16).digest()
        h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:], "big") | 1
        return [(h1 + i * h2) % self.m for i in range(self.k)]
    def add(self, key):
        for p in self._positions(key):
            self.bits[p // 8] |= 1 << (p % 8)
    def __contains__(self, key):
        return all(self.bits[p // 8] >> (p % 8) & 1 for p in self._positions(key))

n = 10000
print(f"{'bits/key':>10} {'k':>3} {'measured false positives':>24} {'(1-e^(-kn/m))^k':>16} {'false negatives':>15}")
for bits_per_key, k in ((5, 3), (10, 7), (10, 3), (10, 14), (15, 10)):
    m = bits_per_key * n
    f = Bloom(m, k)
    for key in range(n):
        f.add(key)
    false_neg = sum(key not in f for key in range(n))                  # must be 0
    tests = range(10**6, 10**6 + 50000)                                # keys never inserted
    fp = sum(key in f for key in tests) / len(tests)
    print(f"{bits_per_key:>10} {k:>3} {fp:>24.4f} {(1 - math.exp(-k * n / m)) ** k:>16.4f} {false_neg:>15}")

# Output:
#   bits/key   k measured false positives  (1-e^(-kn/m))^k false negatives
#          5   3                   0.0914           0.0918               0
#         10   7                   0.0078           0.0082               0
#         10   3                   0.0169           0.0174               0
#         10  14                   0.0182           0.0190               0
#         15  10                   0.0007           0.0007               0

The false-negatives column is zero in every row, as it must be by construction. The false positives match the formula to within a tenth of a percentage point: 9.1% against 9.2% with 5 bits per key and k = 3, 0.78% against 0.82% with 10 bits and k = 7. With the same memory (10 bits per key) the number of hashes matters: k = 7 gives 0.78%, while k = 3 and k = 14 give 1.7% and 1.8%, more than double. The best value of k is about (m/n)·ln 2, which for 10 bits per key is 6.9: the measurement confirms it, and it is the reason why with 15 bits per key you get down to 0.07%. Bloom's original paper (Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 1970) is the source of the structure: I cited it after verifying the metadata, without reading the text.

Which search to choose

• Linear search: no requirement on the input, n comparisons in the worst case; fine for short lists or rare searches.
• Binary search: requires a sorted input, ⌊log₂ n⌋ + 1 probes; fine when you search many times in data that rarely change, and it also provides the insertion point.
• Hash table: no order, constant expected cost with bounded α, but additional memory, resizes with peaks, and no ordering of the keys.
• Bloom filter: few bits per key, no false negatives and a computable probability of false positives, but it does not return the value and does not allow deletion.

The choice does not depend on which is "faster" but on what you need beyond the yes or no: the order of the keys (which the hash table does not keep), the range of nearby values (which only the sorted list offers), or the guarantee of admitting no false negatives with minimal memory (which only the filter gives). If the data change constantly and you also need the order, the right structure is none of these but a balanced tree, the protagonist of the article on BSTs and AVLs.

Exercises

1. Write binary search for the last occurrence of a duplicated value and verify your function against bisect_right.
2. In the listing of the table with lists try a hash function k % 8 with keys that are all multiples of 8 and measure the mean comparisons.
3. Add deletion to open addressing and explain why emptying the cell breaks the later searches.
4. For a filter with 10,000 keys and a false-positive target of 1%, derive m and k from the formula and verify them with the listing.

The third exercise is the most instructive: in open addressing an empty cell means "the chain ends here", and if deletion empties it without leaving a mark (a tombstone) the keys inserted after the collision become unreachable. It is the reason why almost all real implementations use tombstones or redesign the block.

Frequently asked questions

Is a hash table really O(1)?

It is on average, if the hash function spreads the keys well and the load factor stays bounded; with a function that sends all the keys into the same bucket the cost of a search becomes linear, as the experiment with the constant function shows.

Why does binary search require a sorted list?

Because at each step it discards half of the interval based on the order; without order the choice of which half to discard is random, and on unsorted lists the listing missed a present element 1,522 times out of 2,000.

Can a Bloom filter be wrong?

Only in one direction: it can say "maybe present" for a key never inserted (a false positive, with a computable probability), but it never says "absent" for an inserted key.

What you can do now

You can write a binary search starting from its invariant and you know where it breaks: unsorted list and 32-bit index sum. You can measure the cost of a hash table in comparisons or probes and compare it with 1 + α/2, with the open-addressing formulas and with the cost of resizing; you also know when the constant cost stops being true. You have seen a Bloom filter work and you can derive the probability of false positives. In the next article, lists, stacks, queues and deques, you move on to the structures that these searches took for granted.

The same series also includes the closing article on dynamic programming.