Why architecture matters here
The architecture matters because the quotient filter's memory-access pattern is what makes it fast in practice, and access pattern is invisible in a big-O analysis. A Bloom filter's lookup sets or checks k bits at k independent hash positions scattered across a large bit array; at scale each of those probes is likely a cache miss, so a single membership test can cost k trips to main memory. The quotient filter instead concentrates everything about a key into one home slot and a short run of adjacent slots, so a lookup reads a handful of contiguous bytes — typically one cache line. On modern hardware, where a cache miss costs a hundred times a cache hit, this difference dominates: the quotient filter can be several times faster than a Bloom filter for the same false-positive rate despite doing more arithmetic per operation, purely because it respects the memory hierarchy.
The second forcing function is resizability. A Bloom filter is sized up front for an expected element count and target false-positive rate, and if you exceed that count the false-positive rate degrades and there is no way to grow it without rebuilding from the original keys — which you usually no longer have. The quotient filter stores each element's fingerprint (split into quotient and remainder), so it retains enough information to rehash every element into a larger array when it gets full. Growth is possible without the source data. For workloads where the element count is unknown or unbounded — a streaming dedup, a growing set — this ability to grow in place is the deciding advantage.
The third reason is mergeability, which distributed and parallel systems need. Two quotient filters over the same hash function can be combined into one by a linear merge of their sorted runs, because each stores real fingerprints that can be reconciled. This lets a system build partial filters in parallel — one per shard, one per worker — and merge them into a global filter afterward, or union two sets' membership summaries. Bloom filters can only be OR-merged if they share identical size and hash seeds and even then cannot recover per-element fingerprints; the quotient filter's explicit fingerprints make true merging and even (with counting variants) deletion feasible.
The fourth architectural consideration is the honest cost: the quotient filter degrades as it fills. Its performance depends on runs and clusters staying short, and as the load factor climbs toward one, collisions on home slots grow, runs lengthen, and the shifting needed to keep runs contiguous cascades into long clusters — so both inserts and lookups slow markedly in the last stretch before full. This means a quotient filter must be operated with headroom, resized before it gets too dense, and sized with its load-factor curve in mind rather than packed to the last slot. Understanding that its speed is a function of occupancy — excellent at moderate load, sharply worse near capacity — is essential to deploying it well, and is the counterweight to its flexibility.
The architecture: every piece explained
Top row: the split that defines the structure. A key is hashed to a single fingerprint of p bits. That fingerprint is divided: the top q bits are the quotient, which is used directly as an index — the key's home slot — into the slot array; the low r bits are the remainder, which is the only part actually stored, placed in a slot. This is the quotienting trick: the quotient is not stored because it is encoded by which slot region the remainder lives in, so the structure keeps only r bits per element instead of the full p. The slot array is one contiguous array of r-bit slots (plus three metadata bits each), and remainders belonging to the same home slot are kept together, in sorted order, as a run.
Middle row: the three metadata bits that make it all decodable. Because many keys can share a home slot, and because a run may be shifted away from its home slot when the home is occupied by an earlier run, three bits per slot record the structure. is_occupied marks a slot as the home of at least one stored key (some key's quotient equals this index). is_continuation marks a slot as a non-first member of a run — it continues the run of the previous slot rather than starting a new home's run. is_shifted marks a slot whose contents were pushed rightward from their true home because that home was occupied. Together these three bits let a lookup reconstruct, from a compact encoding, exactly which run belongs to which home slot.
Bottom row: scanning, and the operations flexibility buys. A cluster scan is how lookup works: from the home slot, the algorithm walks left to the start of the cluster (a maximal run of occupied, shifted slots) and then rightward, counting runs via the metadata bits until it reaches the run belonging to this key's home, then compares stored remainders against the query's remainder. Resize / merge is the flexibility: because fingerprints are preserved, the filter can be rehashed into a bigger array, and two filters can be merged by linearly walking their runs. Load factor is the governing tension — as occupancy rises, clusters lengthen and every operation's scan grows. The ops strip names the signals: occupancy, false-positive rate, cluster length, and resize cost.
End-to-end flow
Walk an insert and a lookup through a lightly-loaded quotient filter. Insert key x: hash it to a fingerprint, split into quotient q (say slot 5) and remainder r. Slot 5 is empty, so mark it is_occupied, store r there, and clear its continuation and shifted bits — a run of one at its home. Insert key y whose quotient is also 5: slot 5's home already has a run, so y's remainder joins that run in slot 6, marked is_continuation (it continues slot 5's run) and is_shifted (it is not in its own home, which does not exist — its home is 5). The two remainders for home 5 now sit sorted in slots 5 and 6. Insert key z with quotient 6: its home slot 6 is occupied by y's shifted remainder, so z's remainder shifts right to slot 7, slot 6 is marked is_occupied (z homes here), and slot 7 is marked is_shifted. The cluster spanning slots 5–7 now encodes two homes' runs unambiguously via the bits.
Now look up a key w with quotient 6. The algorithm goes to slot 6, sees is_occupied set (some key homes here), then walks left to find the cluster's start — slot 5, the first non-shifted occupied slot — and scans rightward, using is_occupied to count home slots and is_continuation to delimit runs. It counts: home 5's run (slots 5–6), then home 6's run (slot 7), lands on slot 7 as w's home's run, and compares w's remainder against the stored remainder. If it matches, the filter answers 'probably present'; if not, 'definitely absent'. The entire lookup touched slots 5–7 — three adjacent slots, one cache line — which is the cache-friendliness the whole design exists to deliver.
As the filter fills, watch the degradation the operational playbook warns about. At low occupancy, clusters are one or two slots and scans are trivial. As occupancy climbs past three-quarters, collisions on home slots proliferate, runs lengthen, and shifting cascades so clusters stretch across many slots; a lookup that once touched three slots now walks fifteen, and an insert that shifts a long run pays for moving all of it. The average operation cost, flat at moderate load, curves sharply upward near full. This is the signal the occupancy metric exists to catch.
Before the filter gets too dense, a resize fires: allocate a new array twice the size (one more quotient bit), and rehash every element — each stored remainder plus its implicit quotient reconstitutes the original fingerprint, which is re-split against the larger array and reinserted. The rebuilt filter is half as loaded, so clusters shrink and speed returns. Separately, if two shards each built a quotient filter over the same hash, a merge walks both slot arrays in tandem, reconstructing fingerprints and inserting them into a combined filter — producing one global membership summary from parallel partial ones. The cycle of split, store, scan, resize, and merge is what gives the quotient filter its blend of speed and flexibility.