Perfect Hashing / FKS

Why Perfect Hashing / FKS Matters

A compiler has a fixed set of reserved identifiers. A generated lookup table has a known collection of protocol codes. A read-only index is built once and queried repeatedly. In such cases, it is reasonable to spend extra work during construction to remove collisions for the stored keys and make every later membership query take a fixed number of table accesses.

FKS, named for Fredman, Komlós, and Szemerédi, is a two-level static hashing scheme. The first level distributes $n$ distinct keys among $n$ buckets. A bucket containing $b$ keys gets a secondary table of $b^2$ slots and its own hash function, retried until those keys have no collisions. The first level is also retried until the sum of the secondary sizes is linear in $n$.

You will build a reproducible integer set, inspect both kinds of retries, prove the space and expected-construction bounds, and check membership correctly for nonmembers. “Perfect” means collision-free on the chosen stored set; it does not mean every possible query has its own slot, nor that construction always succeeds on its first attempt.

Core Concepts and Terminology

The input is a fixed set $S$ of $n$ distinct keys. The result stores those keys in collision-free secondary arrays, plus hash parameters and bucket metadata. Membership queries are supported after construction; insertion and deletion are not part of this static implementation. A changed set requires a new build or a separate dynamic design.

The example's key universe is $U=\{0,\ldots,P-1\}$ for prime $P=2147483647$. Negative values and $P$ itself are outside its contract. This restriction makes field arithmetic explicit and keeps all intermediate products within signed $64$-bit range in C++ and Java. Zero is a valid key and has a separate occupancy representation.

For table size $m\ge1$, use the family

$$h_{a,b,m}(x)=\bigl((ax+b)\bmod P\bigr)\bmod m,$$

where $1\le a\lt P$ and $0\le b\lt P$. With $a$ and $b$ sampled independently and uniformly from those domains, distinct universe keys collide with probability at most $1/m$ for $m\le P$. This universal collision bound is sufficient; the proof does not require fully independent outputs for all keys.

The first-level hash has range $[0,n)$ when $n\gt0$. Let $b_i$ be bucket $i$'s key count and define

$$Q=\sum_{i=0}^{n-1}b_i^2.$$

Accept the first-level parameters only if $Q\le4n$. Allocate $b_i^2$ slots for bucket $i$, using no slots for an empty bucket and one for a singleton. A nontrivial bucket chooses its own parameters; they need not match those of any other bucket.

An FKS location can be represented by the pair $(i,j)$: first-level bucket and secondary index. If a flat output index is needed, assign each bucket a prefix offset and return $\mathrm{offset}_i+j$. The range then has $Q$ secondary positions, not necessarily $n$, so this still need not be minimal perfect hashing.

How Perfect Hashing / FKS Works, Step by Step

The construction separates the global space decision from the local collision decisions:

1. Validate the input universe and reject duplicate keys. The programs use a stable binary radix pass for each of the $31$ key bits on a copy, then check adjacent equal keys. This avoids using another hash table to validate the set and costs linear work for this fixed-width domain.
2. For a nonempty input, choose first-level parameters, distribute keys into $n$ buckets, and compute $Q$. If $Q\gt4n$, discard the grouping and retry. Do not allocate the large quadratic secondary arrays for a rejected grouping.
3. For each accepted bucket, allocate exactly its squared size. Empty buckets and singletons need no randomized local search in this implementation.
4. For a bucket with at least two keys, sample local parameters and start with a fresh empty secondary array. Insert its keys at their computed indices. If an occupied target is encountered, discard that candidate array and retry that bucket.
5. Accept the local table only after all its keys have been placed without collisions. Once all buckets succeed, the structure is ready for queries.

flowchart TD
    A["Validate distinct universe keys"] --> B{"Input empty?"}
    B -->|Yes| C["Build empty dictionary"]
    B -->|No| D["Choose outer hash; group into n buckets"]
    D --> E{"Sum of squared sizes at most 4n?"}
    E -->|No| D
    E -->|Yes| F{"Another bucket?"}
    F -->|No| G["Construction complete"]
    F -->|Yes| H{"Bucket size at most one?"}
    H -->|Yes| I["Store empty or singleton bucket"]
    I --> F
    H -->|No| J["Choose local hash; allocate fresh squared-size array"]
    J --> K{"Any stored-key collision?"}
    K -->|Yes| J
    K -->|No| L["Accept local table"]
    L --> F

The diagram shows the ideal retry process. The runnable code bounds every first-level or nontrivial secondary search by max_trials, defaulting to $256$. If that budget is exhausted, construction raises an explicit error instead of returning an incomplete dictionary. An empty set performs no random draws and answers every valid-universe membership query as absent.

For lookup, compute $i=h(x)$, return absent if bucket $i$ is empty, then compute $j=h_i(x)$. Return present only if secondary slot $j$ is occupied by the full key $x$. No probing, chaining, or retry occurs during a query.

Worked Example with a Full Trace

Use keys $[0,1,2,3,4,5,6,7]$, seed $7$, and $n=8$. The first-level acceptance limit is $4n=32$. The following table records every outer trial:

The accepted outer hash sends each key to the bucket listed below. Singleton buckets use one slot with trivial local parameters $(1,0)$. Buckets $0$, $2$, and $5$ have no members and allocate no slots.

Secondary construction processes buckets in increasing index order, keeping each bucket's keys in the original input order. All sampled local hashes are shown here:

On the failed bucket-$7$ trial, key $1$ first occupies slot $0$. The attempted placement of $6$ detects that the target is occupied and stops without overwriting it. The candidate is discarded. The successful retry starts with all four slots empty, so no stale key or occupancy information can affect it.

The final local arrays are: bucket $1$ contains $[\mathrm{empty},\mathrm{empty},7,2]$; bucket $3$ contains $[3]$; bucket $4$ contains $[4]$; bucket $6$ contains $[\mathrm{empty},\mathrm{empty},5,0]$; and bucket $7$ contains $[\mathrm{empty},6,1,\mathrm{empty}]$. They use $14$ secondary slots for $8$ members.

There are two outer trials and four randomized secondary trials. Empty and singleton buckets do not contribute to the secondary-trial counter. Each sampled hash pair consumes four raw generator outputs in this run, with no rejection in the bounded conversion, giving $24$ raw draws in total.

For a membership trap, query $9$. Its outer bucket is $4$, and that singleton's local index is $0$, which contains key $4$. The slot is occupied, but $9\ne4$, so the correct answer is absent. Perfectness on the eight stored keys places no restriction preventing this nonmember from sharing their candidate location.

Implementation in Python, C++, and Java

Each panel contains a complete static integer set, including seeded parameter generation, input validation, both retry stages, and full-key membership checks. The input is limited to at most $10000$ distinct keys in $[0,P)$. That cap also ensures that any accepted secondary capacity is at most $4n\le40000\lt P$. The constructor never mutates the caller's key array.

The portable generator uses $s\leftarrow16807s\bmod P$ from a seed in $[1,P)$. To generate parameters over their full required domains, combine two raw outputs: let $B=P-1$, $u=s_1-1$, $v=s_2-1$, and $r=uB+v$. The combined range has size $R=B^2$. For a requested bound $t$, reject values at least $R-(R\bmod t)$ and otherwise return $r\bmod t$. Use $a=1+\mathrm{below}(P-1)$ and $b=\mathrm{below}(P)$.

If the raw digits were independent and uniform, this conversion would provide uniform bounded integers without modulo bias. A finite seeded generator does not supply that ideal independence, so the expectation proof remains a model-based guarantee. Every actual returned layout is still verified for the required space score and collision freedom. A bad candidate sequence can cause an explicit budget error, never a silently accepted collision.

All products fit signed $64$-bit arithmetic: $a x+b\le P(P-1)\lt2^{63}$, and $r\lt(P-1)^2\lt2^{63}$. The raw generator calls are sequenced explicitly, so C++ evaluation order cannot change or invalidate the replay. Key validation precedes the radix passes; all accepted keys have only $31$ nonnegative bits. The fixed $31$ stable partition passes take $\Theta(n+1)$ work in the fixed-width model and $O(n)$ extra storage.

P = 2147483647
B = P - 1
RAW_RANGE = B * B


class RNG:
    def __init__(self, seed):
        if not isinstance(seed, int) or not 1 <= seed < P:
            raise ValueError("invalid seed")
        self.state, self.draws = seed, 0

    def next(self):
        self.state = (16807 * self.state) % P
        self.draws += 1
        return self.state

    def below(self, bound):
        if not 1 <= bound <= P:
            raise ValueError("invalid random bound")
        limit = RAW_RANGE - RAW_RANGE % bound
        while True:
            u = self.next() - 1
            v = self.next() - 1
            r = u * B + v
            if r < limit:
                return r % bound


def parameters(rng):
    return 1 + rng.below(P - 1), rng.below(P)


def hash_key(key, a, b, size):
    return ((a * key + b) % P) % size


def check_key(key):
    if not isinstance(key, int) or not 0 <= key < P:
        raise ValueError("key must be in 0..2147483646")


class FKSSet:
    def __init__(self, keys, seed=7, max_trials=256):
        self.rng = RNG(seed)
        if max_trials < 1 or len(keys) > 10000:
            raise ValueError("invalid trial or input-size limit")
        for key in keys:
            check_key(key)
        ordered = list(keys)
        for bit in range(31):
            ordered = ([key for key in ordered if not ((key >> bit) & 1)]
                       + [key for key in ordered if (key >> bit) & 1])
        if any(ordered[i - 1] == ordered[i] for i in range(1, len(ordered))):
            raise ValueError("input keys must be distinct")
        self.n = len(keys)
        self.top, self.buckets = (1, 0), []
        self.top_trials = self.secondary_trials = self.secondary_slots = 0
        if self.n == 0:
            return
        for _ in range(max_trials):
            self.top_trials += 1
            a, b = parameters(self.rng)
            groups = [[] for _ in range(self.n)]
            for key in keys:
                groups[hash_key(key, a, b, self.n)].append(key)
            q = sum(len(group) ** 2 for group in groups)
            if q <= 4 * self.n:
                self.top, self.secondary_slots = (a, b), q
                break
        else:
            raise RuntimeError("first-level trial limit reached")
        for group in groups:
            size = len(group) ** 2
            if len(group) <= 1:
                self.buckets.append((1, 0, group.copy()))
                continue
            for _ in range(max_trials):
                self.secondary_trials += 1
                a, b = parameters(self.rng)
                slots = [None] * size
                ok = True
                for key in group:
                    j = hash_key(key, a, b, size)
                    if slots[j] is not None:
                        ok = False
                        break
                    slots[j] = key
                if ok:
                    self.buckets.append((a, b, slots))
                    break
            else:
                raise RuntimeError("secondary trial limit reached")

    def location(self, key):
        check_key(key)
        if self.n == 0:
            return None
        i = hash_key(key, *self.top, self.n)
        a, b, slots = self.buckets[i]
        if not slots:
            return None
        j = hash_key(key, a, b, len(slots))
        return (i, j) if slots[j] == key else None

    def contains(self, key):
        return self.location(key) is not None


def main():
    keys = [0, 1, 2, 3, 4, 5, 6, 7]
    s = FKSSet(keys)
    print(f"keys={s.n}, secondary slots={s.secondary_slots}")
    print(f"top trials={s.top_trials}, secondary trials={s.secondary_trials}, raw draws={s.rng.draws}")
    print(f"top parameters = ({s.top[0]}, {s.top[1]})")
    for key in keys:
        i, j = s.location(key)
        print(f"{key} -> ({i}, {j})")
    ok = all(s.contains(key) for key in keys) and not s.contains(9) and not s.contains(100) and not s.contains(P - 1)
    print("checks = " + ("PASS" if ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>
const std::int64_t P = 2147483647, B = P - 1, RAW_RANGE = B * B;

struct RNG {
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= P) throw std::invalid_argument("invalid seed");
    }
    std::int64_t next() { state = (16807 * state) % P; ++draws; return state; }
    std::int64_t below(std::int64_t bound) {
        if (bound < 1 || bound > P) throw std::invalid_argument("invalid random bound");
        std::int64_t limit = RAW_RANGE - RAW_RANGE % bound;
        for (;;) {
            std::int64_t u = next() - 1;
            std::int64_t v = next() - 1;
            std::int64_t r = u * B + v;
            if (r < limit) return r % bound;
        }
    }
};
struct Params { std::int64_t a = 1, b = 0; };
Params parameters(RNG& rng) {
    Params result; result.a = 1 + rng.below(P - 1); result.b = rng.below(P); return result;
}
int hash_key(int key, const Params& h, int size) {
    return static_cast<int>(((h.a * key + h.b) % P) % size);
}
void check_key(int key) {
    if (key < 0 || key >= P) throw std::invalid_argument("key outside field universe");
}
struct Slot { bool used = false; int key = 0; };
struct Bucket { Params hash; std::vector<Slot> slots; };
class FKSSet {
public:
    RNG rng;
    int n;
    Params top;
    std::vector<Bucket> buckets;
    std::int64_t top_trials = 0, secondary_trials = 0, secondary_slots = 0;
    explicit FKSSet(const std::vector<int>& keys, std::int64_t seed = 7, int max_trials = 256)
        : rng(seed), n(static_cast<int>(keys.size())) {
        if (max_trials < 1 || keys.size() > 10000) throw std::invalid_argument("invalid trial or input-size limit");
        for (int key : keys) check_key(key);
        std::vector<int> ordered = keys, temp(keys.size());
        for (int bit = 0; bit < 31; ++bit) {
            std::size_t zeros = 0;
            for (int key : ordered) if (((key >> bit) & 1) == 0) ++zeros;
            std::size_t low = 0, high = zeros;
            for (int key : ordered) {
                if (((key >> bit) & 1) == 0) temp[low++] = key; else temp[high++] = key;
            }
            ordered.swap(temp);
        }
        if (std::adjacent_find(ordered.begin(), ordered.end()) != ordered.end())
            throw std::invalid_argument("input keys must be distinct");
        if (n == 0) return;
        std::vector<std::vector<int>> groups;
        bool accepted = false;
        for (int attempt = 0; attempt < max_trials; ++attempt) {
            ++top_trials; Params h = parameters(rng); groups.assign(n, std::vector<int>());
            for (int key : keys) groups[hash_key(key, h, n)].push_back(key);
            std::int64_t q = 0;
            for (const auto& group : groups) q += static_cast<std::int64_t>(group.size()) * group.size();
            if (q <= 4LL * n) { top = h; secondary_slots = q; accepted = true; break; }
        }
        if (!accepted) throw std::runtime_error("first-level trial limit reached");
        for (const auto& group : groups) {
            Bucket bucket;
            int size = static_cast<int>(group.size() * group.size());
            if (group.size() <= 1) {
                bucket.slots.resize(group.size());
                if (!group.empty()) { bucket.slots[0].used = true; bucket.slots[0].key = group[0]; }
                buckets.push_back(std::move(bucket)); continue;
            }
            accepted = false;
            for (int attempt = 0; attempt < max_trials; ++attempt) {
                ++secondary_trials; Params h = parameters(rng); std::vector<Slot> slots(size); bool ok = true;
                for (int key : group) {
                    int j = hash_key(key, h, size);
                    if (slots[j].used) { ok = false; break; }
                    slots[j].used = true; slots[j].key = key;
                }
                if (ok) { bucket.hash = h; bucket.slots = std::move(slots); accepted = true; break; }
            }
            if (!accepted) throw std::runtime_error("secondary trial limit reached");
            buckets.push_back(std::move(bucket));
        }
    }
    std::pair<int, int> location(int key) const {
        check_key(key); if (n == 0) return {-1, -1};
        int i = hash_key(key, top, n); const Bucket& bucket = buckets[i];
        if (bucket.slots.empty()) return {-1, -1};
        int j = hash_key(key, bucket.hash, static_cast<int>(bucket.slots.size()));
        return bucket.slots[j].used && bucket.slots[j].key == key ? std::make_pair(i, j) : std::make_pair(-1, -1);
    }
    bool contains(int key) const { return location(key).first != -1; }
};
int main() {
    std::vector<int> keys = {0, 1, 2, 3, 4, 5, 6, 7}; FKSSet s(keys);
    std::cout << "keys=" << s.n << ", secondary slots=" << s.secondary_slots << '\n';
    std::cout << "top trials=" << s.top_trials << ", secondary trials=" << s.secondary_trials << ", raw draws=" << s.rng.draws << '\n';
    std::cout << "top parameters = (" << s.top.a << ", " << s.top.b << ")\n";
    for (int key : keys) { auto p = s.location(key); std::cout << key << " -> (" << p.first << ", " << p.second << ")\n"; }
    bool ok = !s.contains(9) && !s.contains(100) && !s.contains(static_cast<int>(P - 1));
    for (int key : keys) ok = s.contains(key) && ok;
    std::cout << "checks = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

import java.util.ArrayList;

public class Main {
    static final long P = 2147483647L, B = P - 1, RAW_RANGE = B * B;
    static class RNG {
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= P) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        long next() { state = (16807L * state) % P; ++draws; return state; }
        long below(long bound) {
            if (bound < 1 || bound > P) throw new IllegalArgumentException("invalid random bound");
            long limit = RAW_RANGE - RAW_RANGE % bound;
            while (true) {
                long u = next() - 1;
                long v = next() - 1;
                long r = u * B + v;
                if (r < limit) return r % bound;
            }
        }
    }
    static class Params {
        final long a, b;
        Params(long a, long b) { this.a = a; this.b = b; }
    }
    static Params parameters(RNG rng) {
        long a = 1 + rng.below(P - 1), b = rng.below(P);
        return new Params(a, b);
    }
    static int hashKey(int key, Params h, int size) { return (int)(((h.a * key + h.b) % P) % size); }
    static void checkKey(int key) {
        if (key < 0 || key >= P) throw new IllegalArgumentException("key outside field universe");
    }
    static class Bucket {
        final Params hash; final Integer[] slots;
        Bucket(Params hash, Integer[] slots) { this.hash = hash; this.slots = slots; }
    }
    static class FKSSet {
        final RNG rng;
        final int n;
        Params top = new Params(1, 0);
        final ArrayList<Bucket> buckets = new ArrayList<>();
        long topTrials, secondaryTrials, secondarySlots;
        FKSSet(int[] keys, long seed, int maxTrials) {
            rng = new RNG(seed);
            if (maxTrials < 1 || keys.length > 10000) throw new IllegalArgumentException("invalid trial or input-size limit");
            for (int key : keys) checkKey(key);
            int[] ordered = keys.clone(), temp = new int[keys.length];
            for (int bit = 0; bit < 31; ++bit) {
                int zeros = 0; for (int key : ordered) if (((key >>> bit) & 1) == 0) ++zeros;
                int low = 0, high = zeros;
                for (int key : ordered) {
                    if (((key >>> bit) & 1) == 0) temp[low++] = key; else temp[high++] = key;
                }
                int[] swap = ordered; ordered = temp; temp = swap;
            }
            for (int i = 1; i < ordered.length; ++i)
                if (ordered[i - 1] == ordered[i]) throw new IllegalArgumentException("input keys must be distinct");
            n = keys.length; if (n == 0) return;
            ArrayList<ArrayList<Integer>> groups = null; boolean accepted = false;
            for (int attempt = 0; attempt < maxTrials; ++attempt) {
                ++topTrials; Params h = parameters(rng); groups = new ArrayList<>();
                for (int i = 0; i < n; ++i) groups.add(new ArrayList<>());
                for (int key : keys) groups.get(hashKey(key, h, n)).add(key);
                long q = 0; for (ArrayList<Integer> group : groups) q += (long)group.size() * group.size();
                if (q <= 4L * n) { top = h; secondarySlots = q; accepted = true; break; }
            }
            if (!accepted) throw new IllegalStateException("first-level trial limit reached");
            for (ArrayList<Integer> group : groups) {
                int size = group.size() * group.size();
                if (group.size() <= 1) {
                    Integer[] slots = new Integer[group.size()];
                    if (!group.isEmpty()) slots[0] = group.get(0);
                    buckets.add(new Bucket(new Params(1, 0), slots)); continue;
                }
                accepted = false;
                for (int attempt = 0; attempt < maxTrials; ++attempt) {
                    ++secondaryTrials; Params h = parameters(rng); Integer[] slots = new Integer[size]; boolean ok = true;
                    for (int key : group) {
                        int j = hashKey(key, h, size);
                        if (slots[j] != null) { ok = false; break; }
                        slots[j] = key;
                    }
                    if (ok) { buckets.add(new Bucket(h, slots)); accepted = true; break; }
                }
                if (!accepted) throw new IllegalStateException("secondary trial limit reached");
            }
        }
        int[] location(int key) {
            checkKey(key); if (n == 0) return null;
            int i = hashKey(key, top, n); Bucket bucket = buckets.get(i);
            if (bucket.slots.length == 0) return null;
            int j = hashKey(key, bucket.hash, bucket.slots.length);
            return bucket.slots[j] != null && bucket.slots[j] == key ? new int[] {i, j} : null;
        }
        boolean contains(int key) { return location(key) != null; }
    }
    public static void main(String[] args) {
        int[] keys = {0, 1, 2, 3, 4, 5, 6, 7}; FKSSet s = new FKSSet(keys, 7, 256);
        System.out.println("keys=" + s.n + ", secondary slots=" + s.secondarySlots);
        System.out.println("top trials=" + s.topTrials + ", secondary trials=" + s.secondaryTrials + ", raw draws=" + s.rng.draws);
        System.out.println("top parameters = (" + s.top.a + ", " + s.top.b + ")");
        for (int key : keys) { int[] p = s.location(key); System.out.println(key + " -> (" + p[0] + ", " + p[1] + ")"); }
        boolean ok = !s.contains(9) && !s.contains(100) && !s.contains((int)(P - 1));
        for (int key : keys) ok = s.contains(key) && ok;
        System.out.println("checks = " + (ok ? "PASS" : "FAIL"));
    }
}

Run Python 3 directly, compile C++ with g++ -std=c++14 -O2 main.cpp -o fks, or use Java 17 or later with javac Main.java followed by java Main. The programs print these twelve lines:

• keys=8, secondary slots=14
• top trials=2, secondary trials=4, raw draws=24
• top parameters = (1143995257, 907828750)
• 0 -> (6, 3)
• 1 -> (7, 2)
• 2 -> (1, 3)
• 3 -> (3, 0)
• 4 -> (4, 0)
• 5 -> (6, 2)
• 6 -> (7, 1)
• 7 -> (1, 2)
• checks = PASS

The check covers every member and several nonmembers, including $9$, which reaches an occupied slot. Invalid keys, duplicates, invalid seeds, a nonpositive trial budget, and input-size overflow are rejected. Construction errors return no completed dictionary. The structure deliberately provides no mutating insert or delete operation after construction.

Complexity, Correctness, and Invariants

The textbook FKS guarantee is expected $O(n)$ construction time, $O(n)$ space, and worst-case $O(1)$ lookup, under the universal collision bound, independent fresh parameter choices, and constant-cost word arithmetic. The expectation concerns construction randomness, not a random distribution of the input keys. The accepted layout's space and query bounds are deterministic properties once it has been built successfully.

Why is first-level space linear? Let $C$ count unordered pairs of stored keys that collide at the first level. Counting contributions within each bucket gives

$$Q=\sum_i b_i^2=n+2C.$$

Since each distinct pair collides with probability at most $1/n$,

$$\mathbb E[Q]\le n+2\binom n2\frac1n=2n-1.$$

Markov's inequality therefore bounds the probability of rejecting a first-level candidate with $Q\gt4n$ by less than $1/2$ for nonempty input. Independent retries take fewer than two trials in expectation. Each trial creates $n$ bucket lists, scatters $n$ keys, and computes their squared sizes in $O(n)$ work, even when the resulting $Q$ is too large.

For a bucket with $b\ge2$ keys and $b^2$ slots, let $C_b$ count colliding pairs. The local universal bound gives

$$\mathbb E[C_b]\le\binom b2\frac1{b^2}=\frac{b-1}{2b}\lt\frac12.$$

Because $C_b$ is a nonnegative integer, $\Pr(C_b\ge1)\le\mathbb E[C_b]\lt1/2$. Thus a fresh local candidate succeeds with probability greater than $1/2$ and takes fewer than two trials on average. Allocating, clearing, and trying one local array costs $O(b^2+b)=O(b^2)$. Summing expected costs over the accepted buckets gives $O(Q)=O(n)$.

The bounded code preserves the first-level threshold before allocating secondary arrays. With trial cap $L$, outer grouping costs $O(Ln)$, and local candidate initialization and insertion cost at most $O(L\sum_i b_i^2)=O(Ln)$. Input validation adds $O(n+1)$ work for fixed $31$-bit keys; parameter generation adds $O(D)$. Empty input takes constant time. Under ideal bounded draws, expected total construction remains $O(n+1)$; with a fixed seed, the program is deterministic, and a trial limit can reject an otherwise feasible set.

The accepted arrays, input-validation buffers, bucket lists, metadata, and one current trial use $O(n+1)$ logically live space. Discarded arrays may await collection in managed runtimes. The bound is in machine words, not “a constant number of bits per key”: this dictionary stores full keys and hash parameters.

To justify the chosen hash family exactly, take two distinct field keys. A uniform nonzero $a$ and uniform $b$ send them uniformly to an ordered pair of distinct field residues. Reduction modulo a target size $m\le P$ groups those residues into classes of sizes differing by at most one. Counting distinct residue pairs in the same class yields collision probability at most $1/m$. This is a universal collision bound, not a claim of mutual independence among every final hash output.

Correctness is checked rather than inferred from probability. A collision causes rejection before a resident key can be overwritten. Retrying a bucket begins with fresh empty slots, and a bucket is retained only after all its members are placed. The outer hash, each local parameter pair, local size, and slot contents must be stored together; a query recomputes precisely the route used during construction.

With ideal independent choices and cap $L$, a union bound gives whole-build trial-exhaustion probability at most $(n+1)2^{-L}$: one outer stage and at most $n$ local stages can each exhaust their budget. This is an upper bound in the stated random model, not a numerical promise about the small deterministic generator. After a successful build there is no residual probability of a stored-key collision, because those collisions were explicitly checked.

Variants, Pitfalls, and Optimizations

The most important query mistake is equating “occupied candidate slot” with membership. The sample's nonmember $9$ reaches the same slot as stored key $4$. FKS is perfect on $S$, not injective over the entire universe, so an exact dictionary must compare keys or use an equally exact verification representation.

Other design choices affect different guarantees:

• Reject or deliberately normalize duplicates. Two equal keys cannot be separated by any deterministic hash. The code rejects them; a map builder might instead specify a rule for duplicate values before starting FKS construction.
• Check total squared size. Giving every bucket a quadratic local array is not enough by itself: one first-level bucket holding all $n$ keys would require $n^2$ slots. The global $Q$ test supplies the deterministic linear-space guarantee.
• Retry the correct level. A large $Q$ requires a new outer partition. A local collision requires only a new local hash for that bucket. Repeating identical parameters and identical keys cannot repair the same collision.
• Clear discarded candidates completely. Reusing occupancy from a failed local trial can cause false collisions or retain keys at indices belonging to old parameters. Fresh arrays make the invariant explicit.
• Protect arithmetic and domains. Multiplying $a$ and a key in $32$ bits silently changes the family. Keys that are congruent modulo $P$ cannot be distinguished by this field representation, so simply accepting arbitrary larger integers would break the construction assumptions.
• Keep static and dynamic designs separate. Adding a new key can create a local collision or change the required capacity. Dynamic perfect hashing needs additional mechanisms; this implementation rebuilds from a new set instead of offering a misleading constant-time insertion method.
• Distinguish perfect from minimal. The sample uses $14$ secondary slots for $8$ keys and is not minimal. A minimal perfect function still maps a nonmember somewhere in its range; whether membership is known in advance or verified later is part of its API.

A map version stores each key's associated payload beside the key and moves both together during construction. Variable-length strings need an injective representation or a carefully analyzed preprocessing strategy; a fingerprint collision cannot be ignored in an exact dictionary. Hashing a long string also changes the query cost relative to the fixed-word model.

Implementation optimizations can skip trivial singleton hashes, store local arrays contiguously with bucket offsets, and clear failed candidate arrays efficiently. Such changes must preserve the same space score, collision test, and full-key comparison. Compact or minimal perfect hashing schemes use additional ideas rather than changing the meaning of “no collisions on the member set.”

Practice Problems and Real-World Use

Compare every query against an independent reference set. Scan the completed structure to verify that every input key appears once, every occupied slot matches the outer and local hashes, and no two input keys share a final pair. Recompute $Q$ and verify both the allocated slot count and the $4n$ acceptance limit.

Include empty and singleton inputs, dense and widely spaced field keys, the largest valid key, duplicates, invalid universe values, and both kinds of retry-budget error. Deliberately query nonmembers that hit occupied slots. Replay the same seed to compare parameters, layouts, and counters across languages, while using exact small-prime enumeration to test the universal-family probability bound independently of the seeded generator.

See the original Fredman–Komlós–Szemerédi paper for the static-dictionary foundation and MIT's universal and perfect hashing notes for the two-level construction and collision-count analysis. The explicit space and collision checks above are what turn randomized parameter search into a verified lookup structure.