Hashing and Hash Tables Questions

Direct answer

A Bloom filter is a bit array plus k hash functions: insert sets k bit positions per item, and might_contain reports present only if all k of an item's positions are set, which guarantees zero false negatives and a bounded, tunable false-positive rate. The catch is that bits are shared across items by design, so a single bit cannot be safely unset on removal, which is exactly what a Counting Bloom Filter fixes by replacing each bit with a small counter.

Structured elaboration

Sizing follows the standard formulas for expected item count n and target false-positive rate p: $m = -\frac{n\ln p}{(\ln 2)^2}$ bits and $k = \frac{m}{n}\ln 2$ hash functions, with k positions per item generated from two base hashes via $g_i(x) = h_1(x) + i\cdot h_2(x) \bmod m$ rather than implementing k independent hash functions.

import hashlib, math

class BloomFilter:
    def __init__(self, n_expected, p_target):
        self.m = max(1, math.ceil(-(n_expected * math.log(p_target)) / (math.log(2) ** 2)))
        self.k = max(1, round((self.m / n_expected) * math.log(2)))
        self.bits = bytearray(self.m)

    def _hashes(self, item):
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def insert(self, item):
        for idx in self._hashes(item):
            self.bits[idx] = 1

    def might_contain(self, item):
        return all(self.bits[idx] for idx in self._hashes(item))


class CountingBloomFilter(BloomFilter):
    def __init__(self, n_expected, p_target, counter_max=15):
        super().__init__(n_expected, p_target)
        self.counters = [0] * self.m
        self.counter_max = counter_max

    def insert(self, item):
        for idx in self._hashes(item):
            if self.counters[idx] < self.counter_max:
                self.counters[idx] += 1

    def remove(self, item):
        for idx in self._hashes(item):
            if self.counters[idx] > 0:
                self.counters[idx] -= 1

    def might_contain(self, item):
        return all(self.counters[idx] > 0 for idx in self._hashes(item))

Insert and might_contain both cost O(k), independent of how many items are already stored, which is the whole appeal versus a hash set whose per-operation cost depends on collision chains that grow with load. The no-deletion limitation is structural, not an implementation oversight: two different items can legitimately share one of their k bit positions, so unsetting a bit because one item is "removed" can silently flip another still-present item to a false negative, which breaks the Bloom filter's core guarantee. A Counting Bloom Filter avoids this by storing a small saturating counter (here capped at 15, fitting a 4-bit slot) at each position instead of a single bit: insert increments, remove decrements, and might_contain checks that every relevant counter is still above zero, so one item's removal only affects a shared position if that position's count truly drops to zero.

Worked example

n_expected, p_target = 1000, 0.01
bf = BloomFilter(n_expected, p_target)
print(f"BloomFilter sized: m={bf.m} bits, k={bf.k} hash functions")

inserted = [f"doc-{i}" for i in range(n_expected)]
for item in inserted:
    bf.insert(item)

false_negatives = sum(1 for item in inserted if not bf.might_contain(item))
print(f"false negatives among inserted items: {false_negatives} (must be 0)")

probes = [f"unseen-{i}" for i in range(20000)]
fp_count = sum(1 for item in probes if bf.might_contain(item))
print(f"empirical FP rate on {len(probes)} unseen probes: {fp_count/len(probes):.4f} (target was {p_target})")

cbf = CountingBloomFilter(n_expected, p_target)
cbf.insert("target-doc")
cbf.insert("unrelated-doc")
before = cbf.might_contain("target-doc")
cbf.remove("target-doc")
after = cbf.might_contain("target-doc")
unrelated_after = cbf.might_contain("unrelated-doc")
print(f"CountingBloomFilter: might_contain BEFORE remove = {before}, AFTER remove = {after}")
print(f"unrelated item still present after unrelated removal: {unrelated_after}")

Running this driver against the classes above prints:

BloomFilter sized: m=9586 bits, k=7 hash functions
false negatives among inserted items: 0 (must be 0)
empirical FP rate on 20000 unseen probes: 0.0109 (target was 0.01)
CountingBloomFilter: might_contain BEFORE remove = True, AFTER remove = False
unrelated item still present after unrelated removal: True

All 1,000 inserted document ids are correctly reported present (zero false negatives, as guaranteed), and probing 20,000 ids that were never inserted produces an empirical false-positive rate of 1.09%, reasonably close to the 1% design target (a single run at this size will naturally land somewhat above or below the target; the theoretical formula is an expectation, not a per-run guarantee). The Counting Bloom Filter demo is the meaningful correctness check for deletion: if remove() were broken (a no-op), might_contain would still read True after the call; instead it flips to False, and a separately inserted, unrelated item remains True after that removal, confirming counters correctly separate the two items' shared positions rather than one clobbering the other.

Trade-offs and pitfalls

A Counting Bloom Filter costs 4 to 8 times the memory of a plain Bloom filter for the same m (each slot is now several bits instead of one) purely to support deletion. It also introduces a new failure mode a plain Bloom filter cannot have: calling remove() on an item that was never actually inserted decrements counters that a genuinely present item may depend on, which can push a shared counter to zero and produce a false negative, something a plain Bloom filter's contract explicitly promises never happens. Counter saturation (hitting counter_max) is the other edge case: once a counter caps out, further increments are silently dropped, so a very hot bit position can under-count relative to true insert volume, meaning a later legitimate sequence of removes may not bring that counter back to exactly zero when it should.

Direct answer

For random-projection LSH (locality-sensitive hashing) on 128-dimensional normalized vectors, a single hyperplane hash function collides two vectors with a probability that is a simple function of the angle between them. Concatenating $k$ hash functions into one band (an AND over the $k$ functions) sharpens the gap between near and far pairs, but also shrinks the collision probability for genuinely near pairs, so you compensate by building $L$ independent bands (an OR across the bands) to push recall back up. $k$ trades false positives for per-band selectivity; $L$ trades recall for the number of hash tables you must build and query.

Structured elaboration

Setup

For unit-length (normalized) vectors, random hyperplane hashing (the sign of a dot product with a random vector $w$) has a closed form: the probability a single hash function agrees on two vectors with angle $\theta$ between them is

Let $p_1 = p(\theta_r)$ be the collision probability for vectors within the "near" radius $r$ (angle $\theta_r$), and $p_2 = p(\theta_{cr})$ the collision probability for vectors at the "far" radius $cr$ (angle $\theta_{cr} > \theta_r$, since $c>1$). Because collision probability falls as angle grows, $p_1 > p_2$.

Banding: choosing k

Concatenate $k$ independent hash functions into one band, requiring ALL $k$ to agree before the band reports a match:

Since $p_1 > p_2$, raising $k$ shrinks $p_2^k$ faster than $p_1^k$ (the ratio $(p_1/p_2)^k$ grows with $k$), so a larger $k$ gives each band better selectivity. The practical target: choose $k$ so $p_2^k$ is small enough that the expected number of false hits per band per query, across the whole dataset of $n$ items, stays close to $O(1)$, roughly $p_2^k \approx 1/n$.

Tables: choosing L

A large $k$ also shrinks $p_1^k$, hurting recall on true near neighbors. Fix this with $L$ independent bands, reporting a candidate if ANY band matches:

Choose $L$ to hit a near-pair recall target of $1-\delta$:

Practical trade-off

Raising $k$ improves per-band selectivity (fewer irrelevant candidates per bucket) but drives $p_1^k$ down too, forcing $L$ up to hold recall; $L$ directly multiplies storage (one full hash table per band) and per-query hashing cost (all $k \times L$ hash values are computed on every query). There is no free choice, only a point on the recall/memory/latency curve.

Worked example

Near threshold: cosine similarity $\geq 0.9$. Far threshold: cosine similarity $\leq 0.5$ (using $\theta = \arccos(\text{similarity})$).

$\theta_r = \arccos(0.9) \approx 25.84^\circ \Rightarrow p_1 = 1 - 25.84/180 \approx 0.856$
$\theta_{cr} = \arccos(0.5) = 60^\circ \Rightarrow p_2 = 1 - 60/180 \approx 0.667$

Pick $k=20$: $p_1^{20} \approx 0.0451$, $p_2^{20} \approx 0.000301$.

For a 95% recall target ($\delta=0.05$), solving for $L$ gives $L \approx 67$ tables. Plugging back in:

• Recall (near pairs reported): $1-(1-0.0451)^{67} \approx 95.4\%$
• False positive rate (far pairs still reported): $1-(1-0.000301)^{67} \approx 2.0\%$

So with $k=20$ and $L=67$, the system recovers about 95% of true near neighbors while only about 2% of unrelated far vectors ever land in a shared bucket, at the cost of maintaining 67 separate hash tables of 20-bit keys each.

Trade-offs and pitfalls

• $k$ too small: bands barely discriminate near from far, regardless of how many tables you build.
• $k$ too large without raising $L$: recall collapses, since even true near neighbors rarely agree on all $k$ hash functions simultaneously.
• $L$ scales storage and per-query cost linearly; in practice $k$ and $L$ are tuned against a labeled validation set of known near/far pairs, since real embeddings rarely have a hard radius/non-radius split.
• This analysis assumes independent, well-distributed random hyperplanes; embeddings clustered on a low-dimensional manifold (common with learned embeddings) can violate the uniformity assumptions the closed-form formula relies on.

Direct answer

At billions of sparse (feature_id, value) pairs, the dominant cost is per-entry overhead, not the raw data itself, so the design is a compact, bit-packed open-addressed hash table (feature IDs and quantized values stored in flat arrays, no per-entry object or pointer), sharded across many memory-mapped files so no single process needs the whole dataset resident in RAM, with a small explicit cache in front for the handful of features that get looked up far more often than the rest.

Structured elaboration

Compact hash tables and bit-packing. Store feature IDs and values in two parallel flat arrays (open addressing, not chaining), rather than a language-level dict/HashMap, which pays for a full object per entry. This is measurable, not just theoretical: tracking sys.getsizeof() of a growing int -> float dict shows the per-entry slot overhead is NOT constant across scale, it starts around 52-54 bytes/entry for small dicts but settles at a higher, stable asymptotic value once the dict is large enough that its internal index array widens:

import sys

d = {}
seen_sizes = set()
for i in range(1, 3_000_000):
    d[i] = float(i)
    cur = sys.getsizeof(d)
    if cur not in seen_sizes:
        seen_sizes.add(cur)
        print(f"n={i:<8} bytes/entry={cur/i:.3f}")

Output (last few growth points, this runtime):

n=87382    bytes/entry=54.512
n=174763   bytes/entry=54.409
...
n=349526   bytes/entry=60.000
n=699051   bytes/entry=60.000
n=1398102  bytes/entry=60.000
n=2796203  bytes/entry=60.000

The ratio stabilizes at exactly 60.0 bytes/entry from roughly 22,000 entries onward and stays there through millions of entries, so 60 bytes/entry, not a smaller transient value measured on a tiny dict, is the right number to extrapolate from at billions-of-entries scale (excluding the separate int/float object allocations Python would also need on top of the table slots). A packed layout storing a 4-byte feature ID and a 2-byte quantized value needs only 6 bytes per entry, live payload only, open addressing, a 10x reduction in slot overhead alone.

Value quantization. Full float32 precision is rarely needed for serving a sparse feature value; quantizing to a 16-bit fixed-point or float16 representation (or 8-bit with a calibrated scale/zero-point per feature or per shard) roughly halves to quarters the per-value cost against float32, in exchange for a small, bounded precision loss that must be validated against the downstream model's actual sensitivity, not assumed safe by default.

Sharding. Partition the feature-ID space across many shards using consistent hashing on feature_id, so no single shard holds the entire corpus and adding shard capacity only reassigns a small fraction of the keyspace rather than a full rehash. More shards means a smaller footprint per shard, at the cost of more shard-management overhead (open file handles, per-shard metadata) and a real risk of splitting related features across shards that would otherwise benefit from being read together.

Memory-mapped files. Back each shard's packed arrays with a memory-mapped file (mmap) instead of a heap-resident structure, so the operating system, not the application, decides which shards' pages are actually resident in physical RAM based on real access recency, transparently overflowing cold shards to disk. This also lets multiple serving processes on the same host share the same underlying pages read-only, avoiding duplicate memory for the same data.

Multi-level caching. In front of the mmap-backed shards, keep a small, explicit in-process cache (a plain LRU, least-recently-used, cache, or one whose admission is guided by a small frequency-tracking sketch) for the minority of features that are looked up disproportionately often, a common power-law pattern in ML feature lookups. This is what actually protects hot-feature latency, since relying on the OS page cache alone gives no guarantee that the hottest features specifically stay resident under memory pressure from everything else.

How to evaluate the design. Replay real production access traces against candidate configurations (shard count, quantization scheme, cache size) and measure three things directly: the top-tier cache hit rate, the page-fault rate on the memory-mapped shards, and end-to-end serving latency at the p99. Separately, compare quantized feature scores against full-precision scores on a held-out validation set to confirm the accuracy loss from quantization stays within whatever tolerance the downstream model can absorb.

Worked example

Assume 5,000,000,000 (feature_id, value) pairs. Packed layout (4-byte ID plus 2-byte quantized value, open addressed): 5,000,000,000 * 6 bytes = 30.0 GB total. A naive Python dict at the measured asymptotic 60.0 bytes/entry overhead extrapolates to 5,000,000,000 * 60 bytes = 300.0 GB for the same 5 billion entries, roughly 10x larger for slot overhead alone, before even counting the separate object allocations a real dict would also need for the keys and values. Sharded across 1,000 shards, each shard holds about 5,000,000 entries and about 30 MB of packed data, small enough to be memory-mapped and warmed cheaply per shard.

Trade-offs and pitfalls

• Quantization precision must be validated against the actual task, not assumed. A scheme that looks fine on average error can still silently degrade the small subset of decisions that were sensitive to the truncated precision; validate on the real downstream metric, not just raw numeric error.
• More shards is not free. Splitting into many small shards reduces per-shard footprint but adds per-shard bookkeeping and can scatter related features that a single request needs together, hurting locality even though total memory usage looks better on paper.
• mmap trades explicit control for OS-managed convenience. Page-cache eviction under memory pressure is not application-controlled, and a cold process restart can produce a burst of page faults (and a latency spike) until the working set is re-warmed; this is exactly why a small, explicit hot-feature cache sits in front rather than relying on the page cache alone.
• A common wrong turn: assuming uniform sharding by feature ID also balances serving load evenly. Feature-access patterns are typically power-law distributed, so a shard can be memory-light but request-heavy if it happens to own a handful of very hot features; the explicit cache tier, not the sharding scheme, is what actually absorbs that skew.

Direct answer

Load factor is the ratio of stored entries to the number of buckets (n / m). A hash table resizes,
allocating a bigger backing array and re-inserting every existing entry, once the load factor crosses
a chosen threshold (commonly 0.75), because letting it climb further makes collisions, and therefore
lookups, get slower.

Structured elaboration

Why load factor matters. For a table using chaining, the average chain length is exactly the
load factor, so a load factor of 0.75 means the average bucket holds 0.75 entries, still effectively
O(1) to scan. Left unchecked (say load factor 20), average chain length would be 20, no longer
meaningfully O(1). For open addressing the effect is sharper: expected probe length grows roughly
like 1 / (1 - load factor), which is fine at 0.5 (about 2 probes) but blows up as load factor
approaches 1 (10 probes at 0.9, effectively unbounded as it approaches 1.0), which is exactly why
open-addressing tables typically resize at a lower threshold than chaining tables do.

What happens during a resize. The table allocates a new backing array, usually double the old
capacity, and re-inserts every live entry by recomputing each one's bucket index against the new
capacity (a key's old bucket index is generally meaningless against a differently-sized table, since
bucket index is hash(key) % new_capacity). This is an O(n) operation, expensive on the one insert
that triggers it, but because it only happens after n has doubled since the last resize, the total
resizing cost summed over n inserts is only O(n), an average (amortized) cost of O(1) extra per
insert (the full amortized-cost proof is worth working through rigorously on its own).

Threshold choice: 0.5 vs 0.75. A lower threshold (0.5) keeps average probe/chain length shorter
at the cost of more frequent resizes and roughly double the wasted (empty) capacity at any given
moment. A higher threshold (0.75, Java HashMap and CPython dict's rough working range) resizes less
often and wastes less memory, at the cost of slightly longer average probes/chains right before a
resize fires. Neither is "correct"; it is a memory-vs-latency trade-off tuned to the expected
workload, latency-sensitive services with memory to spare often pick a lower threshold on purpose.

Worked example

Table starts at capacity 4, threshold 0.75 (resize when entries > 3):

• Insert 1, 2, 3 entries: load factor 0.25, 0.5, 0.75. The 3rd insert leaves load factor exactly at
  the threshold; whether that fires a resize depends on whether the check is > or >= capacity*
  threshold, an implementation detail worth being precise about in an interview.
• Insert the 4th entry: load factor would be 1.0, over threshold, so the table resizes to capacity 8
  first, re-inserting all 4 existing entries (now at load factor 0.5 in the new table), then places
  the 4th entry.

Trade-offs and pitfalls

A frequent mistake is treating the resize threshold as a fixed universal constant rather than a
tunable trade-off, real systems facing bursty, unpredictable growth sometimes pre-size a table to its
expected final count specifically to avoid paying for resizes during a latency-sensitive burst
(worth working out with real numbers for your expected N). A second pitfall is forgetting that
resizing itself is not free even though it is amortized O(1): a single resize on a very large table
is a real, visible latency spike on whichever operation triggers it, which is exactly the motivation
for incremental/progressive resizing strategies, a design worth exploring in depth on its own, in latency-sensitive
production systems.

Direct answer

Build the vocabulary for natural language processing (NLP) model training in two phases: a mutable counting phase (stream every token array through a hash map that tallies frequency), then freeze it into an immutable, id-assigned lookup structure for training and inference. Reserve the first few ids for special tokens, PAD (padding), UNK (unknown / out-of-vocabulary), BOS (beginning-of-sequence), and EOS (end-of-sequence), so every consumer of the vocabulary can hardcode those ids instead of looking them up. At roughly 50 million entries, the STRUCTURE chosen to store the final mapping matters far more for memory and load time than the counting logic itself.

Counting tokens and assigning ids

Stream through the training corpus's token arrays, incrementing a count in a hash map keyed by token string. Once counting finishes, apply a frequency cutoff (drop tokens seen fewer than some minimum number of times) to bound vocabulary size, then assign ids in a fixed order, most commonly by descending frequency, so common tokens get low ids; this also tends to compress better downstream, since low ids repeat more often in a frequency-skewed corpus.

Reserving special tokens

Special tokens need a small, fixed set of ids that never collide with a real corpus token and never depend on which corpus happened to be used for training:

• PAD (padding): fills unused positions in a fixed-length batch so every sequence in a batch has equal length; typically id 0 so padded positions can be masked cheaply.
• UNK (unknown): the fallback id for any token encountered at inference that isn't in the vocabulary.
• BOS (beginning-of-sequence): marks where a sequence starts, useful for generation and for models needing an explicit start signal.
• EOS (end-of-sequence): marks where a sequence ends, so a generative model learns when to stop.

Reserve these before assigning any corpus-derived ids, so their meaning stays stable across vocabulary rebuilds even if the corpus changes.

Handling out-of-vocabulary tokens at inference

A token seen at inference that never appeared (or fell below the training cutoff) has no assigned id. The simplest handling maps it to UNK's id and accepts the information loss. A stronger approach used by most modern pipelines is subword tokenization (byte-pair encoding or WordPiece): tokens are built from smaller sub-units, so a genuinely novel word usually still decomposes into known pieces rather than becoming one opaque UNK, which is why subword vocabularies handle open-ended text far better than whole-word vocabularies.

Memory and storage at roughly 50 million entries: hash maps vs sorted arrays

A hash map keyed by token string needs, per entry: a stored hash, a pointer to the key string (heap-allocated, variable length), the id, and spare capacity (load-factor headroom, typically kept below 0.7) to keep lookups fast. A sorted array of (hash, id) pairs, searched with binary search instead of hashing, is far more compact, since it needs no pointer indirection and no load-factor slack:

$\text{bytes}_{\text{array}} = n \times (\text{hash\_bytes} + \text{id\_bytes})$

For n = 50,000,000 with an 8-byte hash and a 4-byte id, that is 50,000,000 x 12 bytes = 600,000,000 bytes, about 600 MB (572 MiB). A hash map's per-entry cost is roughly:

$\text{bytes}_{\text{hashmap}} \approx \frac{n \times \text{entry\_bytes}}{\text{load factor}}$

With a typical entry cost of 24 to 32 bytes (hash, id, and a pointer to the string) and a load factor of 0.5 to 0.7, that works out to roughly 1.7 to 3.2 GB for the same 50 million entries, several times the sorted array's footprint, purely from pointer indirection and load-factor slack. This is a formula-based engineering estimate, not a measured benchmark of any specific library implementation.

Persistence format for fast load

A sorted array of fixed-width records maps directly onto a flat binary file: loading it is a single memory-map call, and binary search needs no deserialization step at all. A hash map is usually serialized as a list of key-value pairs and has to be walked and reinserted into fresh buckets on load (rehashing), which is both slower and momentarily doubles memory during the rebuild. For a static, read-only, roughly 50-million-entry vocabulary that never changes after training, a memory-mapped sorted array (or a minimal perfect hash function built once offline) is usually the better production choice; a hash map is the right tool for the mutable COUNTING phase, not for the frozen artifact that gets shipped.

Trade-offs and pitfalls

• Shipping a hash map as the FINAL served artifact (rather than only using it during counting) is the most common mistake: it optimizes for a mutability no longer needed and pays for it in memory and cold-start latency.
• Binary search on a sorted array costs O(log n) per lookup ($\log_2(50{,}000{,}000) \approx 26$ comparisons) versus O(1) average for a hash map; for 50 million entries this is still fast in absolute terms, but it's a real trade-off if vocabulary lookup sits on a hot path.
• Forgetting to reserve special-token ids before assigning corpus ids means a vocabulary rebuild (a different corpus, a different frequency cutoff) can silently shift what PAD, UNK, BOS, or EOS mean, a subtle and hard-to-detect training bug.