Hashing and Hash Tables Questions

Direct answer

Weighted consistent hashing changes exactly one thing from the uniform-capacity version: the NUMBER of virtual positions a physical node gets on the ring is made proportional to that node's relative capacity, so a node with twice the capacity claims roughly twice the ring surface. The ring-walk lookup, minimal-movement rebalancing, and failure handling all work identically to the unweighted case once that allocation is set.

Structured elaboration

Virtual node allocation proportional to weight. For nodes with weights $w_i$ and a chosen total virtual-node budget $V_{\text{total}}$, assign node i:

$v_i = \frac{w_i}{\sum_j w_j} \times V_{\text{total}}$

rounded to an integer. A node with weight 4 in a {4, 2, 1} weight set (total weight 7) is entitled to 4/7 of the total virtual-node budget.

Hashing strategy for mapping keys. Identical to the unweighted ring: hash the key, walk clockwise to the first virtual-node position. Weight only changes how many positions each node occupies, never how a key finds its owner.

Replication across regions. Two common patterns: a single global ring where replica placement skips any candidate node already in a region another chosen replica occupies (region-aware placement), guaranteeing a key's R replicas span at least the required number of distinct regions for regional-failure tolerance; or a separate ring per region plus an explicit cross-region replication policy (e.g. asynchronous replication of a primary region's writes to one designated secondary region), trading immediate cross-region consistency for stronger regional isolation.

Minimizing reshuffle. Adding a node inserts its weight-proportional virtual positions, and only the immediately-following arcs move, exactly as in the unweighted case, but the SHARE that moves to the new node is now proportional to its own weight relative to the total, $w_{\text{new}} / \sum_j w_j$, rather than a flat $1/(N+1)$: a node twice as capable should, and does, absorb roughly twice the reshuffled keyspace.

Failure handling. A failed node's virtual positions are removed (or marked unavailable) and its keys fall through to the next clockwise position, the same mechanism as node removal, no special-casing required; combined with region-aware replica placement, a full-region outage still leaves at least one surviving replica for every key as long as replication was configured to span at least 2 regions.

Worked example

Weights {A: 4, B: 2, C: 1}, total weight 7, $V_{\text{total}} = 700$:

$v_A = \frac{4}{7}\times 700 = 400, \quad v_B = \frac{2}{7}\times 700 = 200, \quad v_C = \frac{1}{7}\times 700 = 100$

summing exactly to 700. Node A, at 4x node C's capacity, receives exactly 4x the virtual nodes (400 vs 100) and so is expected to receive roughly 4x C's share of both steady-state traffic and any future reshuffled keys.

Trade-offs and pitfalls

Rounding $v_i$ to an integer introduces deviation from the exact target ratio whenever weights don't divide $V_{\text{total}}$ evenly (this example's clean 4:2:1 split is the easy case); at a small $V_{\text{total}}$, rounding error is a larger fraction of each node's allocation, so weighted consistent hashing generally needs a larger virtual-node budget than the unweighted case to hit target ratios accurately. Region-aware replica placement adds real routing complexity, the walk must now track distinct REGIONS seen, not just distinct physical nodes, and in a poorly balanced deployment (a region with only one node) it can fail to find R replicas across the required region spread at all, which needs an explicit fallback policy (accept fewer effective replicas and alert, rather than silently under-replicating).

Direct answer

An object is hashable if it has a hash value that never changes during its lifetime and an equality
check consistent with that hash value. Lists and dictionaries are unhashable in Python precisely
because they are mutable: their contents (and therefore what their hash should be) can change after
you've already used them as a key, which would silently corrupt the table.

Structured elaboration

The contract a hash table depends on. A hash table computes hash(key) % capacity once, at
insertion, to choose a bucket, and does the same computation again at lookup time to find that
bucket. If the key's hash value could change in between (because the key itself changed), the second
computation would look in the wrong bucket and the entry would appear to have vanished, this is the
exact failure mode mutability creates, not a Python implementation quirk but a structural requirement
of how every hash table works.

Why immutability is the guardrail. Immutable built-ins (strings, numbers, tuples of immutable
elements) are hashable by default because nothing about them can change after creation, so their hash
is safe to cache and reuse forever. Lists and dicts are explicitly excluded (hash([1,2,3]) raises
TypeError) precisely to stop you from creating this bug by construction, Python would rather fail
loudly at the point you try to use a list as a key than silently corrupt a dict later.

Worked example: why the bare case fails

d = {}
key = (1, 2)          # tuple of ints: immutable, hashable
d[key] = "ok"
print(d[(1, 2)])       # "ok" -- fine, the tuple can never change

try:
    bad_key = [1, 2]   # a list: mutable, unhashable
    d[bad_key] = "boom"
except TypeError as e:
    print("TypeError raised (unhashable type: list)")

# The genuinely dangerous case: a tuple that CONTAINS a mutable object.
# Tuples are hashable only if every element inside them is hashable at hash-time;
# nothing stops you from later mutating that inner element.
inner = [1, 2]
sneaky_key = (inner, "label")
try:
    d[sneaky_key] = "will this even work?"
except TypeError as e:
    print("TypeError on tuple containing a list (unhashable type: list)")

Running this: the first insert succeeds and prints ok. The bare-list insert raises a TypeError
mentioning unhashable type: 'list', caught as printed (the exact wording of that message has
changed slightly across Python versions, but the failure is always a TypeError at the point of
use). The "sneaky" tuple-containing-a-list case ALSO raises TypeError, because Python checks
hashability of every element when it hashes the outer tuple, so it fails immediately at insertion
rather than allowing a later, harder-to-diagnose corruption. The real danger in production code is
not this caught case, it's when someone works around the TypeError by converting the list to
something hashable (e.g. id(inner) or a shallow copy) and then mutates the original list
afterward, which silently desyncs the key's later identity from what the table actually stored it
under, no exception, just a lookup that mysteriously "loses" data.

Three ways to safely key on mutable or complex data

1. Freeze the structure (tuple / frozenset). Recursively convert lists to tuples and dicts to
frozensets of (key, value) pairs. This makes nested, order-varying structures compare and hash
consistently, since frozenset is order-independent for dict-shaped data:

def freeze(obj):
    """Recursively convert lists/dicts into hashable tuples/frozensets."""
    if isinstance(obj, dict):
        return frozenset((k, freeze(v)) for k, v in obj.items())
    if isinstance(obj, list):
        return tuple(freeze(v) for v in obj)
    return obj

record_a = {"user": "alice", "tags": ["x", "y"]}
record_b = {"tags": ["x", "y"], "user": "alice"}  # same content, different key order

cache = {}
cache[freeze(record_a)] = "cached-result"
print(freeze(record_a) == freeze(record_b))   # True
print(cache.get(freeze(record_b)))            # "cached-result" -- hits despite key-order difference

Output: True then cached-result, confirming the frozen key is order-independent. Trade-off:
freezing allocates a new structure per lookup and is O(size of the structure), and nested unhashable
leaves (e.g. a list buried three levels deep) still need to be frozen too, recursion handles that but
adds overhead.

2. Canonical serialization. Turn the object into a deterministic string (or bytes) and key on
that. json.dumps(obj, sort_keys=True) is the common choice for JSON-shaped data:

import json

def canonical_key(obj):
    return json.dumps(obj, sort_keys=True)

record_a = {"user": "alice", "tags": ["x", "y"]}
record_b = {"tags": ["x", "y"], "user": "alice"}  # same content, different key order

d2 = {}
d2[canonical_key(record_a)] = "cached-result-2"
print(d2[canonical_key(record_b)])   # "cached-result-2" -- same canonical string regardless of order

Output: cached-result-2. Trade-off: simple and works across process boundaries (the string can be
persisted or sent over the wire), but floats serialize with locale/precision quirks (0.1 vs
0.10000000000000001), and it's slower than a native hash for large objects since it re-encodes the
whole structure on every lookup.

3. Custom __hash__ and __eq__ that ignore volatile fields. When only some fields define
identity (a cached score that legitimately changes shouldn't invalidate the key), hash and compare on
the immutable identity fields only, and document that the mutable field must never be touched from
outside:

class UserScore:
    """Cached score can change; identity for hashing/equality is user_id only."""
    def __init__(self, user_id, score):
        self.user_id = user_id   # identity field: must stay constant
        self.score = score       # volatile field: excluded from hash/eq

    def __hash__(self):
        return hash(self.user_id)

    def __eq__(self, other):
        return isinstance(other, UserScore) and self.user_id == other.user_id

seen = {}
u1 = UserScore(user_id=42, score=10)
seen[u1] = "first-seen"
u1.score = 99                     # mutate the volatile field AFTER insertion
print(seen[u1])                                # "first-seen" -- still found
print(seen[UserScore(user_id=42, score=-1)])   # "first-seen" -- different object, same identity

Output: first-seen printed twice, first for the mutated original object, then for a brand-new
object that only shares the identity field. This is the Java hashCode/equals pattern too: base
both on the same subset of fields, and never on a field that changes post-insertion.

Trade-offs and pitfalls

The instinctive fix many candidates reach for, wrapping a mutable structure in something hashable
just to satisfy the type checker, doesn't remove the underlying risk unless the wrapped value is
ALSO guaranteed not to change afterward; a frozenset or an immutable tuple genuinely solves this,
while hashing on id() or a one-time snapshot does not, since the object behind that identity can
still be mutated by other code holding a reference to it. Freezing is fastest for in-process,
short-lived keys; canonical serialization is best when the key must cross a process boundary or be
persisted; custom __hash__/__eq__ is right when you own the class and want to control identity
semantics explicitly rather than reconstructing it from raw data every time.

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.

Direct answer

When two keys hash to the same bucket, you either let that bucket hold multiple entries (separate
chaining, usually a small linked list or dynamic array per bucket) or you find a different, empty
slot elsewhere in the same table (open addressing, via linear probing, quadratic probing, or
double hashing). Chaining is simpler and more forgiving of a bad hash function; open addressing is
more cache-friendly and memory-efficient when it works well.

Structured elaboration

Separate chaining. Each bucket is itself a small container (linked list, or a dynamic array/tree
once Java's HashMap treeifies a long chain). Insertion appends to the bucket's list; lookup hashes to
the bucket then scans its (usually very short) list; deletion is a normal list removal, no special
handling needed. Memory overhead is one pointer/node per entry beyond the raw key/value, but the
table degrades gracefully, a bad hash function just makes some chains longer, it never causes the
whole table to fail.

Open addressing. All entries live directly in the backing array; there is no auxiliary structure.
On a collision, the table computes an alternate slot via a probe sequence:

• Linear probing: try index+1, index+2, ... . Simple and extremely cache-friendly (the next slot
  is usually already in the same cache line), but suffers primary clustering: once a run of
  occupied slots forms, it tends to grow, since any key hashing anywhere inside the run has to probe
  through the whole thing.
• Quadratic probing: try index+1, index+4, index+9, ... . Spreads probes out faster, reducing
  primary clustering, at some cost to cache locality and at the risk of not visiting every slot
  unless the table size and quadratic step are chosen carefully.
• Double hashing: the probe step size itself comes from a second hash function, so different
  keys that collide at the same first slot follow different probe sequences, avoiding secondary
  clustering. This needs the step size to be coprime with the table size (its own dedicated
  question covers exactly this).

Deletion under open addressing is the sharp edge. You cannot simply clear a slot to "empty," or a
later probe sequence that walked past it looking for a still-present key would incorrectly stop early
and report the key missing. Implementations use a tombstone marker (a distinct third state:
occupied / tombstone / never-used) so probing keeps walking through tombstones, while insertion is
allowed to reuse a tombstone slot (covered in depth separately: it needs a dedicated tombstone marker rather than clearing the slot outright, and why tombstones must eventually be cleared by a full rehash).

Worked example

Table of capacity 8, linear probing, keys hash to indices [3, 3, 4, 3] for keys A, B, C, D in that
order:

• A -> slot 3 (empty, placed directly)
• B -> wants slot 3 (occupied by A), probes to slot 4 (empty, placed)
• C -> wants slot 4 (occupied by B), probes to slot 5 (empty, placed)
• D -> wants slot 3 (occupied), probes 4 (occupied), probes 5 (occupied), lands at slot 6

Four keys that only collided on their first choice ended up forming one contiguous run of length
four (slots 3 to 6), which is exactly primary clustering: every future key hashing into slots 3
through 6 now has to walk through this whole run. Under separate chaining, the same four keys would
simply form two short chains (bucket 3: [A, B, D]; bucket 4: [C]), no run, no clustering across
neighboring buckets.

Trade-offs and pitfalls

Open addressing needs the load factor kept meaningfully below 1 (commonly under 0.7 to 0.75) because
performance degrades sharply as the table fills, an empty slot becomes hard to find. Chaining
degrades far more gracefully and can even be pushed past a load factor of 1 (average chain length
just grows past one entry). The real-world default matters here: Java's HashMap uses chaining
(with treeification of long chains since Java 8), while Python's dict uses open addressing
internally, both are legitimate, widely-used production choices, so "which is better" depends on
whether you value graceful degradation under a bad hash function (chaining) or raw cache locality and
lower per-entry memory overhead when the hash function is trustworthy (open addressing).