Hashing and Hash Tables Questions

Direct answer

Consistent hashing places both nodes and keys onto one ring (a large hash space, e.g. 0 to 2^160-1), and a key belongs to the first node found walking clockwise from the key's own hash position. At real N-node, R-replica scale, the design decisions that make this work are how many virtual positions each physical node is given, how you walk the ring to pick R distinct replicas, and how you bound how much data moves when membership changes.

Structured elaboration

Virtual nodes. Each physical node is hashed into V virtual positions (commonly 100 to a few hundred) instead of one, spreading its ownership across many small, non-contiguous ring arcs rather than a single large one. This does two things at once: it balances load across equal-capacity nodes (many small arcs average out hash-luck variance far better than one big arc would), and it bounds churn on membership change, since only the arcs immediately clockwise of a changed node's OWN virtual positions are affected, not the whole ring.

Ring traversal. get_node(key) hashes the key onto the ring, then finds the first virtual-node position at or after that hash going clockwise (a binary search over sorted virtual positions, O(log(N*V))); the physical node owning that virtual position holds the key.

Replica placement for factor R. Walk clockwise from the key's position, collecting the first R DISTINCT physical nodes encountered, skipping any virtual node that belongs to a physical node already counted. This spreads a key's R replicas across R different machines automatically, with no separate replica-assignment step, but it means the walk must track physical nodes seen, not virtual positions seen, or it can return the same physical node twice.

Minimal-movement rebalancing. Adding a node inserts its V virtual positions onto the ring; only keys that previously belonged to the virtual node immediately following each of those V new positions move to the new node, everyone else keeps their assignment. Going from N to N+1 nodes, the expected fraction of keys that move is about 1/(N+1), a small fraction rather than a full reshuffle, which is the entire advantage over plain modulo hashing (hash(key) % N), where changing N remaps nearly every key.

Hot keys. However evenly the rest of the keyspace is spread, one very popular key still funnels all its traffic to whichever few physical nodes hold its R replicas. Standard mitigations: detect the hot key and replicate it beyond the standard R, spreading reads round-robin across the extra copies, or split it logically (shard a single hot counter into several sub-counters merged on read) so no single physical node absorbs all of its traffic.

Worked example

import hashlib, bisect
from collections import Counter

def h(key):
    return int(hashlib.sha256(key.encode()).hexdigest(), 16)

class ConsistentHashRing:
    def __init__(self, nodes, vnodes_per_node=100):
        self.vnodes_per_node = vnodes_per_node
        self.ring, self.sorted_positions = {}, []
        for node in nodes:
            self.add_node(node)

    def add_node(self, node):
        for v in range(self.vnodes_per_node):
            pos = h(f"{node}#vnode{v}")
            self.ring[pos] = node
            bisect.insort(self.sorted_positions, pos)

    def get_node(self, key):
        pos = h(key)
        idx = bisect.bisect(self.sorted_positions, pos)
        if idx == len(self.sorted_positions):
            idx = 0
        return self.ring[self.sorted_positions[idx]]

    def get_replicas(self, key, r):
        pos = h(key)
        n = len(self.sorted_positions)
        idx = bisect.bisect(self.sorted_positions, pos) % n
        replicas, seen = [], set()
        total_physical = len(set(self.ring.values()))
        i, steps = idx, 0
        while len(replicas) < r and len(seen) < total_physical and steps < n:
            physical = self.ring[self.sorted_positions[i % n]]
            if physical not in seen:
                seen.add(physical)
                replicas.append(physical)
            i += 1
            steps += 1
        return replicas

# ---- driver ----
nodes = [f"node-{i}" for i in range(5)]
ring = ConsistentHashRing(nodes, vnodes_per_node=100)
keys = [f"key-{i}" for i in range(50000)]

before = {k: ring.get_node(k) for k in keys}
dist = Counter(before.values())
for n in nodes:
    print(f"{n}: {dist[n]} ({100*dist[n]/len(keys):.2f}%)")

ring.add_node("node-5")
after = {k: ring.get_node(k) for k in keys}
moved = sum(1 for k in keys if before[k] != after[k])
print(f"keys remapped: {moved} / {len(keys)} = {100*moved/len(keys):.2f}%")
print(f"expected fraction under ideal consistent hashing ~= 1/6 = {100/6:.2f}%")

replicas = ring.get_replicas("key-0", 3)
print(f"replicas for 'key-0' with R=3: {replicas}")

With 5 nodes at 100 virtual nodes each and 50,000 keys, this prints a pre-add distribution of:

node-0: 12934 (25.87%)   node-1: 9422 (18.84%)   node-2: 9581 (19.16%)
node-3: 9774 (19.55%)    node-4: 8289 (16.58%)

against an ideal of 20.00% each, showing that even 100 virtual nodes per physical node leaves real
variance (node-0 is meaningfully over-represented), which is why production rings often use several
hundred virtual nodes per node to tighten this further. Adding a 6th node then produces:

keys remapped: 8479 / 50000 = 16.96%
expected fraction under ideal consistent hashing ~= 1/6 = 16.67%

closely matching the theoretical minimal-movement fraction rather than a full reshuffle. A
replication check for R=3 on one sample key returned 3 distinct physical nodes, confirming the
skip-already-seen-physical-node logic works: ['node-1', 'node-0', 'node-3'].

Trade-offs and pitfalls

Too few virtual nodes (e.g. one per physical node) gives no load-balancing benefit and can leave one node responsible for a hugely disproportionate arc purely by hash luck; too many (thousands per node) balances load further but grows ring metadata and lookup cost. The most common implementation bug is forgetting to deduplicate by PHYSICAL node while walking for replicas, silently returning the same physical node twice as two different replicas and reducing the real replication factor below R without any error being raised.

Direct answer

Generating short IDs for a URL shortener has three realistic options: hash the long URL and truncate
(risking collisions you must detect and handle), use a monotonically increasing counter encoded in a
compact base (e.g. base62, guaranteed collision-free but requires coordinating the counter across
shards), or generate a random ID and check for collision before committing (simple, but needs a
uniqueness check on every write). Most production designs land on a sharded counter or a
collision-checked random ID, not a raw hash truncation, specifically because hash truncation's
collision rate becomes a real operational problem at scale.

Structured elaboration

Why "just hash the URL and truncate" is the tempting but weaker option. A hash function
distributes long URLs into IDs, but a SHORT id (say 7 base62 characters, about 3.5 * 10^12 possible
values) truncated from a longer hash inherits the birthday-paradox collision behavior of that space,
at meaningful scale (billions of URLs), the odds of two different URLs truncating to the same short
ID stop being negligible, and now every WRITE needs a re-check-and-extend-on-collision path anyway,
undermining the "just hash it" simplicity that made this option appealing in the first place.

Counter-based generation avoids collisions structurally. If short IDs come from an always-
increasing counter (encoded in base62 for compactness: 7 base62 characters already cover over
3.5 trillion values), collisions are structurally impossible, no two counter values are ever equal.
The real engineering problem this creates is COORDINATING that counter across many write-serving
shards without it becoming a single bottleneck or a contention point, standard answers include
pre-allocating counter RANGES to each shard (so each shard hands out IDs from its own reserved block
without talking to a central counter on every write) or using a distributed ID generator (e.g. a
Snowflake-style scheme combining a timestamp, a shard ID, and a local sequence number into one
globally-unique value).

Sharding storage and handling hot keys. Once you have a short ID, routing "look up this ID's
target URL" to the right storage shard is itself a hashing/sharding decision, and consistent hashing is the standard mechanism, letting you add storage
capacity without re-shuffling nearly every existing mapping. A small number of extremely popular
short links (a "hot key", e.g. a viral URL getting a disproportionate share of the 1B/day redirect
traffic) benefit from an additional caching layer in front of the sharded storage, since the
consistent-hashing layer alone routes a hot key's reads to one shard/replica set, it doesn't by
itself absorb that shard's disproportionate read volume.

Supporting analytics. Redirects (1B/day, roughly 11,600/sec on average) are the hot read path,
so recording a click/redirect event can't sit synchronously in front of that response: incrementing
a counter in the same hash-based store on every redirect would turn the read-hot-key problem above
into a WRITE-hot-key problem on the exact same keys. The standard fix is to decouple: the redirect
handler emits a small, asynchronous event (short ID, timestamp, minimal request metadata) onto a
log or stream and returns the redirect immediately, without waiting on that write. A separate
downstream consumer aggregates those events (batched or streaming) into a store optimized for
analytics rollups (per-short-ID counts, referrer/geo breakdowns, time-bucketed series) that
dashboards read, not the redirect path itself. This keeps the redirect's hot path doing exactly one
thing (look up and redirect), and lets the analytics side scale, or even drop an occasional event
under overload, without ever affecting redirect latency or correctness.

Worked example

At 100M stored URLs and 1B redirects/day (about 11,600 redirects/sec on average, ignoring peak
skew), a counter-based scheme needs only about log62(100,000,000), roughly 5 base62 characters, to
uniquely represent every stored URL with room to grow, comfortably under the 6-7 character short
codes seen in practice, which typically budget headroom for years of future growth rather than
sizing exactly to the current count. The read path (1B/day, heavily read-dominated versus the
write/creation path) is where caching hot redirects in front of the sharded lookup store earns its
keep, since redirect lookups vastly outnumber new-URL creations.

Trade-offs and pitfalls

The pitfall worth naming explicitly: presenting hash-and-truncate as if it were collision-free "often
enough" without ever quantifying the actual birthday-paradox math at the scale the question specifies,
this is exactly the kind of claim that should come with a rough number (as above) rather than a bare
assertion. A second pitfall is treating the SHARDING/consistent-hashing layer as if it alone solved
hot-key read pressure, it solves balanced OWNERSHIP of the keyspace, not necessarily balanced READ
LOAD when a small number of keys receive a wildly disproportionate share of traffic, that needs an
explicit caching or replica-fan-out answer on top.

Direct answer

A lock-free hash table replaces mutexes with atomic compare-and-swap (CAS) operations on individual pointers or slots, so a thread that loses a race simply retries instead of ever blocking. That freedom brings two hard problems: safely freeing memory a reader might still be traversing, and resizing without a stop-the-world pause, both of which sharded locking sidesteps by simply accepting that one shard's lock holder can occasionally stall everyone else waiting on that same shard.

Structured elaboration

Non-blocking insert and lookup. Represent each bucket as a chain of nodes linked by atomic pointers. Insert performs a CAS on the relevant pointer (the bucket head, or a node's next pointer) to splice in a new node, and if the CAS fails because another thread's concurrent insert won first, the thread simply retries the CAS immediately, it is never suspended waiting on another thread. Lookup only follows pointers and never mutates anything, so it needs no synchronization at all beyond the atomic pointer reads themselves, which is why lookups are truly non-blocking.

Safe memory reclamation. The central hazard is freeing a node another thread is still mid-traversal on. Two standard techniques: hazard pointers, where each thread publishes, in a small shared per-thread slot, which node pointer it is currently about to dereference before it dereferences it; a thread that wants to free a removed node first scans all published hazard pointers and only frees the memory once no other thread has that node marked, otherwise it defers the free onto a retire list and rechecks later. Or epoch-based reclamation, where each thread announces a monotonically increasing global epoch counter value when it begins an operation, and memory removed during epoch E is only actually freed once every thread has advanced past epoch E, meaning nobody can still hold a reference into that stale epoch. Epoch-based reclamation is usually cheaper (an integer read/write versus scanning a hazard array) but reclaims memory less promptly, since one slow or stalled thread delays reclamation for every removed node, not just the ones it happens to touch.

Concurrent resizing. Allocate the new, larger table and migrate buckets from old to new incrementally, using a CAS-based per-bucket migration marker so that any thread, reader, writer, or an idle helper, that touches a not-yet-migrated bucket can help finish moving it (a common lock-free "helping" pattern that avoids any single thread becoming a resize bottleneck). Readers mid-transition either check both tables or follow a forwarding pointer left behind in a migrated bucket, so no key is ever lost or briefly duplicated.

Worked example

Compare the two designs directly:

For a service where even brief lock contention is unacceptable, this table is the actual argument for the added complexity: sharded locking still has a genuine worst-case blocking path (a popular shard, or a preempted lock holder), while the lock-free design guarantees every OTHER thread keeps making progress regardless of what one thread is doing.

Trade-offs and pitfalls

Be precise about the guarantee: lock-free means the system as a whole always makes progress, it does not mean any one specific thread is guaranteed to finish in bounded time (a thread could in principle retry indefinitely while others keep winning the race); that stronger, per-thread guarantee is called wait-free and costs considerably more to implement. The reclamation and resizing logic are also where the real engineering cost lives: hazard-pointer scans add a real per-operation cost, epoch-based schemes can leak memory indefinitely if a single thread stalls inside an old epoch and never advances, and resize-helping code is exactly the kind of rare-interleaving logic that passes ordinary tests and fails only under real production concurrency.

Direct answer

A hash set gives O(1) average membership checks regardless of blacklist size, which is the right
choice for a high-query-rate service; a sorted array with binary search gives O(log n)
membership checks, slower per query but with better cache locality and much lower per-entry
memory overhead. The real deciding factor is usually update frequency: a hash set tolerates
frequent updates cheaply, while a sorted array's inserts require shifting elements and are
expensive at scale.

Structured elaboration

Membership test complexity. A hash set computes one hash and does O(1) average work to
confirm or deny membership, independent of how many entries are in the set. A sorted array with
binary search needs ceil(log2(n)) comparisons in the worst case; for n = 1{,}000{,}000
entries, that is 20 comparisons, small in absolute terms but structurally always growing (however
slowly) with blacklist size, unlike the hash set's flat cost.

Cache locality. Binary search on a sorted array has excellent locality in one specific sense:
the array itself is one contiguous block, so each individual access is cheap, though the ACCESS
PATTERN (jumping to the middle, then a quarter point, etc.) is not sequential and does not
prefetch as well as a straight linear scan would. A hash set's single lookup touches one (or a
handful of, under collision) location directly, without the multi-step probe pattern binary
search requires, at the cost of that location being determined by a hash rather than a
predictable arithmetic position.

Update costs, the real differentiator. Inserting a new id into a SORTED array requires
finding its position and shifting every element after that position by one slot to keep the array
sorted; for a mid-range insert into a million-element array, that means moving on the order of
half a million elements. Inserting into a hash set touches exactly one new slot (amortized,
ignoring occasional resizing) with no shifting at all. For a blacklist that is updated
frequently (new abusive users added continuously), this asymmetry usually dominates the decision
far more than the query-time gap between O(1) and O(log n).

When to prefer each, concretely for a backend service. Prefer a hash set when the blacklist
updates frequently and query volume is very high (the question's "thousands of queries per
second" scenario clearly favors this). Prefer a sorted array with binary search when the
blacklist is effectively static or updated in large infrequent batches (rebuild the sorted array
wholesale on each batch update rather than incrementally), AND you specifically need the array's
side benefits, such as efficient RANGE queries (all ids between X and Y) or a smaller, more
predictable memory footprint per entry, neither of which a hash set provides at all.

Worked example

import bisect

def counting_bisect_left(sorted_list, target, counter):
    lo, hi = 0, len(sorted_list)
    while lo < hi:
        mid = (lo + hi) // 2
        counter[0] += 1
        if sorted_list[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

n = 1_000_000
blacklist_sorted = [2 * i for i in range(n)]
blacklist_set = set(blacklist_sorted)

counter_hit = [0]
idx_hit = counting_bisect_left(blacklist_sorted, 500_000, counter_hit)
print("HIT comparisons:", counter_hit[0], "found:", blacklist_sorted[idx_hit] == 500_000)

counter_miss = [0]
idx_miss = counting_bisect_left(blacklist_sorted, 999_999_501, counter_miss)
found_miss = idx_miss < n and blacklist_sorted[idx_miss] == 999_999_501
print("MISS comparisons:", counter_miss[0], "found:", found_miss)

print("hash set: 500,000 in set ->", 500_000 in blacklist_set)
print("hash set: 999,999,501 in set ->", 999_999_501 in blacklist_set)

# Update cost: inserting a new odd id into the sorted array shifts everything after it
new_id = 1_000_001
pos = bisect.bisect_left(blacklist_sorted, new_id)
shifted = len(blacklist_sorted) - pos
blacklist_sorted.insert(pos, new_id)
print(f"inserting {new_id} into the sorted array shifts {shifted} existing elements")

before_size = len(blacklist_set)
blacklist_set.add(new_id)
print(f"hash set size before: {before_size}, after: {len(blacklist_set)} (one new entry, no shifting)")

Instrumenting binary search to count actual comparisons against a sorted array of 1,000,000 even
ids: a HIT lookup (id 500,000, present) takes 19 comparisons, and a MISS lookup (id 999,999,501,
an odd number genuinely absent from the array) also takes 19 comparisons, both within the
ceil(log2(1{,}000{,}000)) = 20 theoretical bound. A hash set confirms the same membership
answers for both queries (True and False respectively) in a single in check. For the update
cost: inserting a new odd id (1,000,001) into the middle of the sorted array requires shifting
499,999 existing elements to keep it sorted, while inserting the same id into the hash set
touches exactly 1 new entry, no shifting, directly demonstrating the update-cost asymmetry the
"structured elaboration" section describes.

Trade-offs and pitfalls

• Do not decide this purely on the O(1) vs O(log n) query gap. At realistic blacklist sizes,
  20 comparisons versus 1 hash lookup is rarely the bottleneck; update pattern is usually the
  deciding factor in practice.
• A sorted array shines for range queries ("give me every blacklisted id between X and Y"), a
  query shape a hash set cannot answer efficiently at all (it would require scanning every entry);
  if that capability is ever needed, it tips the decision toward the array (or a hybrid, keeping
  both).
• Batch-rebuilding a sorted array (collect updates, then rebuild the whole sorted array
  periodically) sidesteps the expensive per-insert shifting cost, if the update latency
  requirement tolerates a delay between when an id is added and when it takes effect.
• Per-entry memory overhead is usually lower for a plain sorted array of fixed-size values
  than for a hash set's backing table (which reserves extra capacity to keep its load factor
  low); at very large scale with a memory-constrained service, this can matter as much as the
  update-cost argument.

Direct answer

hashCode() and equals() must be defined together and stay consistent: two objects that compare
equal MUST produce the same hash code, or a HashMap can insert a key, then fail to find it again
because it looks in the wrong bucket for the "equal" object. For a composite key, that means basing
both methods on the exact same set of fields, handling any nullable field the same way in both, and
caching the hash so repeated lookups aren't recomputing it from scratch.

Structured elaboration

The one-directional contract. The rule is not symmetric: equal objects must share a hash code,
but two objects sharing a hash code do NOT have to be equal (that's an ordinary collision, which the
table's collision-resolution strategy already handles via a follow-up equals() check within the
bucket). Violate the required direction (equal objects, different hashes) and the table breaks
structurally: insertion computes one bucket from the object's hash at that moment, but a later lookup
with an "equal" object computes a different hash, and therefore checks an entirely different
bucket, never finding the entry that is sitting right there in the other one.

Composite keys make this concrete. A key built from multiple fields (say userId, eventType,
date) needs both equals() and hashCode() to consider exactly the same fields, in the same way.
If equals() compares all three fields but hashCode() only hashes userId, two objects that differ
only in date would (correctly) compare unequal but (incorrectly, though harmlessly) share a hash
code, that's just a collision, not a contract violation, since equals() still separates them within
the bucket. The dangerous direction is the reverse: if hashCode() used all three fields but
equals() only compared userId, two objects with different dates but the same userId would compare
EQUAL yet (correctly, given they differ) hash DIFFERENTLY, silently breaking lookups for one of them.

Handling nulls. Any of the three fields (say eventType) may legitimately be null. Hand-rolled
field.hashCode() and field.equals(other.field) calls throw NullPointerException the moment that
field is null. Java's java.util.Objects utility class exists precisely for this: Objects.hash(a, b, c) treats a null argument as contributing 0 to the combined hash instead of throwing, and
Objects.equals(a, b) returns true when both are null, false when exactly one is null, and
delegates to a.equals(b) only when both are non-null. Using these consistently in both methods means
a null eventType behaves the same way in hashCode() as it does in equals(), which is the actual
requirement, not just "doesn't crash."

Performance. Recomputing a hash from three fields on every bucket lookup is wasted work if the
key object is immutable, since the hash can never change after construction. The standard technique
(the one java.lang.String itself uses) is to compute the hash once, in the constructor or lazily on
first use, and store it in a final int field that hashCode() just returns. This turns hashCode()
into an O(1) field read instead of an O(k) recomputation over k fields on every get/put/containsKey
call, which matters once the key class is hashed millions of times a second.

Why immutability matters here too. Even with a perfectly consistent contract, if any field that
feeds hashCode() mutates after the object has already been inserted as a key, the object's hash
changes but its position in the table (chosen using the OLD hash) does not move. A lookup using the
current (post-mutation) state now computes a different bucket than the one the entry actually lives
in. This is exactly the same "moved key" failure that using an inherently mutable type as a key
causes, just triggered here by careless field mutation instead. Marking every field final and
providing no setters makes this class of bug structurally impossible rather than merely unlikely, and
it's also what makes hash-caching in the constructor safe (a mutable field would invalidate the cache).

Worked example (Java)

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

final class CompositeKey {
    private final String userId;     // may be null
    private final String eventType;  // may be null
    private final String date;
    private final int cachedHash;    // computed once at construction

    CompositeKey(String userId, String eventType, String date) {
        this.userId = userId;
        this.eventType = eventType;
        this.date = date;
        this.cachedHash = Objects.hash(userId, eventType, date); // null-safe
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof CompositeKey)) return false;
        CompositeKey other = (CompositeKey) o;
        return Objects.equals(userId, other.userId)
                && Objects.equals(eventType, other.eventType)
                && Objects.equals(date, other.date);
    }

    @Override
    public int hashCode() {
        return cachedHash;   // O(1), not recomputed per lookup
    }
}

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

        CompositeKey k1 = new CompositeKey("u1", "click", "2026-01-01");
        CompositeKey k2 = new CompositeKey("u1", "click", "2026-01-01"); // distinct object, equal value
        counts.put(k1, "first-insert");
        System.out.println(k1.equals(k2));                  // true
        System.out.println(k1.hashCode() == k2.hashCode());  // true
        System.out.println(counts.get(k2));                  // "first-insert"

        // Null field: must not throw, and two null-eventType keys must still be equal
        CompositeKey n1 = new CompositeKey("u2", null, "2026-01-02");
        CompositeKey n2 = new CompositeKey("u2", null, "2026-01-02");
        counts.put(n1, "null-event-insert");
        System.out.println(n1.equals(n2));    // true
        System.out.println(counts.get(n2));   // "null-event-insert"
    }
}

Running this prints true, true, first-insert, true, null-event-insert. The first three lines
confirm the standard contract (equal objects, same hash, lookup by an equal-but-distinct object
succeeds); the last two confirm the null-field case behaves identically instead of throwing or
silently miscomparing.

Trade-offs and pitfalls

The most common real bug is hand-editing equals() (often to add or drop one field during a
refactor) and forgetting to update hashCode() to match, since Java does not enforce this
correspondence at compile time, IDEs' "generate equals and hashCode" helpers exist mainly to keep the
two in sync. Marking all key fields final (and re-deriving cachedHash only in the constructor)
makes the mutation-after-insertion bug structurally impossible rather than just unlikely, and using
Objects.hash/Objects.equals throughout removes null-handling as a place to introduce an
inconsistency between the two methods.