Hashing and Hash Tables Questions

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

A normal resize stops the world: it allocates a new, larger bucket array and walks every existing entry into it before anything else can proceed, which is exactly what produces a long garbage collection (GC, the JVM or runtime's process for reclaiming memory) or stop-the-world pause at tens of millions of entries. Incremental (progressive) resizing instead keeps the old and new tables alive side by side and migrates a small, fixed number of buckets on every subsequent put, get, and remove call, so the cost of the resize is spread as a tiny constant surcharge across many operations instead of one enormous pause on a single operation.

Structured elaboration

Algorithm. When the load factor crosses its threshold, do not rehash immediately. Instead:

1. Allocate the new, larger bucket array, but keep the old array around too.
2. Track a migration cursor (an index into the old array) starting at 0.
3. On every subsequent put, get, and remove, before doing that call's own work, migrate a fixed small number of old buckets (say 2) into the new array, advancing the cursor. Once the cursor passes the end of the old array, drop it and the migration is complete.
4. While migration is in progress, new inserts go directly into the new table (never the old one), and lookups check the new table first, falling back to the old table only if the new table does not have the key.

Required invariants during the transition period. Every key that existed before the resize started must be found by exactly one of: already migrated into the new table, or still reachable via a lookup into the old table at its old bucket. A key must never be reachable in both stale and fresh form after being explicitly deleted; a remove during migration has to check and clear the key from whichever table currently holds it, old or new. The migration cursor must advance monotonically and only ever look at each old bucket exactly once, so the total migration work across the whole transition is bounded (no bucket is migrated twice, and no bucket is skipped).

Preserving correctness. The critical property is that at every point during migration, a get for any key that exists must succeed by checking new-then-old, and a get for any key that does not exist must fail on both, and a remove mid-migration must delete the key from whichever table it is actually sitting in so it does not reappear from the other one. The demo below verifies all three directly, with remove actually invoked and confirmed to work while _migrating() still reports True, not just asserted in prose.

Code

class IncrementalHashMap:
    MIGRATE_PER_OP = 2

    def __init__(self, capacity=4):
        self._capacity = capacity
        self._buckets = [[] for _ in range(capacity)]
        self._size = 0
        self._old_buckets = None
        self._old_capacity = None
        self._migrate_index = 0

    def _migrating(self):
        return self._old_buckets is not None

    def _start_resize(self):
        self._old_buckets = self._buckets
        self._old_capacity = self._capacity
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        self._migrate_index = 0

    def _migrate_step(self):
        if not self._migrating():
            return
        for _ in range(self.MIGRATE_PER_OP):
            if self._migrate_index >= self._old_capacity:
                self._old_buckets = None
                self._old_capacity = None
                self._migrate_index = 0
                return
            bucket = self._old_buckets[self._migrate_index]
            for k, v in bucket:
                idx = hash(k) % self._capacity
                self._buckets[idx].append((k, v))
            self._migrate_index += 1

    def put(self, key, value):
        self._migrate_step()
        if not self._migrating() and (self._size + 1) / self._capacity > 0.75:
            self._start_resize()
            self._migrate_step()
        idx = hash(key) % self._capacity
        for i, (k, v) in enumerate(self._buckets[idx]):
            if k == key:
                self._buckets[idx][i] = (key, value)
                return
        self._buckets[idx].append((key, value))
        self._size += 1

    def get(self, key):
        self._migrate_step()
        idx = hash(key) % self._capacity
        for k, v in self._buckets[idx]:
            if k == key:
                return v
        if self._migrating():
            old_idx = hash(key) % self._old_capacity
            for k, v in self._old_buckets[old_idx]:
                if k == key:
                    return v
        return None

    def remove(self, key):
        self._migrate_step()
        idx = hash(key) % self._capacity
        for i, (k, v) in enumerate(self._buckets[idx]):
            if k == key:
                del self._buckets[idx][i]
                self._size -= 1
                return True
        if self._migrating():
            old_idx = hash(key) % self._old_capacity
            for i, (k, v) in enumerate(self._old_buckets[old_idx]):
                if k == key:
                    del self._old_buckets[old_idx][i]
                    return True
        return False


if __name__ == "__main__":
    # Bigger starting table + MIGRATE_PER_OP=1 so migration stays in flight
    # across several operations, wide enough to test remove() WHILE it's happening.
    m = IncrementalHashMap(capacity=8)
    m.MIGRATE_PER_OP = 1
    for i in range(6):
        m.put(f"k{i}", i)
    m.put("k6", 6)  # crosses load factor 0.75 at capacity 8, starts migration (old_capacity=8)
    print("mid-migration right after starting? ->", m._migrating(),
          "| old_capacity ->", m._old_capacity, "| new capacity ->", m._capacity,
          "| migrate_index ->", m._migrate_index)

    # Remove a key WHILE migration is still in flight (only 1 bucket/op migrated,
    # 8 old buckets total, so several ops are needed before it finishes).
    removed = m.remove("k1")
    print("remove k1 while still migrating ->", removed, "| still migrating ->", m._migrating())
    print("get k1 after remove ->", m.get("k1"))

    # never-inserted key while migration is still in flight
    print("get on never-inserted key while migrating ->", m.get("zzz_absent"), "| still migrating ->", m._migrating())
    print("remove on never-inserted key while migrating ->", m.remove("zzz_absent"))

    print("other keys still correct while migration continues ->",
          all(m.get(f"k{i}") == i for i in range(7) if i != 1))

    # Force-drain any in-flight migration (including any cascading second resize
    # triggered by further puts below) so we can assert a clean post-migration state.
    for i in range(7, 20):
        m.put(f"k{i}", i)
    while m._migrating():
        m._migrate_step()
    print("migration fully drained ->", not m._migrating())
    print("k1 stays removed after migration completes ->", m.get("k1") is None)
    print("all surviving keys correct post-migration ->",
          all(m.get(f"k{i}") == i for i in range(20) if i != 1))

Output (executed as shown):

mid-migration right after starting? -> True | old_capacity -> 8 | new capacity -> 16 | migrate_index -> 1
remove k1 while still migrating -> True | still migrating -> True
get k1 after remove -> None
get on never-inserted key while migrating -> None | still migrating -> True
remove on never-inserted key while migrating -> False
other keys still correct while migration continues -> True
migration fully drained -> True
k1 stays removed after migration completes -> True
all surviving keys correct post-migration -> True

Trade-offs and pitfalls

• Extra memory during the transition. Both the old and new arrays are alive simultaneously until migration completes, roughly 1.5x the steady-state memory at the moment right after a resize starts (old array plus a new array sized double the old). For a table already holding tens of millions of entries, this transient overhead has to be budgeted for, not just the steady-state size.
• Read amplification while migrating. A lookup for a key that has not yet been migrated costs two bucket scans (new table miss, then old table check) instead of one; this is the price paid for never taking a single big pause, and it is bounded and predictable rather than a spike.
• The migration rate is a tunable knob. Migrating too few buckets per operation (say 1) stretches the transition period over more operations, each cheaper; migrating too many (say the whole table) collapses back into the stop-the-world behavior this design exists to avoid. The right rate is chosen so the transition finishes comfortably before the next resize would otherwise be needed.
• A second resize must not start before the first finishes. The guard here explicitly checks not self._migrating() before starting a new resize; without it, an old-old-new three-way state becomes possible and the invariant that a key is findable in exactly the old-or-new pair breaks down.
• A common wrong turn: treating the migration cursor as optional and instead trying to lazily migrate only the buckets a lookup happens to touch. That approach never provides a bound on how long the tail of untouched old buckets survives, so a resize can, in the worst case, never fully complete if some old buckets are never queried again, quietly doubling memory forever instead of just temporarily.

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

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

Doubling capacity gives amortized O(1) insertion because the total cost of all the copying done across n insertions is bounded by a geometric series that sums to O(n), a standard aggregate-analysis argument. A smaller growth factor like 1.5x keeps the same asymptotic O(1) amortized guarantee but changes both constants in opposite directions: it wastes less memory right after a resize but does strictly more total copying over the table's lifetime, which is why memory-constrained services sometimes deliberately choose a smaller factor despite the extra copying cost.

Structured elaboration

Formal proof: doubling gives amortized O(1)

Use the aggregate method. Suppose the table starts at capacity $C_0$ and doubles every time it fills: $C_0, 2C_0, 4C_0, \dots$ After $n$ insertions, the table has resized $r = \lceil \log_2(n/C_0) \rceil$ times. Each resize at capacity $2^{i}C_0$ copies all $2^{i}C_0$ existing elements. The total copying work across all resizes is

a geometric series that telescopes to strictly less than $2n$, that is, $O(n)$ total copying work for $n$ insertions. Adding the $n$ direct insertion costs (O(1) each, O(n) total) gives total work $O(n)$ for $n$ insertions, so the AMORTIZED cost per insertion, total work divided by $n$, is $O(1)$, even though any single insertion that triggers a resize costs $O(n)$ in that instant.

Alternative growth factors: 1.5x versus 2x

The same argument holds for any growth factor $g > 1$: the geometric series still telescopes to $O(n)$ total copying, so amortized O(1) holds for ANY fixed $g>1$, not just doubling. What changes is the CONSTANT inside that O(1), in two opposite directions:

• Time constant: total copying work relative to $n$ scales with $\frac{g}{g-1}$. This is LARGER for smaller $g$: at $g=2$, the constant is 2 (copy up to 2x the final size in aggregate); at $g=1.5$, the constant is 3 (copy up to 3x). Smaller growth factors resize more often and do MORE total copying over the table's life.
• Space constant: right after a resize to capacity $gC$ holding $C$ elements, the table is only $1/g$ full. At $g=2$, that is 50% full (up to half the allocated capacity is temporarily wasted); at $g=1.5$, that is about 67% full (only about a third wasted). Smaller growth factors waste LESS peak memory.

So doubling buys a cheaper amortized time constant at the cost of wasting up to half the table's capacity right after a resize; a smaller factor like 1.5x wastes less memory at the cost of a larger total-copying constant over the table's lifetime.

When a smaller growth factor is preferable

For a memory-constrained service, many small maps held simultaneously, or a hard per-process memory limit such as embedded or high-density multi-tenant deployments, the up-to-50%-wasted peak capacity of doubling is a real, direct memory cost multiplied across every live table. Trading some extra copying work (a CPU cost, generally cheaper and more elastic than a hard memory ceiling) for a tighter worst-case memory bound is the right trade when memory, not CPU, is the binding constraint.

Worked example (10 million keys)

Target: insert 10,000,000 keys, keeping the load factor at or below 0.75 at all times, starting from an initial capacity of 16 and doubling.

Minimum capacity needed to hold 10,000,000 keys at a 0.75 load factor: $10{,}000{,}000 / 0.75 \approx 13{,}333{,}334$. The smallest power of two at or above that is $2^{24} = 16{,}777{,}216$. Starting from $2^4=16$ and doubling to $2^{24}$ takes exactly

Total copying work across those 20 resizes (summing the capacity at each resize: $16+32+64+\dots+2^{23}$) is $2^{24}-16 = 16{,}777{,}200$ element-copies, about 1.68x the final key count of 10,000,000, confirming the amortized O(1) bound concretely: roughly 1.68 copy-operations per insertion on average, despite 20 individual resize events, several of which each cost millions of copies in that single instant.

Mitigating long pause times in production

• Pre-size when the target is knowable: if 10,000,000 is known or well-estimated ahead of time, constructing the table at capacity $2^{24}$ directly eliminates all 20 resizes and their pauses, at the cost of allocating the full capacity up front even before it is needed.
• Incremental (lazy) resizing: instead of copying the entire old table in one atomic step, keep both the old and new tables alive during a transition window and migrate a bounded number of entries (a few buckets) on each subsequent operation, spreading one large pause into many tiny ones; this is how some production key-value stores avoid a single stop-the-world copy.
• Smaller growth factor: reduces the SIZE of the worst individual pause (each resize copies less, since resizes happen more often but at a smaller jump), trading a few large pauses for more numerous, smaller ones, useful when the tail latency of one huge pause matters more than the higher aggregate resize count.
• Segmented structures: a table built from independently-sized segments, adding a new segment instead of reallocating and copying the whole table, avoids the "copy everything" pattern altogether, at the cost of a slightly more complex lookup path (checking the right segment).

Trade-offs and pitfalls

• Treating "amortized O(1)" as meaning "every insertion is fast" is the most common misreading of this proof; the guarantee is about the AVERAGE over many insertions, individual resize-triggering insertions are genuinely $O(n)$ in that instant, exactly why production services with strict per-operation latency budgets need the mitigations above, not just the amortized guarantee.
• Choosing a growth factor without a specific memory or latency constraint driving the choice is arbitrary; the analysis above only tells you the shape of the trade-off, the right point on it depends on which resource, memory or CPU/pause time, is actually scarce for the specific service.