add and contains, packing the bit array into u64 words and deriving k hash functions from just two with the double-hashing trick;Learn Zig Series):Every single structure in this run of the series -- the linked list, the skip list, the three flavours of balanced tree, and last week's trie -- shares one habit so deep you probably never questioned it: they all keep the keys. Insert "cat" and somewhere in memory the three bytes c, a, t live on, ready to be handed back, compared, walked, enumerated. That is exactly what you want when you need to retrieve things. But I closed episode 110 by pointing at a whole family of problems where you never retrieve anything at all -- where the only question you ever put to the set is "have I seen this key before?" and a plain yes-or-no is the entire answer. A spam filter checking a URL against a billion known-bad ones. A database deciding whether to bother touching the disk. A crawler skipping a page it already fetched. For those, storing every key exactly is a fortune in RAM spent to answer a one-bit question.
The bloom filter is the structure that takes that observation seriously and runs with it, further than feels reasonable. It stores none of the keys. Not a compressed copy, not a hash of them -- nothing you could ever read back. What it keeps is a bare bit array and a promise, and the promise is a strange one: it will tell you "definitely not present" and be right every single time, or tell you "probably present" and be wrong just often enough that you get to choose how often, in advance, by turning a dial. First though, the debt from last week -- three exercises, and the third was a proper generalisation.
Exercise 1 -- remove with pruning. Clearing a word's is_word flag is the easy half; the interesting half is reclaiming the nodes that clearing it stranded. The trick is that pruning has to happen on the way back up the recursion: a node is safe to free only once you know it has no children and is not itself a word. So the recursive helper returns a bool -- "I freed myself, unhook me" -- and each parent nulls the child slot and checks whether it too has become a dead leaf.
// Returns true if `node` was freed, so the caller must null the slot that pointed here.
fn removeNode(self: *Self, node: *Node, word: []const u8, depth: usize) bool {
if (depth == word.len) {
if (!node.is_word) return false; // word was never stored; change nothing
node.is_word = false;
self.len -= 1;
} else {
const idx = word[depth] - 'a';
const child = node.children[idx] orelse return false; // path breaks: absent
if (self.removeNode(child, word, depth + 1)) node.children[idx] = null;
}
// prune: a node with no children and no word flag is dead weight -- free it upward.
if (node.is_word) return false;
for (node.children) |c| if (c != null) return false; // still a junction, keep it
if (node == self.root.?) return false; // never free the root here
self.allocator.destroy(node);
return true;
}
fn remove(self: *Self, word: []const u8) bool {
const before = self.len;
_ = self.removeNode(self.root orelse return false, word, 0);
return self.len != before; // len only drops if a real word was cleared
}
The insight is that pruning is the mirror of insertion: insert creates nodes top-down as it discovers they are missing, remove destroys them bottom-up as it discovers they are pointless. Removing cart from {car, cart} clears the t node's flag, frees the now-childless t, then stops dead at r because car still flies its is_word flag -- so car stays findable and startsWith("car") stays true, exactly as the test demands.
Exercise 2 -- countWordsWithPrefix, two ways. The on-demand version walks the subtree under the prefix and tallies every is_word it meets. The cached version pays at write time instead: every node carries a subtree_words counter that insert bumps along the whole path, so the query becomes a single find plus one field read -- O(k), no subtree walk at all.
// Way 1: walk the subtree on every query. Zero write-time cost, O(subtree) per read.
fn countSubtree(node: *Node) usize {
var total: usize = if (node.is_word) 1 else 0;
for (node.children) |c| if (c) |child| {
total += countSubtree(child);
};
return total;
}
fn countWordsWithPrefix(self: *Self, prefix: []const u8) usize {
const node = self.find(prefix) orelse return 0;
return countSubtree(node);
}
// Way 2: maintain a counter in each node so the query is O(k). insert() must bump every
// node it walks through -- shown here as the delta from the episode's insert().
fn insertCounted(self: *Self, word: []const u8) !void {
if (self.root == null) self.root = try self.newNode();
var node = self.root.?;
node.subtree_words += 1; // the root sees every word
for (word) |c| {
const idx = c - 'a';
if (node.children[idx] == null) node.children[idx] = try self.newNode();
node = node.children[idx].?;
node.subtree_words += 1; // every node on the path gains one
}
if (!node.is_word) { node.is_word = true; self.len += 1; }
}
Which one would I ship? It depends entirely on the read/write ratio. A dictionary loaded once and queried a million times a second (an autocomplete backend) wants the cached counter -- reads dominate, so pay at the rare write. A structure churning constantly with few prefix-count queries wants the on-demand walk, because the cached version taxes every insert whether anyone ever asks or not. That "move the cost to whichever operation is rarer" instinct is one of the most reusable judgements in all of engineering.
Exercise 3 -- the generic Trie(comptime R, comptime indexOf). This is the one that pulls the a-z assumption out of the code entirely and hands it to comptime, exactly as we have parameterised every generic since episode 14. The alphabet size R sizes the child array, and a comptime indexOf function maps a byte to a slot -- so the same definition yields a lowercase trie, a full-byte trie, and a four-letter DNA trie, each monomorphised with zero runtime cost.
const TrieError = error{InvalidCharacter};
fn Trie(comptime R: usize, comptime indexOf: fn (u8) TrieError!usize) type {
return struct {
const Self = @This();
const Node = struct {
children: [R]?*Node = [_]?*Node{null} ** R,
is_word: bool = false,
};
root: ?*Node = null,
allocator: std.mem.Allocator,
fn init(allocator: std.mem.Allocator) Self {
return .{ .allocator = allocator };
}
fn insert(self: *Self, word: []const u8) !void {
if (self.root == null) {
self.root = try self.allocator.create(Node);
self.root.?.* = .{};
}
var node = self.root.?;
for (word) |c| {
const idx = try indexOf(c); // comptime-supplied policy, checked
if (node.children[idx] == null) {
node.children[idx] = try self.allocator.create(Node);
node.children[idx].?.* = .{};
}
node = node.children[idx].?;
}
node.is_word = true;
}
};
}
// Three alphabets, three purpose-built tries -- and @sizeOf(Node) tells the whole story.
fn lowerIndex(c: u8) TrieError!usize {
if (c < 'a' or c > 'z') return TrieError.InvalidCharacter;
return c - 'a';
}
fn dnaIndex(c: u8) TrieError!usize {
return switch (c) { 'A' => 0, 'C' => 1, 'G' => 2, 'T' => 3, else => TrieError.InvalidCharacter };
}
const LowerTrie = Trie(26, lowerIndex); // Node is ~208 bytes: 26 pointers + a flag
const ByteTrie = Trie(256, byteIndex); // Node is ~2 KB: the version you never ship as-is
const DnaTrie = Trie(4, dnaIndex); // Node is ~32 bytes: lean, four fat edges
Measuring @sizeOf(LowerTrie.Node) against @sizeOf(ByteTrie.Node) makes the R-way trie's memory problem impossible to argue with -- the 256-way node is roughly ten times the size of the 26-way one, almost all of it null pointers. That is precisely the "waste" I promised we would confront, and it is the perfect springboard into today's structure, which attacks the memory problem from the opposite direction entirely. Debt paid. On to the bit array ;-)
Here is the whole bloom filter in a picture. Take an array of m bits, all zero. Pick k independent hash functions, each of which maps any key to a bit position in 0..m. To add a key, hash it k times and set those k bits to 1. To test a key, hash it the same k times and look: if any of those k bits is still 0, the key was definitely never added -- because adding it would have set that very bit. If all k bits are 1, the key is probably present.
That asymmetry is the soul of the thing, so sit with it a second. A false negative is impossible. If the key had been added, its k bits would be set, full stop -- so "any bit is 0" is an airtight proof of absence. A false positive, though, is entirely possible: the k bits for a key you never added might all happen to have been set by other keys, a coincidental collision across k independent positions. The filter cannot tell "I set these bits for this key" from "these bits got set by some combination of other keys". So it hedges, honestly: "probably".
The consequences fall straight out of that picture, and they are the reason the bloom filter is a genuinely different animal from everything before it:
m bits and k hashes -- that is all. Whether your keys are three-byte tickers or three-kilobyte URLs, the filter is the same handful of bytes. Contrast the trie, whose memory grows with every character of every key, or the hash set, which stores the keys outright.n and your tolerable error rate p, and it hands back the m and k that hit it. Want one-in-a-million false positives instead of one-in-a-hundred? Spend a few more bits per key. It is a smooth, predictable trade -- space for certainty.Having said that, let's build one and watch the trade play out in real bits.
I'll pack the bits into a slice of u64 words -- 64 bits to a word, the natural unit the CPU pushes around. Bit i lives in word i / 64 (which I write i >> 6) at position i % 64 (which I write i & 63), the exact bit-twiddling we first met back in episode 17 when we packed flags into integers. The struct holds the words, the bit count m, the hash count k, and an allocator, because m is a runtime choice here and the array lives on the heap.
const std = @import("std");
const BloomFilter = struct {
const Self = @This();
bits: []u64, // the bit array, packed 64 bits per word
num_bits: usize, // m -- total addressable bits (>= 64 * bits.len)
num_hashes: usize, // k -- how many bits each key touches
allocator: std.mem.Allocator,
fn init(allocator: std.mem.Allocator, num_bits: usize, num_hashes: usize) !Self {
const num_words = (num_bits + 63) / 64; // round the bit count up to whole words
const words = try allocator.alloc(u64, num_words);
@memset(words, 0); // every bit starts at 0 -- an empty set
return .{
.bits = words,
.num_bits = num_words * 64, // the true capacity after rounding up
.num_hashes = num_hashes,
.allocator = allocator,
};
}
fn deinit(self: *Self) void {
self.allocator.free(self.bits); // one slice, one free -- no per-node walk this week
}
fn setBit(self: *Self, i: usize) void {
self.bits[i >> 6] |= (@as(u64, 1) << @intCast(i & 63)); // OR the one bit on
}
fn testBit(self: *const Self, i: usize) bool {
return (self.bits[i >> 6] & (@as(u64, 1) << @intCast(i & 63))) != 0;
}
};
Notice how much quieter teardown is than it has been for weeks. The trie needed a recursive post-order free; the red-black tree the same. A bloom filter is one flat allocation, so deinit is a single free. There are no nodes, no pointers chasing pointers -- the entire structure is one contiguous run of bytes, which (spoiler for the performance section) is also why it is so brutally cache-friendly.
The textbook description says "k independent hash functions", and a naive reader reaches for k separate hash algorithms. Don't -- that is slow and needless. The Kirsch-Mitzenmacher result (a genuinely lovely little theorem) proves you can synthesise as many hash functions as you like from just two real ones: the i-th derived hash is simply h1 + i * h2. The false-positive rate is asymptotically identical to using k truly independent hashes, and you compute the input's real hash exactly twice regardless of how big k gets. I'll take two Wyhash results with different seeds as my h1 and h2.
// Two real hashes, seeded differently, are all we need -- the rest are derived arithmetically.
fn hashPair(key: []const u8) [2]u64 {
return .{
std.hash.Wyhash.hash(0x9E3779B97F4A7C15, key), // seed 1 (golden-ratio constant)
std.hash.Wyhash.hash(0xD1B54A32D192ED03, key), // seed 2 (a different odd constant)
};
}
fn add(self: *Self, key: []const u8) void {
const h = hashPair(key);
var i: usize = 0;
while (i < self.num_hashes) : (i += 1) {
// Kirsch-Mitzenmacher: derived hash i = h1 + i*h2, wrapping (+%) to stay in u64.
const combined = h[0] +% (@as(u64, @intCast(i)) *% h[1]);
self.setBit(combined % self.num_bits);
}
}
fn contains(self: *const Self, key: []const u8) bool {
const h = hashPair(key);
var i: usize = 0;
while (i < self.num_hashes) : (i += 1) {
const combined = h[0] +% (@as(u64, @intCast(i)) *% h[1]);
if (!self.testBit(combined % self.num_bits)) return false; // a 0 bit -> DEFINITELY absent
}
return true; // every bit set -> PROBABLY present (this is the only line that can lie)
}
The +% and *% are Zig's wrapping arithmetic operators, and they are load-bearing, not lazy. A plain + or * on a u64 that overflows is a panic in a safe build -- Zig refuses to silently wrap by default, one of the language's sharper edges. But here wrap-around is exactly the behaviour I want: the hash math is modular by nature, so I tell the compiler "yes, wrapping is intended" explicitly with +%. That one-character difference is Zig making me state my intent out loud instead of guessing it -- the same philosophy that turned integer overflow from C's silent landmine into a decision you have to sign for.
The single line that can ever lie to you is the final return true. Every return false above it is backed by proof -- a bit that is 0 could not have been set by adding this key. Only "all bits set, therefore probably present" carries the sliver of doubt. Which is a nice property to be able to point at in a code review: here, this one line, is where all the uncertainty in the whole structure lives.
The version above takes num_bits and num_hashes as runtime arguments, which is flexible but leaves the caller to compute good values and leaves the array on the heap. For the very common case where you know your target capacity and error rate at compile time, Zig lets you do far better: bake the whole sizing into the type, so the bit array becomes a fixed-size array living on the stack with no allocator in sight. This is the comptime through-line of the entire series -- push everything that never changes at runtime into the compile step, and what remains is lean.
// Given target capacity n and false-positive rate p, the classic formulas:
// m = -n*ln(p) / (ln 2)^2 (bits needed)
// k = (m/n) * ln 2 (optimal hash count)
fn optimalBits(n: usize, p: f64) usize {
const nf: f64 = @floatFromInt(n);
const m = -(nf * @log(p)) / (std.math.ln2 * std.math.ln2);
return @intFromFloat(@ceil(m));
}
fn optimalHashes(m: usize, n: usize) usize {
const ratio: f64 = @as(f64, @floatFromInt(m)) / @as(f64, @floatFromInt(n));
return @max(1, @as(usize, @intFromFloat(@round(ratio * std.math.ln2))));
}
// A filter whose size is decided by the compiler. No allocator, no heap, no deinit.
fn StaticBloom(comptime n: usize, comptime p: f64) type {
const m = optimalBits(n, p);
const num_words = (m + 63) / 64;
return struct {
const Self = @This();
const num_bits = num_words * 64;
const num_hashes = optimalHashes(m, n);
bits: [num_words]u64 = [_]u64{0} ** num_words, // zeroed at comptime, lives on the stack
fn add(self: *Self, key: []const u8) void {
const h = hashPair(key);
inline for (0..num_hashes) |i| { // k is known at comptime -> the loop unrolls
const combined = h[0] +% (@as(u64, i) *% h[1]);
const idx = combined % num_bits;
self.bits[idx >> 6] |= (@as(u64, 1) << @intCast(idx & 63));
}
}
fn contains(self: *const Self, key: []const u8) bool {
const h = hashPair(key);
inline for (0..num_hashes) |i| {
const combined = h[0] +% (@as(u64, i) *% h[1]);
const idx = combined % num_bits;
if ((self.bits[idx >> 6] & (@as(u64, 1) << @intCast(idx & 63))) == 0) return false;
}
return true;
}
};
}
Look at what comptime bought us. StaticBloom(1_000_000, 0.01) computes its m (about 9.6 million bits, ~1.2 MB) and its k (7) at compile time, sizes the array to match, and the inline for unrolls the hash loop entirely because k is a compile-time constant -- there is no loop counter, no branch, just seven straight-line bit operations. The type carries its own configuration, and a filter for a different capacity is a genuinely different type the compiler builds for you. No garbage collector, no allocation failure to handle, no deinit to forget. This is the sort of thing that makes me quietly happy every time -- the abstraction costs nothing at runtime because it was all spent before the program ran.
Testing something that is allowed to be wrong feels slippery at first, but it splits cleanly into two very different claims. One is absolute and must never break: no false negatives. The other is statistical: the false-positive rate should land near the target you asked for. You test the first with a hard assertion, and the second with a tolerance band -- and mixing those two up is the classic rookie mistake.
test "bloom filter: zero false negatives, ever" {
var bf = try BloomFilter.init(std.testing.allocator, 8192, 5);
defer bf.deinit();
// Add a batch of keys, then demand every single one reports present. This can NEVER fail.
var buf: [16]u8 = undefined;
var i: usize = 0;
while (i < 500) : (i += 1) {
const key = try std.fmt.bufPrint(&buf, "key-{d}", .{i});
bf.add(key);
}
i = 0;
while (i < 500) : (i += 1) {
const key = try std.fmt.bufPrint(&buf, "key-{d}", .{i});
try std.testing.expect(bf.contains(key)); // a false negative here is a real bug
}
}
The second test probes the statistical claim -- fill the filter to its design capacity, then hammer it with keys that were never added and count how many wrongly report present.
test "bloom filter: false-positive rate is in the right ballpark" {
// Size for n=1000 at p=0.01, then probe with 10000 keys we NEVER added.
const n = 1000;
var bf = try BloomFilter.init(std.testing.allocator, optimalBits(n, 0.01), optimalHashes(optimalBits(n, 0.01), n));
defer bf.deinit();
var buf: [24]u8 = undefined;
var i: usize = 0;
while (i < n) : (i += 1) { // fill it to its design capacity
const key = try std.fmt.bufPrint(&buf, "member-{d}", .{i});
bf.add(key);
}
var false_positives: usize = 0;
i = 0;
while (i < 10000) : (i += 1) { // absent keys -- any "present" is a false positive
const key = try std.fmt.bufPrint(&buf, "stranger-{d}", .{i});
if (bf.contains(key)) false_positives += 1;
}
const rate = @as(f64, @floatFromInt(false_positives)) / 10000.0;
try std.testing.expect(rate < 0.03); // target 0.01, allow slack -- it is a random process
}
The first test is the one I would defend hardest: it asserts the guarantee that makes bloom filters usable at all. If a false negative ever slips through, every system built on top -- every "skip the disk read because the filter says absent" -- is silently broken, returning wrong answers with total confidence. The second test is deliberately loose: I target 1% but assert only that we stay under 3%, because a false-positive rate is a sample from a random process and a tight assertion would flap. Nota bene: never pin a statistical test to an exact value -- assert the band the math allows, or you will spend your life re-running a "failing" green build.
Time first, because it is uniformly excellent and barely depends on anything. add and contains are both O(k) -- a fixed number of hash computations and bit probes, dead independent of how many keys you have stored. With k typically between 5 and 15, that is a tiny constant. There is no tree to descend, no chain to walk, no rehashing when the load factor climbs. A bloom filter's timing is about as flat as an algorithm gets.
The subtler performance story is cache. The bit array is one contiguous block, which is lovely, but the k probes scatter across it at hash-random positions -- so a single contains on a large filter can trigger k separate cache misses, each a trip to main memory that dwarfs the arithmetic. The standard fix is the blocked bloom filter: carve the array into cache-line-sized chunks, hash the key once to pick a chunk, and set all k bits within that one line. Now a query touches a single cache line instead of k scattered ones -- a big speedup for a slightly worse false-positive rate. It is the same species of trade we keep meeting: give up a sliver of theoretical quality to fit the hardware you actually run on.
On space, the bloom filter is the whole reason we are here. The rule of thumb worth memorising: about 9.6 bits per key for a 1% false-positive rate, and each additional factor-of-ten reduction in the error rate costs roughly 4.8 more bits per key. So a billion URLs at 1% fit in about 1.2 GB -- versus storing the URLs themselves, easily 100 GB or more. That is the trade laid bare: give up the keys and a controlled sliver of certainty, and the memory bill collapses by two orders of magnitude. For the "have I seen this?" question, nothing else is close.
The reach here is enormous, precisely because "cheaply prove something is absent" is such a common sub-problem. Databases are the giant: Cassandra, RocksDB, LevelDB, HBase and friends keep a bloom filter per on-disk table (SSTable), and before doing an expensive disk seek for a key, they ask the in-memory filter "could this key be in that file?". A "definitely not" -- which is most of the time -- skips the disk read entirely. That single trick is why log-structured storage engines stay fast as they accumulate hundreds of on-disk files. Web infrastructure leans on them everywhere: CDNs and proxies use a filter to answer "have we cached this URL?" before checking the real cache; the classic "don't show a one-hit-wonder" cache admission policy is a bloom filter deciding whether a URL has been requested before.
Your browser ships one -- historically, Chrome's Safe Browsing checked every URL you visited against a local bloom filter of known-malicious sites, and only on a "probably bad" hit did it phone home for the definitive check, keeping the common (safe) case entirely local and private. Spell-checkers did the original trick decades ago: the whole dictionary as a bloom filter, a word flagged as misspelled only when the filter says "definitely not a word". And distributed systems use them to slim down set-reconciliation -- shipping a compact filter of "keys I have" across the network instead of the keys themselves, so the other side can cheaply spot what it is missing.
The contrast with the trie from last week is the sharpest in the whole series. The trie stores keys exactly and can hand every one of them back, sorted, spelled out -- and pays in memory that grows with the data. The bloom filter stores no keys, can hand back nothing, cannot even be enumerated -- and pays a fixed, tiny amount of memory plus a controlled chance of a wrong "yes". Same abstract job (membership testing), opposite ends of the fidelity spectrum. When you need the keys back, the trie or a hash set. When you only need a fast, space-cheap "probably / definitely not", the filter wins by a mile.
In C, a bloom filter is honestly one of the friendliest structures to write -- a malloc'd array of uint64_t, a couple of hash functions, and bit-twiddling with |= and &. No pointers-to-pointers, so none of the teardown-leak hazards that dog the tree structures; a single free and you are done. The one recurring C bug is a weak or single hash function producing correlated bit positions, which quietly inflates the false-positive rate above what the math predicted -- a failure that no crash or valgrind run will ever flag, because the code is "working", just poorly.
In Rust, the bloom filter is a rare structure that does not pick a fight with the borrow checker, for the same reason the trie was pleasant: there are no internal references at all, just a Vec<u64> or a bitvec of owned bits. Ownership is trivially a single flat buffer, teardown is automatic, and the crates (bloomfilter, fastbloom) are thin. Rust's real contribution here is trait-based hashing -- you parameterise over a Hasher and the type system keeps you from accidentally mixing hash strategies between add and contains, which would silently break the guarantee.
In Go, it is a []uint64 and a hash/fnv or hash/maphash, the garbage collector handles the one allocation, and popular libraries (willf/bloom) wrap it in a few hundred lines. Short and safe, at the usual Go cost of a hash interface with some call overhead on the hot path. Our Zig version sits where it always does: the bit array sized either at runtime with an explicit allocator you can point at an arena (episode 26), or baked entirely into the type with comptime so it lives on the stack and the hash loop unrolls to straight-line code. Same structure across all four languages -- but only in Zig do you get to decide, per use, whether it costs a heap allocation or nothing at all, and see that decision in the type.
Add a estimateCount(self: *const Self) f64 method that estimates how many distinct keys have been added, using only the bit array -- no counter. The formula is -(m/k) * ln(1 - X/m), where X is the number of set bits and m, k are the filter's parameters. Count the set bits with @popCount over the u64 words (episode 17's population count), then apply the formula. Test it by adding a known number of keys and asserting the estimate lands within, say, 5% of the truth. Why does the estimate get less reliable as the filter fills toward saturation?
Implement a union of two bloom filters: given two filters with identical m and k, produce a third whose membership set is the union of the inputs. The trick is almost embarrassingly simple (bitwise-OR the two bit arrays word by word), but the precondition is the interesting part -- write it as a function that returns error.Mismatch if the two filters differ in size or hash count, since OR-ing incompatible filters produces silent garbage. Why can you union bloom filters this cheaply, but you cannot intersect them to get an exact set-intersection (what goes wrong)?
Build a counting bloom filter: replace each single bit with a small counter (say a u4 nibble), so add increments the k counters and a new remove decrements them -- finally giving the structure the deletion it lacks. Store the counters packed two-per-byte, implement add, remove, and contains (a key is present if all k counters are non-zero), and write a test proving that after add(x); add(y); remove(x), the filter still reports y present and x absent. Then answer the sharp question in a comment: deletion works now, but what did you pay for it in memory, and what happens catastrophically if a 4-bit counter overflows past 15?
Step back and stare at the one thing the bloom filter cannot do, because that hole is the doorway to the next episode. We can add and we can contains, and this week's exercise 3 hints at bolting on deletion by fattening every bit into a counter -- but look at what that costs: the memory advantage that justified the whole structure gets multiplied by the counter width, four-x for a nibble, eight-x for a byte, and the counters can still overflow and corrupt the filter permanently. So the counting bloom filter buys deletion at a price that partly undoes the reason you reached for a bloom filter in the first place. That is not a clean solution -- that is a workaround wearing a solution's coat.
So here is the question that the whole next step turns on. What if you could have a filter that supports deletion natively, cleanly, without inflating every slot into a counter -- and that, at the low false-positive rates real systems actually demand, is often more space-efficient than the classic bloom filter, not less? What if instead of scattering k bits across a giant array, you stored a tiny fingerprint of each key in one of a small number of candidate buckets, and let keys politely shove each other between their alternate homes to make room -- so that deleting a key is just erasing its fingerprint, no shared bits, no counters, no overflow? That structure exists, it borrows a trick from a hashing scheme with a mischievous name, and it is where we go next. One nest at a time ;-)
De groeten, en tot de volgende keer!
@scipio