[mijoharas]

I should have thought about things more. I think this is a case of confirmation bias on my part.

I thought "what about dynamically resizing" and quickly googled complexity of rehashing a hash which confirmed my thought that it was n.

I guess I didn't think that since we must have inserted n values in at this point, we could just say "insertion is O(1)" and the constant factor would be "performing two hashes" if we are going to a point where it's resizing, i.e. pay the cost of hashing once and rehashing once.

that feels like it makes sense. I'm being a bit hand-wavy as I don't want to sit down with pen and paper.

I retract my incorrect statement above. (I can no longer edit it to add postscript retraction.)