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

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

Open addressing stores every entry directly inside the backing array, with no linked nodes. add probes forward from the hashed index until it finds an empty slot or the key itself; remove must leave behind a TOMBSTONE marker rather than a true empty slot, or later lookups for a DIFFERENT key that had to probe past the removed slot would stop early and wrongly report it absent; and resizing has to happen well before the table nears full, because linear probing's performance degrades far faster than chaining's as load factor climbs.

Structured elaboration

Index computation. Spread the hash's bits before reducing modulo capacity (h ^= (h >>> 16) in Java) so that a hashCode() which only varies in its low bits still spreads across the table; skipping this step reproduces primary clustering even with an otherwise fine hash.

add(key). Check the resize threshold BEFORE inserting (kept conservative, 0.5 rather than the 0.75 that works fine for chaining); then linear-probe from the hashed index, remembering the first tombstone slot seen along the way so a reused tombstone is preferred over continuing to a further, truly-empty slot, which keeps live probe chains shorter across repeated insert/remove cycles. Return false if the key is already present.

contains(key). Probe from the hashed index; a true empty slot (never written) means the key cannot be further along this probe chain, since it would have stopped there during insertion too, so contains returns false immediately. A TOMBSTONE, by contrast, must NOT stop the search: the key being searched for may have been placed further along, past this now-removed entry, during its own insertion.

remove(key). On finding the key, overwrite it with the TOMBSTONE sentinel, never with null. Nulling would silently break contains() for any other key whose probe chain had to pass through this slot.

Resize and rehash. Double capacity and re-insert only the LIVE entries, dropping every tombstone in the process. This is also the tombstone cleanup mechanism, not just capacity growth: without it, repeated insert/remove churn would eventually fill the table with dead tombstones even while the live entry count stays low, which is why the resize trigger should be based on live-plus-tombstone count (used), not live count alone.

Avoiding clustering as load grows. Linear probing's expected probe length for a successful search is $\frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right)$ where $\alpha$ is the load factor, a curve that stays flat at low load and then rises sharply as $\alpha \to 1$, unlike chaining's roughly linear degradation; a conservative resize threshold and bit-spreading before modulo are what keep the table on the flat part of that curve.

Worked example

public class ProbingHashSet<E> {
    private static final Object TOMBSTONE = new Object();
    private static final double LOAD_FACTOR_LIMIT = 0.5;

    private Object[] table;
    private int size;   // live entries
    private int used;   // live + tombstones

    public ProbingHashSet(int initialCapacity) {
        table = new Object[initialCapacity];
        size = 0;
        used = 0;
    }

    private int indexFor(E key, int capacity) {
        int h = key.hashCode();
        h ^= (h >>> 16);
        return Math.floorMod(h, capacity);
    }

    public boolean add(E key) {
        if ((double) (used + 1) / table.length > LOAD_FACTOR_LIMIT) resize();
        int idx = indexFor(key, table.length);
        int firstTombstone = -1;
        for (int probes = 0; probes < table.length; probes++) {
            int i = (idx + probes) % table.length;
            Object cur = table[i];
            if (cur == null) {
                int placeAt = (firstTombstone != -1) ? firstTombstone : i;
                table[placeAt] = key;
                size++;
                if (firstTombstone == -1) used++;
                return true;
            }
            if (cur == TOMBSTONE) {
                if (firstTombstone == -1) firstTombstone = i;
                continue;
            }
            if (cur.equals(key)) return false;
        }
        throw new IllegalStateException("table full despite resize check");
    }

    public boolean contains(E key) {
        int idx = indexFor(key, table.length);
        for (int probes = 0; probes < table.length; probes++) {
            int i = (idx + probes) % table.length;
            Object cur = table[i];
            if (cur == null) return false;
            if (cur != TOMBSTONE && cur.equals(key)) return true;
        }
        return false;
    }

    public boolean remove(E key) {
        int idx = indexFor(key, table.length);
        for (int probes = 0; probes < table.length; probes++) {
            int i = (idx + probes) % table.length;
            Object cur = table[i];
            if (cur == null) return false;
            if (cur != TOMBSTONE && cur.equals(key)) {
                table[i] = TOMBSTONE;
                size--;
                return true;
            }
        }
        return false;
    }

    @SuppressWarnings("unchecked")
    private void resize() {
        Object[] old = table;
        table = new Object[old.length * 2];
        size = 0;
        used = 0;
        for (Object o : old) {
            if (o != null && o != TOMBSTONE) {
                add((E) o);
            }
        }
    }

    public int size() { return size; }
    public int capacity() { return table.length; }

    public static void main(String[] args) {
        ProbingHashSet<Integer> set = new ProbingHashSet<>(4);
        System.out.println("add(10): " + set.add(10));
        System.out.println("add(10) again (duplicate): " + set.add(10));
        System.out.println("contains(10): " + set.contains(10));
        System.out.println("contains(99): " + set.contains(99));

        for (int i = 1; i <= 10; i++) set.add(i);
        System.out.println("size after adding integers 1..10 (10 is a repeat of the first add): " + set.size());
        System.out.println("capacity after growth (started at 4): " + set.capacity());

        boolean allFound = true;
        for (int i = 1; i <= 10; i++) allFound &= set.contains(i);
        System.out.println("all 10 distinct elements still found after resize: " + allFound);

        // find two distinct, not-yet-inserted keys that hash to the SAME initial slot
        Integer a = null, b = null;
        int slot = -1;
        outer:
        for (int cand1 = 1000; cand1 < 5000; cand1++) {
            if (set.contains(cand1)) continue;
            int s1 = set.indexFor(cand1, set.capacity());
            for (int cand2 = cand1 + 1; cand2 < 5000; cand2++) {
                if (set.contains(cand2)) continue;
                if (s1 == set.indexFor(cand2, set.capacity())) { a = cand1; b = cand2; slot = s1; break outer; }
            }
        }
        System.out.println("collision pair mapping to same initial slot " + slot + ": a=" + a + ", b=" + b);

        set.add(a);
        set.add(b);
        System.out.println("contains(b) before removing a: " + set.contains(b));
        set.remove(a);
        System.out.println("contains(b) after removing a (tombstone in place): " + set.contains(b));
        System.out.println("contains(a) after removing a: " + set.contains(a) + " (must be false)");
    }
}

Compiled and run (starting capacity 4):

add(10): true
add(10) again (duplicate): false
contains(10): true
contains(99): false
size after adding integers 1..10 (10 is a repeat of the first add): 10
capacity after growth (started at 4): 32
all 10 distinct elements still found after resize: true
collision pair mapping to same initial slot 8: a=1000, b=1032
contains(b) before removing a: true
contains(b) after removing a (tombstone in place): true
contains(a) after removing a: false (must be false)

1000 and 1032 were found by scanning small integers for a pair that hashes to the same initial slot
after bit-spreading, so 1032's insertion had to probe past 1000's slot. After removing 1000,
contains(1032) still returns true because a tombstone, not null, was left behind; a broken
implementation that nulled the slot instead would have made contains(1032) incorrectly return
false the moment it hit that null. Note the size is 10, not 11: the loop re-adds 10 (already
present from the very first add(10) call), and that duplicate correctly returns false without
increasing size.

Trade-offs and pitfalls

Deleting via null instead of a tombstone is the single most common correctness bug in an open-addressing implementation: it fails silently (wrong answers, not a crash) for unrelated keys rather than the key actually removed. Never rehashing means tombstones accumulate indefinitely under insert/remove churn, degrading lookup performance as if the table were nearly full even when the live entry count is low, which is why the resize decision must watch live-plus-tombstone count, not live count alone.

Direct answer

A hash table stores key/value pairs so that lookup, insertion, and deletion all run in average-case
constant time, O(1), regardless of how many entries it holds. It does this by using a hash function
to convert each key into an integer, and using that integer (reduced modulo the table size) as the
index of an array where the entry lives.

Structured elaboration

The three moving parts.

• Keys are whatever you look things up by (a string, a number, a tuple of fields).
• Buckets are the slots of a fixed-size backing array. The number of buckets is the table's
  capacity.
• The hash function maps a key to an integer, and the table takes that integer modulo the
  capacity to get a bucket index. A good hash function scatters different keys roughly uniformly
  across the buckets, so no single bucket ends up disproportionately full.

Why O(1) is only an average, not a guarantee. If the hash function scatters n keys uniformly
across m buckets, each bucket holds about n/m keys on average, a small constant so long as the table
resizes to keep n/m bounded (this ratio is the load factor, covered by its own question). Looking a
key up means computing its bucket index once (O(1)) and then scanning that one small bucket, so the
whole operation is O(1) on average.

What breaks the average-case claim. The O(1) claim depends on the hash function actually
distributing keys uniformly over the keys you will actually see. It fails when:

1. The input is adversarial. An attacker who can choose the keys (e.g. form-field names, JSON
   object keys) can pick values that all hash to the same bucket, forcing every one of them into a
   single long chain, O(n) to look any of them up. This is a real, historically-exploited attack class (the mechanics and defenses are a deep topic in their own right).
2. Load factor is left unbounded. If the table never resizes as it fills up, buckets grow long
   even with an honest hash function.
3. The hash function itself is weak. A hash function with poor bit-mixing (e.g. one that only
   varies its low bits for common key patterns) can cluster "normal" keys into a few buckets even
   without any attacker.

Worked example

Take capacity m = 8 and insert three string keys using Python's built-in hashing:

# PYTHONHASHSEED=0 python3 this_file.py
# The seed is pinned ONLY so this example prints the same thing for you as it does here.
# Real deployments leave randomization ON: it is a hash-flooding defense.
keys = ["alice", "bob", "carol"]
m = 8
for k in keys:
    print(k, "-> bucket", hash(k) % m)

Output (actually run, PYTHONHASHSEED=0, reproducible across runs):

alice -> bucket 1
bob -> bucket 2
carol -> bucket 2

Note what actually happened: bob and carol both landed in bucket 2. Three keys into eight buckets collide more often than intuition suggests, and that is the point of this example rather than a flaw in it. alice is alone in bucket 1, so looking her up touches one bucket holding one entry. Looking up bob touches bucket 2, which holds two entries, so the table must compare against both. That is still O(1) on average, because the work per lookup depends on the length of ONE bucket, not on the size of the table.

If you run this without pinning the seed you will get different buckets every time, and on some runs all three keys share a bucket. If instead all three
happened to collide into the same bucket, the table would fall back to whatever collision-resolution
strategy it uses (chaining or open addressing, covered by their own question) and lookup would degrade
toward O(3) for that bucket, i.e. still fine at small n, but this is exactly the mechanism that turns
into O(n) at scale under bullet 1 or 2 above.

Trade-offs and pitfalls

A common junior mistake is to treat "hash tables are O(1)" as an unconditional fact rather than an
average-case property with named assumptions. A senior answer states the assumptions (uniform
hashing, bounded load factor, non-adversarial keys) up front and can point to at least one concrete
way each assumption can fail in production, which is exactly what separates this question from a
rote definition.

Direct answer

For small integer keys in a range 0..K, a direct-indexing array wins on raw lookup speed and
cache locality whenever the keys are DENSE (most of the range is actually used); a hash map wins
on memory whenever the keys are SPARSE (only a small fraction of the range is present), because
an array must pay for every slot in the range whether or not it holds a key, while a hash map
only pays for the keys that actually exist.

Structured elaboration

Dense case: prefer the array. If nearly every value in 0..K is a real key, a direct-index
array gives true O(1) lookup with no hashing step, no collision handling, and excellent cache
locality (sequential or nearby accesses land on adjacent memory, which the processor can
prefetch). This is strictly better than a hash map in the dense case: same or better time
complexity, no hashing overhead, no memory wasted on a mostly-empty array (since it is mostly
FULL by assumption).

Sparse case: prefer the hash map. If only a small fraction of 0..K is actually present
(the question's example: K = 1e9 but only 1e6 keys present, a 0.1% occupancy), a direct-index
array must still allocate all K slots, most of which are wasted space holding nothing. A hash
map instead allocates space roughly proportional to the number of keys actually present, at the
cost of a hashing step per lookup (still O(1) average) and slightly worse cache locality than
sequential array access (though still far better than, say, a tree).

The crossover point. As occupancy rises from sparse toward dense, there is a break-even
density where the array's fixed K-sized cost stops being worse than the hash map's
per-entry cost; above that density, the array becomes the more memory-efficient choice again,
in addition to already being the faster one. Where exactly that crossover sits depends on the
per-entry overhead of the specific hash map implementation you are using, which is worth
measuring rather than assuming.

Update patterns. Both structures support O(1) average insert and update for a key already
within range. The practical difference under updates is less about complexity and more about
whether new keys can appear OUTSIDE the originally assumed range K: an array sized for K at
allocation time cannot cheaply grow past K without a full reallocation and copy, while a hash
map's amortized resizing (doubling capacity and rehashing existing entries once load factor
crosses a threshold) handles arbitrary growth naturally, since it was never tied to a fixed K
in the first place.

Worked example

import sys

K = 1_000_000_000
present = 1_000_000
dense_array_bytes = K * 4  # int32 slots

sample = {i: i for i in range(100_000)}
bytes_per_entry = sys.getsizeof(sample) / len(sample)
hashmap_bytes = present * bytes_per_entry

print(dense_array_bytes, hashmap_bytes, dense_array_bytes / hashmap_bytes)

For K = 1{,}000{,}000{,}000 (1e9) with int32 slots, a dense direct-index array needs
4{,}000{,}000{,}000 bytes (about 3.73 GiB), allocated regardless of occupancy. Measuring a real
Python dictionary's actual memory footprint (sys.getsizeof) for 100,000 int-to-int entries
gives about 52.4 bytes per entry for the hash table's backing structure; extrapolating that
measured per-entry cost to the question's 1{,}000{,}000 present keys gives roughly 50 MiB for
the hash map, versus 3.73 GiB for the array, about 76 times more memory for the array at this
0.1% occupancy. Solving for where the array stops being the memory loser (dense_array_bytes <= present_entries * bytes_per_entry) with these measured numbers gives a break-even around 7.6%
occupancy: below that density, the hash map wins on memory; above it, paying for the full K
slots up front costs less than the hash table's per-entry overhead.

Trade-offs and pitfalls

• "Small integer keys" is doing real work in the question. This comparison is specific to
  integer keys in a bounded range; it does not generalize to string or composite keys, which have
  no natural direct-index mapping at all.
• The measured 76x and 7.6% break-even numbers above are specific to this demo's assumptions
  (int32 array slots, a particular runtime's dictionary overhead); recompute for your actual
  value type and hash-map implementation rather than treating these as universal constants.
• A common mistake is defaulting to a hash map "to be safe" even when the key range is known,
  small, and dense, giving up the array's simplicity and cache-locality advantage for no real
  benefit.
• The reverse mistake, defaulting to a huge array because the key TYPE happens to be an
  integer, is exactly the failure mode the sparse case in this question is testing for.