Hashing and Hash Tables Questions

Direct answer

A Bloom filter trades a small, tunable false-positive rate for O(1)-per-check membership testing in a fixed, sublinear amount of memory (independent of each item's actual size), with the guarantee that it never produces a false negative. That is exactly the right trade for "skip expensive downstream processing if we've probably already seen this event id": the cost of a rare, bounded-rate mistake (redundantly reprocessing a genuinely new event misclassified as a duplicate) is far cheaper than storing every event id in full.

Structured elaboration

Given an expected item count n and a target false-positive rate p, the bit array size m and hash-function count k are:

$m = -\frac{n \ln p}{(\ln 2)^2}$
$k = \frac{m}{n}\ln 2$

These fall out of the false-positive rate formula $p \approx (1 - e^{-kn/m})^k$: fixing n and m, this expression is minimized over k at $k = (m/n)\ln 2$; substituting that back in and solving for m at a target p gives the first formula. In practice, k is rounded to the nearest integer, and instead of computing k fully independent hash functions, two independent hashes h1, h2 are combined via $g_i(x) = h_1(x) + i \cdot h_2(x) \bmod m$ for $i = 0, \ldots, k-1$ (the Kirsch-Mitzenmacher construction), which behaves like k independent hashes for this purpose without needing k separate implementations.

Persistence. The filter is just a bitmap, so it serializes trivially: snapshot it to disk or object storage periodically, or back it directly with a memory-mapped file so a process restart does not lose state. Because bits cannot be read back into the original ids, persistence only protects against losing the "have I seen this" answer, not against losing the actual id list; if you need to recover the ids themselves you need a separate log, the filter is not that log.

Reset strategy. Deduplication is usually windowed ("seen in the last 24 hours"), but a plain Bloom filter cannot delete a single item without risking false negatives for other items sharing a bit, so full resets are the only safe removal. A common pattern is time-sliced filters: roll a fresh filter every window (e.g. hourly), check membership against the last N windows' filters, and drop the oldest window's filter once it ages out. If per-item expiry (rather than whole-window expiry) is required, that calls for a Counting Bloom Filter instead, trading more memory per slot for the ability to decrement on removal.

Versus a full hash set. A hash set has zero false positives, but memory scales with the actual bytes of every distinct item stored (a 16-byte UUID plus per-entry hash-map overhead, often 40 to 80 bytes total per entry in typical language runtimes), while the Bloom filter's footprint is a small, fixed number of bits per expected item regardless of how large or small each item's own representation is.

Worked example

For n = 1,000,000 expected event ids and a target false-positive rate p = 0.01: $m = -\frac{1{,}000{,}000 \times \ln(0.01)}{(\ln 2)^2} \approx 9{,}585{,}059$ bits, about 1.14 MiB, and $k = \frac{9{,}585{,}059}{1{,}000{,}000}\ln 2 \approx 6.64$, rounded to k = 7 hash positions per event. A full hash set storing 1,000,000 sixteen-byte UUIDs at roughly 50 bytes/entry with overhead would need on the order of 50 MB, over 40x the Bloom filter's 1.14 MiB, at the cost of accepting that about 1% of genuinely new event ids will be misclassified as duplicates and skipped.

Trade-offs and pitfalls

The false-positive rate is only p at the moment the filter holds exactly n items; if the real stream keeps inserting past n (no reset ever fires, or the window sizing was wrong), the effective false-positive rate climbs well above the design target as m stays fixed while the true item count grows, since the bit array saturates toward all-ones. A persisted filter must be reloaded with the exact same m, k, and hash implementation it was built with. If any of those change between versions, deserializing old bits under new parameters produces silently wrong membership answers rather than a crash, a correctness bug that is easy to miss in testing and hard to detect in production unless you actively track the empirical false-positive rate (periodically probing with keys known not to be in the set and comparing the observed hit rate to your target p).

Direct answer

On-call, with p95/p99 latency spiking and CPU pegged: first confirm the symptom (is one specific
endpoint or hash-table-backed component actually the hot path, via CPU profiling or request
tracing), apply an immediate, reversible mitigation to restore service (rate-limit or reject the
suspect traffic pattern), THEN do the slower root-cause work (was this a genuine attack, or an
organic pathological-input pattern), and only after that decide on the durable fix.

Structured elaboration

Step 1: Confirm before you act. A CPU spike correlated with a specific endpoint or a specific
data structure's operations (visible via a CPU profiler showing time concentrated in hash/lookup
code, or via request tracing showing a small number of abnormally slow requests) is the signal to
look for BEFORE assuming "hash flooding" specifically, plenty of other things cause CPU spikes and
tail-latency jumps, jumping straight to a hash-table-specific fix on a hunch risks fixing the wrong
thing while the real cause continues.

Step 2: Stop the bleeding, reversibly. Once the suspect requests/inputs are identified (e.g. a
specific client, IP range, or an endpoint accepting attacker-controlled keys), the fastest safe
mitigation is usually rate-limiting or temporarily rejecting that specific traffic shape, NOT a
code deploy, deploys are slower and riskier to do under active incident pressure than a
traffic-shaping change, which can typically be rolled back just as fast if it turns out to be wrong.

Step 3: Root-cause, now that the immediate fire is out. Was this attacker-controlled (keys chosen
specifically to collide) or an organic pathological pattern (e.g. a legitimate but unusually
uniform/adversarial-shaped dataset from a real customer)? Confirming which changes what "fixed"
means, an organic pattern might need a data-modeling fix, while a genuine attack needs the
seeded-hashing defense.

Step 4: The durable fix, deployed carefully. If root-caused to predictable hashing, the actual
code change (seeded/randomized hashing, or capping per-request key counts, or confirming
treeification is active) goes through normal review and staged rollout, not rushed out under
continued incident pressure, since a hasty hashing change risks a NEW correctness bug (e.g. breaking existing persisted hash-based routing that depended on the old, predictable hash values) that's arguably worse than the original latency issue.

Worked example

A concrete timeline: T+0, alerting fires on p99 latency; T+2min, CPU profile shows 80% of sampled
stack traces inside the request-parsing hash-map's put path for exactly one endpoint; T+4min,
traffic logs show the spike correlates with a burst of requests from one client ID with unusually
large, unusually structured JSON bodies; T+6min, that client ID is rate-limited (a config change, no
deploy), latency recovers within a minute as the offending traffic drains; T+30min (post-recovery, no
longer under pressure), the actual request bodies are pulled and analyzed offline to confirm whether
the keys were deliberately collision-engineered; T+1 day, if confirmed adversarial, a seeded-hashing
fix is written, reviewed, and staged normally.

Trade-offs and pitfalls

The single biggest mistake under this kind of pressure is skipping straight from "CPU is high" to
"ship a hashing fix", without first confirming causation and without an immediate, reversible
mitigation in place, that ordering risks a rushed code change deployed mid-incident (higher risk of
introducing a NEW bug) while the actual traffic pattern causing the spike might not even be
adversarial. A postmortem that only lists "we added SipHash" without describing HOW the on-call
engineer got from symptom to that specific root cause is a weaker artifact than one that shows the
triage reasoning explicitly, that reasoning is exactly what's being evaluated in a scenario like this.

Direct answer

MinHash estimates Jaccard similarity between two shingle sets by hashing every shingle with several independent hash functions, keeping the minimum value under each one, and taking the fraction of matching minimums across two documents' signatures as the estimate. The estimator is unbiased with variance $J(1-J)/k$ for $k$ hash functions, so signature size is chosen directly from how much estimation error is tolerable, and in large-scale near-duplicate detection this signature is what feeds a locality-sensitive hashing (LSH) banding step so full pairwise comparison is never required.

Structured elaboration

Shingle and true-similarity functions

Build the shingle set (overlapping length-k substrings) and the true Jaccard similarity directly from set overlap, used here as a sanity baseline to check the estimator against.

Hash family and signature

Use $k$ independent universal hash functions of the form $h(x) = (ax+b) \bmod p$ over a large prime $p$ as the practical stand-in for random permutations, applied to a deterministic integer hash of each shingle so results are reproducible across machines and processes. Python's built-in string hash is randomized per process by design (to resist hash-flooding attacks), so it cannot be relied on for this.

Estimating similarity

Compare two signatures position by position; the fraction of positions where the two documents' minimum hash values agree is the similarity estimate.

Variance vs signature size

The estimator's variance is $\text{Var}[\hat{J}] = J(1-J)/k$ for $k$ hash functions, so quadrupling $k$ halves the standard error. This is why MinHash accuracy is a direct, tunable function of how many hash functions (the signature length) you are willing to compute and store per document.

Use in large-scale near-duplicate detection

At web scale, comparing full signatures pairwise is still quadratic in corpus size, so in practice the signature feeds a locality-sensitive hashing (LSH) banding step: split the signature into bands, hash each band to a bucket, and only documents sharing a bucket in at least one band ever get compared directly. The signature is the input to that indexing step, not the end of the pipeline.

Worked example

Two near-duplicate sentences, 5-character shingles, true Jaccard similarity computed directly from the shingle sets: 0.6087.

import random
import zlib

def shingles(text, shingle_len):
    text = text.lower()
    return {text[i:i+shingle_len] for i in range(len(text) - shingle_len + 1)}

def true_jaccard(a, b):
    return len(a & b) / len(a | b)

def base_hash(s):
    # deterministic string -> int, independent of Python's per-process
    # string hash randomization
    return zlib.crc32(s.encode("utf-8"))

def build_hash_family(num_hashes, seed):
    rng = random.Random(seed)
    p = 2_305_843_009_213_693_951  # a Mersenne prime
    return [(rng.randrange(1, p - 1), rng.randrange(0, p - 1), p) for _ in range(num_hashes)]

def minhash_signature(shingle_set, hash_family):
    base = [base_hash(sh) for sh in shingle_set]
    return [min((a * x + b) % p for x in base) for a, b, p in hash_family]

def estimate_jaccard(sig_a, sig_b):
    return sum(1 for x, y in zip(sig_a, sig_b) if x == y) / len(sig_a)

doc1 = "the quick brown fox jumps over the lazy dog near the riverbank"
doc2 = "the quick brown fox leaps over the lazy dog by the riverbank"
s1, s2 = shingles(doc1, 5), shingles(doc2, 5)
true_j = true_jaccard(s1, s2)
print(f"true Jaccard: {true_j:.4f}")

# empirical variance across independent hash-family draws, checked
# against the analytic prediction J(1-J)/k
for num_hashes in (16, 64):
    ests = []
    for t in range(200):
        family = build_hash_family(num_hashes, seed=1000 + t)
        est = estimate_jaccard(minhash_signature(s1, family), minhash_signature(s2, family))
        ests.append(est)
    mean_est = sum(ests) / len(ests)
    var_est = sum((e - mean_est) ** 2 for e in ests) / len(ests)
    predicted = true_j * (1 - true_j) / num_hashes
    print(f"num_hashes={num_hashes}: empirical var={var_est:.5f}  predicted J(1-J)/k={predicted:.5f}")

Output:

true Jaccard: 0.6087
num_hashes=16: empirical var=0.01489  predicted J(1-J)/k=0.01489
num_hashes=64: empirical var=0.00367  predicted J(1-J)/k=0.00372

The empirical variance across 200 independent hash-family draws matches the $J(1-J)/k$ prediction closely at both signature sizes, and quadrupling the number of hash functions from 16 to 64 cut the variance by roughly 4x, exactly as the formula predicts.

Key points

• Never rely on Python's built-in hash() for the base string-to-int step; it is randomized per process (PYTHONHASHSEED) specifically to resist hash-flooding attacks, which would make signatures non-reproducible across runs and processes.
• Universal hashing $(ax+b) \bmod p$ is the standard practical stand-in for true random permutations, which are too expensive to materialize directly over large shingle sets.

Complexity

Building one signature costs $O(|\text{shingles}| \times m)$ for $m$ hash functions; comparing two signatures is $O(m)$. MinHash replaces an $O(|\text{shingle set}|)$ per-pair comparison with a fixed $O(m)$ one, independent of document length.

Edge cases

• Empty or near-empty shingle sets (very short documents) make Jaccard similarity and MinHash both unstable; guard against documents shorter than the shingle length.
• Duplicate shingles within one document collapse to one set entry (shingle sets, not multisets), correct for near-duplicate detection but wrong if term frequency mattered.

Trade-offs and pitfalls

• A larger signature (more hash functions) reduces variance but costs more memory and comparison time per document pair; the choice is a direct trade against how much estimation error the downstream decision can tolerate.
• Treating a single MinHash comparison as a final duplicate/not-duplicate decision, rather than feeding it through LSH banding first, does not scale past a small corpus, since pairwise comparison is still quadratic.

Direct answer

Java's equals() and hashCode() are a matched pair by CONTRACT, not by compiler enforcement:
if a.equals(b) is true, a.hashCode() and b.hashCode() MUST also be equal, or a
HashMap/HashSet will silently fail to find an object that equals() says is present, because
lookups only compare within the bucket the hash selects. For cache keys that must survive
application restarts, rolling deploys, and serialization, that same contract needs to hold ACROSS
versions too, which means keeping hashCode()/equals() off any field that can vary between a
deploy that wrote a cache entry and a deploy that reads it, and explicitly versioning the key's
own format.

Structured elaboration

Why an inconsistent implementation breaks hash-based caches and maps. A HashMap places an
entry in the bucket its key's hashCode() selects; a lookup computes the hash of the SEARCH key,
goes straight to that bucket, and only then uses equals() to check candidates within it. If two
objects are equals()-equal but have different hashCode() values, they can land in different
buckets, so a lookup for one will never even consider the other as a candidate, even though the
application considers them the same logical key. This produces exactly the symptom a cache
exhibits when this bug is present: unexplained, intermittent cache misses for keys the
application is certain it already cached.

Designing key classes that remain stable across application versions. The danger is any field
that can differ between the version of the code that WROTE a cache entry and the version that
READS it: a field derived from a build identifier, an ordinal position in an enum that a future
release might reorder, a timestamp captured at construction, or any value influenced by
process-local state. None of these belong in hashCode()/equals() for a cache key meant to
outlive a single deploy; strip the key down to the minimal set of business-identity fields that
are guaranteed to mean the same thing across versions.

Surviving serialization. If cache keys are serialized (written to a distributed cache, or
persisted across a restart), hashCode() must be computed from the DESERIALIZED object's fields,
never from a stored, pre-computed hash value, for the same reason raw persisted hash codes are
unsafe in general: a hash's specific numeric value is an implementation detail of hashCode()'s
CURRENT logic, and that logic can legitimately change between versions even if the underlying
fields do not.

Avoiding volatile fields. A volatile field is one whose value the JVM (Java Virtual Machine, the runtime Java code executes on) guarantees is visible
across threads immediately, which matters for correctness under concurrent access, but has
nothing to do with whether a field is a good input to hashCode(); the actual concern for a
cache key is any field that is MUTABLE at all (volatile or not) after the key enters the cache:
mutating a field hashCode() depends on, after the object is already inserted, moves its logical
identity without moving its physical bucket, orphaning the entry from future lookups.
"Avoid volatile fields" in this context specifically means avoiding fields whose value is subject
to change across the key's lifetime in the cache, not a claim about the volatile keyword itself.

Explicit versioning of key formats. Give every cache key an explicit schema version, most
simply as a literal prefix or field in the key itself (for example "v2:user-id:region:currency"
versus an old "v1:user-id:region"). When the key's shape changes (a field added, removed, or
reinterpreted), bump the version. This guarantees new code looking up a v2 key can never
accidentally match a stale v1 entry that has a different shape, since the version prefix itself
makes the two simply unequal, converting what would otherwise be a silent
wrong-schema-deserialization risk into a clean, safe cache miss that repopulates correctly.

Worked example (Java)

import java.util.HashMap;
import java.util.Map;

final class BrokenCacheKey {
    final String userId;
    final String buildId;
    BrokenCacheKey(String userId, String buildId) {
        this.userId = userId;
        this.buildId = buildId;
    }
    @Override
    public boolean equals(Object o) {
        if (!(o instanceof BrokenCacheKey)) return false;
        return userId.equals(((BrokenCacheKey) o).userId);
    }
    @Override
    public int hashCode() {
        return buildId.hashCode();   // BUG: inconsistent with equals()
    }
}

public class BrokenCacheKeyDemo {
    public static void main(String[] args) {
        BrokenCacheKey k1 = new BrokenCacheKey("u-42", "build-101");
        BrokenCacheKey k2 = new BrokenCacheKey("u-42", "build-102");

        System.out.println(k1.equals(k2));  // true: same business identity

        Map<BrokenCacheKey, String> cache = new HashMap<>();
        cache.put(k1, "cached-response-A");
        String result = cache.getOrDefault(k2, "CACHE MISS");
        System.out.println(result);         // different hash -> MISS despite equals() being true
    }
}

Running this prints true then CACHE MISS: k1.equals(k2) is true (same userId, the
intended identity), but the cache lookup with k2 misses, because k1 and k2 have different
hashCode() values (derived from the differing buildId, standing in for two different
deployments) and therefore land in different buckets. Fixing hashCode() to depend on userId
only (matching equals()) makes the identical lookup return "cached-response-A" correctly.

For key-format versioning, a separate small demo makes the claim concrete instead of just
asserting it:

import java.util.HashMap;
import java.util.Map;

public class VersionedKeyDemo {
    public static void main(String[] args) {
        Map<String, String> cache = new HashMap<>();

        String v1Key = "v1:u-1:US";
        cache.put(v1Key, "old-shape-cached-value");

        String v2Key = "v2:u-1:US:USD";  // shape changed: currency field added, version bumped
        String result = cache.getOrDefault(v2Key, "CACHE MISS (safe invalidation)");
        System.out.println(result);
    }
}

Running this prints CACHE MISS (safe invalidation): the version prefix makes v1Key and
v2Key simply unequal strings, so writing under the old shape and reading under the new shape is
a clean cache miss (which safely repopulates) rather than a silent misread of an old-shape value
as if it had the new shape.

Trade-offs and pitfalls

• This bug is silent and intermittent, not a crash, which is exactly why it is dangerous in
  production: it surfaces as an unexplained cache-hit-rate drop after a rolling deploy, not as an
  obvious error.
• Do not conflate "immutable" with "safe for a cache key across versions." A field can be
  perfectly immutable within one process's lifetime and still be unsafe across versions, if its
  MEANING or presence changes between releases (an enum ordinal is the classic trap: it is
  immutable per-instance but not stable across a code change that reorders the enum's
  declaration).
• Version-prefixing trades a clean invalidation for some wasted cache space immediately after
  a version bump (every old-version entry is now permanently unreachable dead weight until it
  naturally expires or is evicted); this is normally a good trade for correctness, but worth
  accounting for in cache-sizing.
• The contract direction only goes one way. equals() == true must imply hashCode()
  equal; the reverse is not required (hashCode() equal does not imply equals() true, that
  is simply an ordinary hash collision, handled normally by the bucket's internal comparison).

Direct answer

The real root cause is almost never the map's raw memory footprint, it is allocation churn: Integer is immutable, so map.put(key, map.get(key) + 1) allocates a brand-new Integer object on every single increment. At 100,000 queries per second (QPS) that is 100,000 short-lived objects entering the young generation every second, which is exactly what drives frequent young-generation garbage collection (GC, the JVM's automatic process for reclaiming heap memory that is no longer referenced) pauses. Boxing (wrapping a raw primitive like long in a heap object like Long) also multiplies per-entry memory versus a primitive table, and if the map is made thread-safe via a single lock or synchronizedMap, every request serializes on that one lock regardless of which user it touches. The fix is threefold: stop boxing on the hot increment path, shard the keyspace to spread lock contention, and only go off-heap if key cardinality itself threatens the heap budget.

Structured elaboration

1. Eliminate boxing on the hot path with a primitive collection. Libraries such as Eclipse Collections (LongIntHashMap) or fastutil (Long2IntOpenHashMap) store raw long keys and int values in flat arrays with open addressing, never allocating a Long, Integer, or HashMap.Node wrapper per entry. This removes both the per-increment allocation (the actual GC driver) and the static per-entry overhead.

2. Reduce contention with sharding. Partition the user-id keyspace across N independent shards (shard = hash(userId) % N), each holding its own primitive map and its own lock (or a lock-free structure). Unrelated users updating different shards no longer fight over the same lock, the same effect ConcurrentHashMap gets internally from segment/bin-level locking, but tuned explicitly to the counter workload. Pick N as a small multiple of core count; too few shards under-spreads contention, too many wastes memory on mostly-empty tables.

3. Use LongAdder for the counter itself, not a boxed value. java.util.concurrent.atomic.LongAdder is a JDK class built for exactly this write-heavy pattern: instead of every thread compare-and-swapping one shared counter, it stripes the count across several internal cells (each padded to its own cache line) so concurrent writers usually hit different cells, then sums them on read. It is the right tool when writes vastly outnumber reads, which per-request counters are; it is the wrong tool if the counter is read as often as it is written, because sum() has to walk every cell.

4. Reserve off-heap stores for cardinality, not contention. If the number of distinct users is large enough that even a primitive in-heap table would inflate the heap past its budget (tens to hundreds of millions of distinct keys), move the table off the JVM heap entirely (a memory-mapped structure, or a library such as Chronicle Map) so GC never has to scan it. This trades away JIT-friendly access speed and adds serialization/lifecycle complexity, so it should be the last lever pulled, after boxing and contention are already fixed, not the first.

Worked example

Assume 1,000,000 distinct active users being counted. On a 64-bit JVM with compressed object pointers (the default for heaps under 32 GB), typical object sizes are: a boxed Long is about 24 bytes (12-byte header plus an 8-byte value, padded to 8-byte alignment), a boxed Integer is about 16 bytes, and each HashMap.Node wrapping them is about 32 bytes (header plus hash, key reference, value reference, next reference). That is roughly 24 + 16 + 32 = 72 bytes per live entry, before the bucket array itself, and critically, a fresh 16-byte Integer is discarded and reallocated on every increment.

A flat primitive long-to-int open-addressed table stores 8 + 4 = 12 bytes of live key+value data per slot. At a load factor of 0.5 (kept low so probe chains stay short), that costs about 12 / 0.5 = 24 bytes per live entry, and updates happen in place with zero allocation. For 1,000,000 entries: about 72 MB versus about 24 MB, a 3x static memory reduction, and the incrementing hot path goes from 100,000 allocations/sec to zero.

Trade-offs and pitfalls

Common wrong turn: reaching for ConcurrentHashMap<Long, AtomicInteger> and calling it done. It removes the single-lock bottleneck and stops per-increment allocation (the AtomicInteger is created once, not once per increment), but the Long key is still boxed, and it does nothing about hot-key contention on one AtomicInteger if a single user dominates traffic; that case still needs LongAdder or explicit striping regardless of how the map itself is built. Also watch key skew: sharding by user id only helps if load is roughly uniform across users. A single very hot user still serializes on its own counter no matter how many shards exist.