Load factor, rehashing and performance

After this page, you should be able to:

• Separate live load, used load, distribution and rebuild work.

• Qualify expected, worst-case and amortised costs for each operation.

Builds on: Chaining and probing use different search invariants.

Code languages: Python defines the explanations, figures and self-checks. Use the language guide for native conventions and dependencies. Complete runnable topic examples: Python · JavaScript · Julia.

Native containers have different equality and iteration rules. JavaScript examples use primitive keys; array keys compare by identity. The low-level helpers use the supplied teaching hash: h(k)=k for integer traces. Julia helper indices are one-based; table layouts for other native hash functions need not match Python. Snapshot containers differ in type, not ownership.

Let n be the number of live entries and m the capacity. The load factor is $\alpha=n/m$. It summarises occupancy; it does not describe how evenly keys are distributed.

Load factor and collision strategies¶

In chaining, $\alpha$ is the average bucket length, including empty buckets, and may exceed 1. With suitable hash distribution, constant-cost hashing/equality and bucket access, expected lookup takes $O(1+\alpha)$. If all keys share a bucket, the worst case is $O(n)$.

In open addressing, each live entry needs a distinct slot. Lookup examines at most m slots in the bounded linear-probing implementation. Expected probe cost depends on the collision method, distribution, occupancy and deletion history; do not reuse the chaining formula for probing.

For long strings or custom keys, hashing and equality may themselves require more than constant work. State the key-cost assumption when analysing table operations.

Live load and used load¶

If d slots are tombstones, distinguish live load $n/m$ from used load $(n+d)/m$. With m = 10, n = 3 and d = 6, live load is 0.3 but used load is 0.9. Only one slot is EMPTY, and a failed search may pass many tombstones.

Rebuilding at the same capacity can remove tombstones. Growing the table and removing tombstones address related but different problems.

Why changing capacity requires rehashing¶

An index depends on m. With $h(k)=k$, keys 8, 15 and 22 all select index 1 at capacity 7. At capacity 14, they select 8, 1 and 8 respectively. Copying each old slot into the same numbered new slot would violate the new placement rule.

A rebuild creates an empty table and reinserts live entries using the new capacity. For probing, specify the reinsertion order because it can affect final positions. Tombstones are not reinserted.

Compare operations under stated assumptions¶

Let m be allocated table capacity, n live entries, d tombstones and r returned records. Hashing/equality and reference operations are constant-cost in this table; add key-processing costs separately.

Membership can use the same exact-key search without treating a stored None as absence. A bare table with no cached count must scan to compute size. Operation workspace is normally O(1); bucket allocation and full rebuilds can require additional memory. These costs are about representations, not universal Map/Set guarantees.

Rebuild helpers illustrate maintenance¶

def rebuild_chained(table, capacity):
    if type(capacity) is not int or capacity <= 0:
        raise ValueError("capacity must be a positive integer")
    fresh = [[] for _ in range(capacity)]
    for bucket in table:
        for key, value in bucket:
            put_chained(fresh, key, value)
    return fresh

def rebuild_probed(table, capacity):
    if type(capacity) is not int or capacity <= 0:
        raise ValueError("capacity must be a positive integer")
    fresh = [EMPTY] * capacity
    for slot in table:
        if slot is not EMPTY and slot is not DELETED:
            put_probed(fresh, slot[0], slot[1])
    return fresh

function rebuild_chained(table, capacity) {
    if (!Number.isSafeInteger(capacity) || capacity <= 0) throw new RangeError("positive integer capacity required");
    const fresh = Array.from({length: capacity}, () => []);
    for (const bucket of table) for (const [key, value] of bucket) put_chained(fresh, key, value);
    return fresh;
}
function rebuild_probed(table, capacity) {
    if (!Number.isSafeInteger(capacity) || capacity <= 0) throw new RangeError("positive integer capacity required");
    const fresh = Array(capacity).fill(EMPTY);
    for (const slot of table) if (slot !== EMPTY && slot !== DELETED) put_probed(fresh, slot[0], slot[1]);
    return fresh;
}

function rebuild_chained(table, capacity)
    (capacity isa Int && capacity > 0) || throw(ArgumentError("positive integer capacity required"))
    fresh = [Any[] for _ in 1:capacity]
    for bucket in table, (key, value) in bucket
        put_chained!(fresh, key, value)
    end
    return fresh
end
function rebuild_probed(table, capacity)
    (capacity isa Int && capacity > 0) || throw(ArgumentError("positive integer capacity required"))
    fresh = Any[EMPTY for _ in 1:capacity]
    for slot in table
        if slot !== EMPTY && slot !== DELETED; put_probed!(fresh, slot[1], slot[2]); end
    end
    return fresh
end

These helpers reuse preceding definitions and return a new table, leaving the old table unchanged. Probing reinserts live entries in old physical-slot order; deleted markers disappear. A requested probing capacity smaller than n raises OverflowError during rebuilding; the original remains valid. A caller keeps the returned table only after successful construction.

Rebuilding scans the old storage, initialises the new storage and pays all reinsertion costs. Under suitable distribution and bounded target load, expected cost is O(m_old+m_new+n). Reinsertions can cost O(n²) under pathological collisions, so rebuilding is not unconditionally linear. Extra storage includes the new table while the old remains live.

Expected and amortised complexity¶

Expected cost averages over a stated probabilistic model, such as suitable hash distribution. Amortised cost spreads work across an operation sequence. Neither term means that each individual operation is cheap.

With geometric capacity growth, the entry counts processed across successive expansions form a geometric series. Under suitable distribution, bounded occupancy and the usual capacity policy, the total rebuilding work over n insertions is expected $O(n)$, giving expected amortised $O(1)$ insertion. A single insertion that triggers rebuilding may still cost $O(n)$ under those assumptions. Pathological collisions can invalidate the expected constant-time claim.

These distinctions connect hash tables to dynamic arrays, where occasional resizing also motivates amortised analysis.

Implementation choices and suitability¶

Growing prevents excessive live load; same-capacity rebuilding removes tombstones; shrinking releases spare storage. These are separate policies. Thresholds should leave enough successful updates between rebuilds to support the claimed amortised bound. Rebuilding after every deletion would not do so. The fixed helpers above implement a rebuild, not an automatic threshold policy.

Check your understanding¶

Predict the result and resulting state before opening the explanation.

1. With m=10, n=3 and d=6, what are live and used load?

2. Does expected amortised O(1) insertion make a resizing insertion worst-case O(1)?

Next: Choosing a structure.

Browse: Maps, Sets and Hashing · Concept index