10,000 items, index with resizing on:

$ algo index -in s10k.jsonl
n = 10000, resize = true

  buckets          16384
  stored           10000
  resizes          10
  load factor      0.610
  empty buckets    8925
  mean chain       1.341
  LONGEST chain    5
  build time       1.5ms

  10000 lookups: 13095 comparisons (1.310 per lookup), 0s
  same by linear scan: 50005000 comparisons (5000.5 per lookup), 85ms

1.310 comparisons per lookup. The linear scan spent 5000.5 on the same 10,000 questions. That is 3,818× fewer, and 85 ms against a time the clock did not register.

The worst case — the longest chain — is 5. Not 5,000. That is what "O(1) average" means: not that every lookup costs exactly one step, but that the chains stay short and stop depending on n.

Where the O(1) goes without growth

$ algo index -in s10k.jsonl -nogrow -buckets 16
n = 10000, resize = false

  buckets          16
  stored           10000
  resizes          0
  load factor      625.000
  empty buckets    0
  mean chain       625.000
  LONGEST chain    680
  build time       20.527ms

  10000 lookups: 3134392 comparisons (313.439 per lookup), 17.117ms

Same data, same hash function, same code — 239× more comparisons. Because 10,000 items poured into 16 buckets is just 16 linear searches parked next to each other.

Growth is not an optimization. Without it a hash table is not a hash table.

Your guess

In step 1 you wrote down a number: how many comparisons with 10,000 items and 128 buckets?

$ for b in 128 512 2048 8192 16384; do algo index -in s10k.jsonl -nogrow -buckets $b; done

   buckets      load      mean   longest    cmps/lookup
       128    78.125    78.125       105         40.161
       512    19.531    19.531        34         10.830
      2048     4.883     4.929        15          3.465
      8192     1.221     1.740         7          1.620
     16384     0.610     1.341         5          1.310

40.161 — about half the load factor (78.125 / 2 ≈ 39), plus a little.

And it holds down the whole table: 19.531 → 10.8, 4.883 → 3.5, 1.221 → 1.6. A successful lookup stops on average halfway along the chain, so the cost is load / 2 + 1. That is not a rule of thumb — it is just the mean position of a key that is equally likely to be anywhere in the chain.

Which is why the threshold is 1.0 and not 10 or 100: growth keeps that quotient below two.

And look at the longest column. At 128 buckets the longest chain is 105 against a mean of 78. The average is not a promise about any individual lookup; some keys will always be worse off.