Hashing and Hash Tables Questions

Direct answer

At 10 billion documents, no exact structure can cheaply answer "have I seen this before": a Bloom filter (a fixed-size bit array plus k hash functions, that can only ever say "definitely new" or "possibly seen before", never "definitely seen before") is the right first-line gate, because it collapses each average-2 KB document down to a handful of bit checks regardless of document size. Every positive from the filter (true duplicate or false positive) then gets verified against a persisted exact index keyed by a cryptographic content hash, which is what actually decides duplication. Sharding that whole pipeline by consistent hashing (so each node owns a disjoint, resizable slice of the 10-billion-document keyspace) is what lets the design hit 50,000 docs/sec and stay incrementally updatable without a global rebuild.

Structured elaboration

Hashing strategy. Two roles for hashing, deliberately kept separate. First, the Bloom filter itself needs k hash functions per document to set/check k bits; rather than implementing k independent hash functions, use the standard Kirsch-Mitzenmacher trick of deriving all k from just two: g_i(x) = h1(x) + i * h2(x) mod m. Second, and separately, every document is reduced to a cryptographic content hash (SHA-256 of its normalized content) that becomes its actual dedup key in the persistent exact-index; a 256-bit cryptographic hash makes a genuine collision between two different documents astronomically unlikely, so content-hash equality can be trusted as ground truth for "these are the same document" without a full byte-for-byte comparison.

Sharding by consistent hashing (distributed ownership). Partition the 10-billion-document keyspace across shard nodes using consistent hashing on the content hash, not a plain hash mod N. The difference matters operationally: adding or removing a shard node under consistent hashing only reassigns roughly 1/N of the keyspace, versus a full reshuffle under plain modulo hashing, which is what lets the ingest fleet scale elastically at 50,000 docs/sec without a stop-the-world repartition. Each shard then only has to size its own Bloom filter for its own fraction of the 10 billion documents, not the whole corpus.

Storage choices, layered for the latency target. Each shard holds three tiers: (1) a small in-memory LRU (least-recently-used) cache of the most recently ingested hashes, so a burst of near-simultaneous duplicates never even reaches the filter; (2) the shard's Bloom filter, the main membership gate; (3) a persistent exact-index (a key-value store keyed by content hash, backed by a log-structured merge tree, a write-optimized on-disk structure that batches writes and merges them in the background rather than updating in place) that is the actual source of truth, used both for verification and for full-filter rebuilds. In a memory-constrained deployment, a Count-Min Sketch (CMS, a small fixed-size frequency-estimating structure) can drive the admission and eviction policy for tier (1), promoting keys that are being seen repeatedly and evicting ones that are not, the same admission-policy idea used by modern cache designs, so the bounded RAM budget is spent on the keys most likely to be checked again soon rather than on whichever key happened to arrive most recently.

Collision handling and verification. A Bloom filter's "possibly seen" answer is never proof; every positive must be verified against the persistent exact-index before being counted as a real duplicate, and only a verified hit is treated as a duplicate for the 5% duplicate-fraction accounting the question states. This is also why sizing the filter's false-positive rate matters operationally: every false positive costs one wasted verification read against the persistent store, on top of the verification reads every true duplicate legitimately needs.

Memory estimates, worked at the stated scale. Sizing a single Bloom filter for all n = 10,000,000,000 documents at a target false-positive rate p = 1e-6 uses the standard formulas:

m = -n * ln(p) / (ln 2)^2
k = (m / n) * ln 2

That gives m about 287,551,751,321 bits (about 35.94 GB) and k = 20 (rounding the computed 19.93 to the nearest integer), which achieves a false-positive rate of essentially 1e-6 when checked directly. At 5% true duplicates, that is 500,000,000 genuine duplicate verifications expected, against roughly 10,000 expected false-positive verifications at this achieved rate, wasted verification traffic is about 0.002% of the genuine verification volume, well controlled. Sharded across nodes, each shard's bit array shrinks proportionally: 4.49 GB at 8 shards, 2.25 GB at 16 shards, 1.12 GB at 32 shards, and at 16 shards each node only needs to sustain about 3,125 docs/sec of the 50,000 docs/sec target, comfortably within the sub-second per-document budget since a Bloom filter check is k = 20 cheap hash-and-bit-test operations.

The 4 GB-RAM-constrained variant. If a single node's RAM budget is capped at 4 GB, running the full 10-billion-item filter on one node is not an option (35.94 GB needed) and naively truncating it to 4 GB on one node collapses accuracy: at n = 10,000,000,000 and m capped to a 4 GB bit array (32,000,000,000 bits), the achieved false-positive rate blows up to about 21.6%, useless against a 1e-6 target. The fix is exactly the sharding-by-consistent-hashing design above, not a bigger machine: splitting the corpus across 9 shards, each holding its own 4 GB filter sized for its own roughly 1.11 billion documents, achieves a per-shard false-positive rate of about 9.8e-7, back in line with the global 1e-6 target, because each shard's filter only has to be accurate for its own slice of the keyspace, not the whole corpus.

flowchart LR
    A[Incoming doc, ~2KB avg] --> H[SHA-256 content hash]
    H --> CH[Consistent-hashing router]
    CH --> SH1[Shard 1: LRU + Bloom filter + exact index]
    CH --> SH2[Shard 2: LRU + Bloom filter + exact index]
    CH --> SH3[Shard N: LRU + Bloom filter + exact index]
    SH1 --> V{Bloom says possibly seen?}
    V -->|no| ACC[Accept as new, add to filter and index]
    V -->|yes| VER[Verify against exact index]
    VER -->|confirmed dup| REJ[Reject as duplicate]
    VER -->|false positive| ACC

Worked example

The memory table above is the concrete instantiation at the stated scale: full-corpus filter 35.94 GB at k=20 for a 1e-6 target; sharded to 8/16/32 nodes at 4.49/2.25/1.12 GB each; the 4 GB-constrained case needing 9 shards (not fewer) to hold the global false-positive rate near target, versus 21.6% if forced onto one 4 GB node.

Trade-offs and pitfalls

• Incremental updates are naturally supported for additions, not deletions. A plain Bloom filter has no way to unset a bit safely (another key may share it), so if the corpus ever needs to support removing a document from the dedup set, that requires a counting Bloom filter (small counters instead of single bits) or a scheduled rebuild from the persistent exact-index, not an in-place fix to the bit array.
• Fallback when the persistent exact-index is temporarily unavailable is a genuine business decision, not just an engineering one. Fail-closed (treat any unverifiable Bloom-filter positive as a duplicate and defer or reject the write) protects against ingesting duplicates but risks losing legitimately new documents during an outage; fail-open (accept anyway, reconcile later in a batch pass) protects ingest availability but risks temporarily double-counting. Pick based on which failure mode costs the business more.
• A common wrong turn: sizing one enormous shared Bloom filter for the whole corpus and putting it behind a single service, which recreates a single point of contention and a single point of failure at 50,000 docs/sec; the entire reason to shard by consistent hashing is so no single filter, and no single node, has to absorb the full throughput or the full memory requirement alone.
• Verification cost scales with the true duplicate rate, not just the false-positive rate. At 5% duplicates, verification reads happen for roughly 1 in 20 documents regardless of how tightly the filter's false-positive rate is tuned; tuning p tighter mainly buys back the small extra sliver of wasted verification traffic, not the bulk of it.

Direct answer

For a static set of millions of strings needing O(1) lookup with minimal memory, build a minimal perfect hash function (MPHF) offline: bucket the strings with a first-level hash, then solve a small displacement or assignment problem within each bucket (the CHD or BDZ approach), so the final structure is a lookup table of a few bits per key plus one array indexed directly by the MPHF's output, no probing, no wasted slots, and O(1) worst-case lookup.

Structured elaboration

Why brute force does not scale

The simplest possible idea, try random hash functions until one happens to map all $n$ keys to $n$ distinct slots with no collisions, works for a small example set but the expected number of attempts grows roughly exponentially in $n$, so it becomes computationally hopeless well before $n$ reaches even a few hundred keys, let alone millions (see the worked example below for a direct data point on how fast this grows).

The real approach: two-level construction (CHD/BDZ family)

1. A first-level hash function splits the $n$ keys into $n/\lambda$ buckets of a small constant average size $\lambda$ (typically single digits).
2. Each bucket independently searches for a small displacement value that, combined with a second hash function, places its handful of keys into distinct slots in the final table, avoiding collisions with keys from OTHER buckets that already claimed those slots. Because each bucket's search space is tiny, this step is cheap and independent across buckets, unlike a single global collision search.
3. The result is a lookup table of one small displacement value per bucket. Looking up a key means: compute the first-level hash to find its bucket, read that bucket's displacement value, compute the final slot from key plus displacement, all O(1) memory accesses.

This is what makes construction linear in $n$ overall even though it is doing a search: the search is distributed over many small, independent, cheap subproblems instead of one large collision search over the whole key set.

Trade-offs

• Construction is a genuine offline batch cost, proportional to $n$, with a real constant factor from the per-bucket search; this is unattractive for a key set that changes often.
• Memory per key lands close to the information-theoretic minimum ($\log_2 e \approx 1.44$ bits/key); real implementations typically land somewhat higher, still far below a general hash table.
• No slack capacity anywhere in the final table (that is what "minimal" means), so there is no room to add a key without a full rebuild.

Worked example: a small Python builder sketch

For a SMALL example set, brute-force seed search (try seeds until one gives a collision-free assignment) is simple to read and demonstrates the concept, even though it does not scale the way CHD/BDZ do:

import zlib

def base_hash(seed, key):
    return zlib.crc32(f"{seed}:{key}".encode("utf-8"))

def build_mphf(keys):
    n = len(keys)
    seed = 0
    while True:
        slots = [base_hash(seed, k) % n for k in keys]
        if len(set(slots)) == n:
            return seed, dict(zip(keys, slots))
        seed += 1

vocab = ["cat", "dog", "fox", "wolf", "bear", "lion", "tiger",
         "hawk", "owl", "crow", "seal", "orca"]

seed, mapping = build_mphf(vocab)
print(f"found perfect hash at seed={seed} for n={len(vocab)} keys")
slots_used = sorted(mapping.values())
print("slots used:", slots_used)
assert slots_used == list(range(len(vocab)))
print("verified: bijection onto 0..n-1, zero collisions, minimal table size")

Output:

found perfect hash at seed=8617 for n=12 keys
slots used: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
verified: bijection onto 0..n-1, zero collisions, minimal table size

It took 8,617 attempts to find a collision-free seed for just 12 keys, concrete evidence that brute force does not scale: attempts grow so fast with $n$ that a real system needs the bucketed CHD/BDZ construction instead of a bigger version of this loop.

Key points

• The toy builder above is a genuine minimal perfect hash (verified zero collisions, minimal table size) but algorithmically the wrong tool past a few dozen keys, exactly why production MPHF libraries implement the bucketed displacement search instead.
• zlib.crc32 here is just a fast, deterministic, seedable string hash for the demo, not a cryptographic requirement.

Complexity

Toy brute-force builder: expected attempts grow roughly exponentially in $n$, unusable past small $n$ (12 keys already needed 8,617 attempts, measured above). Real CHD/BDZ construction: $O(n)$ time and space. Both give $O(1)$ lookup once built.

Edge cases

• Duplicate keys in the input set make a perfect hash impossible by definition to reason about cleanly (two occurrences of the same key must map to the same slot); de-duplicate the set first.
• An empty key set is a degenerate case worth guarding against explicitly, no slots, nothing to build.

Trade-offs and pitfalls

• Reaching for brute-force seed search on anything beyond a small demo set is the single most common misunderstanding of "just try hash functions until one works"; the growth rate makes it infeasible almost immediately.
• Treating an MPHF as a general-purpose hash table (expecting it to gracefully accept new keys) is a design error, not an implementation bug to fix later.

Direct answer

Both Java's HashMap and Python's dict grow by allocating a bigger backing array and reinserting every existing entry once a fill-ratio threshold is crossed, so both pay an O(n) cost exactly at the operation that triggers the resize, a real latency spike, not just an average-case cost. They differ sharply on one point that matters for iteration: Java's HashMap gives no ordering guarantee at all (it can and does change across resizes), while Python's dict has guaranteed insertion order as part of the language specification since Python 3.7. For a model server holding a large, live feature-lookup dictionary, the practical fix for both is the same idea in different clothing: avoid growing the structure under live request traffic in the first place.

Structured elaboration

Resizing and rehashing, compared.

Measured resize behavior. Because Python's exact resize thresholds are a CPython implementation detail, not a language guarantee, they are worth measuring directly rather than assumed. Tracking sys.getsizeof() of a growing dict on the current runtime shows the backing storage growing at specific insertion counts:

import sys

d = {}
prev = sys.getsizeof(d)
print(f"n=0   sys.getsizeof(dict) = {prev} bytes")
for i in range(1, 30):
    d[i] = i
    cur = sys.getsizeof(d)
    if cur != prev:
        print(f"n={i:<4} sys.getsizeof(dict) = {cur} bytes  (grew from {prev})")
        prev = cur

Output (CPython 3.14):

n=0   sys.getsizeof(dict) = 64 bytes
n=1   sys.getsizeof(dict) = 224 bytes  (grew from 64)
n=6   sys.getsizeof(dict) = 352 bytes  (grew from 224)
n=11  sys.getsizeof(dict) = 632 bytes  (grew from 352)
n=22  sys.getsizeof(dict) = 1168 bytes  (grew from 632)

The pattern (growth roughly every time the dict is a bit over half full, by a shrinking multiplicative factor as the dict gets larger) matches the general shape both languages share: infrequent, geometrically-spaced resizes rather than a resize on every single insert, which is what keeps the amortized cost per insertion O(1) even though any individual insertion can occasionally cost O(n).

Iteration order guarantees. Java's HashMap iteration order depends on hash values, bucket count, and insertion/collision history, is not part of its contract, and can visibly change after a resize reshuffles entries into new buckets; code that depends on a particular HashMap iteration order is relying on an accident, not a guarantee (LinkedHashMap exists specifically for callers who need predictable order). Python's dict, by contrast, has guaranteed insertion order as a documented language feature since Python 3.7 (an implementation detail of CPython 3.6 that was formalized into the language specification the following version). Confirmed directly:

d2 = {}
d2["z"] = 1
d2["a"] = 2
d2["m"] = 3
print(list(d2.keys()))
print("matches insertion order:", list(d2.keys()) == ["z", "a", "m"])

Output:

['z', 'a', 'm']
matches insertion order: True

How rehash spikes affect latency, and the practical impact for ML feature serving. A model server that keeps a large in-memory dictionary for feature lookups (an embedding table, a feature-store cache, a user-to-features index) and grows it incrementally while serving live requests will see an occasional request pay the full O(n) rehash cost, showing up as a tail-latency spike (a bad P99 or P999) rather than a change in average latency, exactly the kind of intermittent, hard-to-reproduce latency issue that is painful to debug in production. The practical fix differs slightly by language because of the API difference above: in Java, construct the HashMap with an initial capacity computed from the expected entry count divided by the load factor (rounded up), so no resize happens at all during the life of the map; in Python, because there is no equivalent public capacity hint, the standard pattern is to build the full dictionary once, in one shot, before serving traffic starts (at model-load time, from a fully materialized source), rather than growing it entry by entry under live request load, so any resizing that does happen is confined to warmup and never shows up as a request-serving latency spike.

Worked example

The measured Python dict growth trace above is the worked example: sizes jump at n=1, 6, 11, and 22 insertions on this runtime, not on every insertion, which is exactly the geometric-resize pattern responsible for keeping the amortized insert cost O(1) while still producing an occasional expensive insert. The insertion-order check (['z', 'a', 'm']) is the concrete confirmation of Python's ordering guarantee, something no equivalent check could confirm for Java's HashMap, since its contract explicitly makes no such promise.

Trade-offs and pitfalls

• Do not rely on Java HashMap iteration order for anything user-visible or test-asserted; if order matters, use LinkedHashMap (preserves insertion or access order) or TreeMap (sorted order), both of which make the ordering an explicit contract rather than an accident of the current bucket layout.
• Do not assume Python's exact resize thresholds are portable across Python implementations or even across CPython versions. The insertion-order guarantee is part of the language specification; the specific growth-trigger points measured above are a CPython implementation detail and can shift between versions.
• Pre-sizing removes the spike, it does not remove the total rehash cost. The total work to build a map of n entries is the same either way; pre-sizing just moves all of it to construction time instead of spreading unpredictable spikes across live traffic, which is the actual point for a latency-sensitive serving path.
• A common wrong turn: treating a large, frequently-mutated feature dictionary as a single shared structure updated in place during serving, then being surprised by an intermittent tail-latency spike that no code change seems to fix, when the real fix is architectural: stop growing it live, rebuild it wholesale on a schedule or on model reload instead.

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

Geohash and Morton (Z-order) codes both convert a 2D coordinate (latitude, longitude) into a
single bit string by interleaving bits from each dimension, so that points which are close in
2D space tend to share a long common bit prefix. That shared prefix becomes a natural hash-table
bucket key: put points with the same prefix (down to some fixed length) in the same bucket, and
nearby-point queries reduce to comparing prefixes instead of scanning every point.

Structured elaboration

Geohash construction. Geohash builds its bit string by adaptive bisection: maintain a
shrinking latitude range and longitude range, and at each step, check whether the point falls in
the upper or lower half of whichever range is being refined that step (alternating longitude,
latitude, longitude, ...), appending a 1 or 0 bit and narrowing that range to the matching half.
Because both endpoints keep bisecting the SAME global range, two nearby points usually take the
same sequence of "upper/lower" decisions for their first several bits, which is exactly what
produces the shared prefix.

Morton (Z-order) code construction. Morton coding is simpler: quantize each dimension to a
fixed-resolution integer grid up front (decided once, not adaptively), then interleave the BITS
of the two integers (bit 0 of latitude, bit 0 of longitude, bit 1 of latitude, bit 1 of
longitude, ...) into one combined integer. The resulting integer has the same locality property
as geohash (nearby points produce numerically close codes), but the grid resolution is fixed by
how many bits per dimension you choose upfront, rather than adapting per query.

Locality preservation, and its limit. Both techniques preserve locality on average: points
close together usually share a long prefix (geohash) or a small integer distance (Morton). But
neither guarantees it for every pair, because the underlying subdivision is a grid, and any grid
has boundaries. Two points a few meters apart that happen to straddle a boundary the very FIRST
bisection depends on (for example, straddling the equator, or the prime meridian) get assigned
to completely different halves at that step, and every subsequent bit inherits that early
divergence, producing a short shared prefix despite genuine physical proximity.

Collision behavior. Two genuinely different coordinates can produce the identical geohash
or Morton code if you truncate to a low enough precision (fewer bits), since many nearby points
round into the same grid cell at low resolution. This is expected, not a bug: bucket size is
exactly 1 / 2^bits_used of each dimension's range, so precision (bucket size) is a direct,
adjustable trade-off against how many distinct points get lumped into one bucket.

Range and neighbor queries. A bucket lookup by full prefix answers "what else is in exactly
this cell" in O(1) average (hash the prefix string / integer code). A NEIGHBOR query (what is
near this point, including across a cell boundary) cannot rely on prefix match alone, because of
the boundary-discontinuity problem above: production implementations compute the current cell
plus its (up to) 8 adjacent cells and query all of them, not just an exact-prefix match. A RANGE
query over a rectangular area decomposes the area into the minimal set of grid cells covering it
and queries each.

Worked example

def geohash_bits(lat, lon, num_bits=30):
    lat_lo, lat_hi, lon_lo, lon_hi = -90.0, 90.0, -180.0, 180.0
    bits, even = [], True
    for _ in range(num_bits):
        if even:
            mid = (lon_lo + lon_hi) / 2
            bits.append(1 if lon >= mid else 0)
            lon_lo, lon_hi = (mid, lon_hi) if lon >= mid else (lon_lo, mid)
        else:
            mid = (lat_lo + lat_hi) / 2
            bits.append(1 if lat >= mid else 0)
            lat_lo, lat_hi = (mid, lat_hi) if lat >= mid else (lat_lo, mid)
        even = not even
    return "".join(map(str, bits))

def morton_code(lat, lon, bits_per_dim=15):
    lat_q = int((lat + 90.0) / 180.0 * (2 ** bits_per_dim - 1))
    lon_q = int((lon + 180.0) / 360.0 * (2 ** bits_per_dim - 1))
    code = 0
    for i in range(bits_per_dim):
        code |= ((lat_q >> i) & 1) << (2 * i)
        code |= ((lon_q >> i) & 1) << (2 * i + 1)
    return code

def common_prefix_len(a, b):
    n = 0
    for ca, cb in zip(a, b):
        if ca != cb:
            break
        n += 1
    return n

san_francisco = (37.7749, -122.4194)
oakland = (37.8044, -122.2712)      # ~13 km from San Francisco
new_york = (40.7128, -74.0060)      # ~4,100 km from San Francisco

sf_bits, oak_bits, ny_bits = geohash_bits(*san_francisco), geohash_bits(*oakland), geohash_bits(*new_york)
print("SF vs Oakland prefix:", common_prefix_len(sf_bits, oak_bits))
print("SF vs NYC prefix:", common_prefix_len(sf_bits, ny_bits))

sf_m, oak_m, ny_m = morton_code(*san_francisco), morton_code(*oakland), morton_code(*new_york)
print("SF vs Oakland Morton distance:", abs(sf_m - oak_m))
print("SF vs NYC Morton distance:", abs(sf_m - ny_m))

just_south = geohash_bits(-0.0001, 10.0)
just_north = geohash_bits(0.0001, 10.0)
print("Equator-straddling prefix (22m apart):", common_prefix_len(just_south, just_north))

Running this: encoding San Francisco (37.7749, -122.4194), Oakland (37.8044, -122.2712, about
13 km away), and New York City (40.7128, -74.0060, about 4,100 km away) at 30 bits prints a
14-bit common prefix for San Francisco vs Oakland versus only a 2-bit common prefix for San
Francisco vs New York, confirming the nearby pair's bucket keys agree far longer than the distant
pair's. Computing Morton codes for the same three points prints a distance of 22,617 between San
Francisco and Oakland versus 101,605,854 between San Francisco and New York, the same locality
property expressed as integer distance instead of bit prefix. The boundary pitfall prints
directly too: two points about 22 meters apart straddling the equator (latitude -0.0001 vs
+0.0001, same longitude) share only a 1-bit common prefix out of 30, far shorter than the San
Francisco/Oakland pair despite being over 500x closer in real distance, exactly because the very
first bisection (the equator itself) splits them.

Trade-offs and pitfalls

• Precision (number of bits/characters) is the core tuning knob: more bits means smaller,
  more numerous buckets (finer locality, more buckets to check for a wide-area query); fewer
  bits means larger buckets (cheaper storage, coarser locality, more false neighbors within a
  bucket).
• Never search only the exact-prefix bucket for a "nearby" query. The boundary-discontinuity
  example above is the standing reason neighbor search must also probe adjacent cells.
• Morton code's fixed-resolution quantization means choosing bits_per_dimension upfront is
  a hard commitment; geohash's adaptive bisection achieves a similar effect but is more commonly
  paired with a variable-length prefix (shorter prefix = coarser bucket) for the same data.
• This is a genuinely different problem from consistent hashing for load distribution:
  geohash/Morton codes preserve SPATIAL locality (nearby inputs map to nearby outputs), while a
  good general-purpose hash function is explicitly designed to destroy locality (nearby inputs
  should map to unrelated outputs); do not reach for SHA-256 or MurmurHash here, they would
  eliminate the very property this problem needs.