Dynamic resizing a hash table by doubling its size when it reaches a threshold capacity is amortised O(1) per insert.
If there are deletions, both operations are amortised O(1) provided they have been sensible and made the deletion threshold a lower factor.
It's the same sort of pattern as dynamically resizing a growing string. As long as you resize by a constant > 1 factor, rather than an addition, the number of resizes is low enough that the O(n) cost of copying is amortised over prior appends.
> Either way, it's definitely larger than the simpler O(n) case we're thinking about.
It actually isn't larger than O(n), setting aside constant factors.
For a hash map's time to grow more than O(n) for n insertions starting from empty, suggests an implementation problem.
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.)
If there are deletions, both operations are amortised O(1) provided they have been sensible and made the deletion threshold a lower factor.
It's the same sort of pattern as dynamically resizing a growing string. As long as you resize by a constant > 1 factor, rather than an addition, the number of resizes is low enough that the O(n) cost of copying is amortised over prior appends.
> Either way, it's definitely larger than the simpler O(n) case we're thinking about.
It actually isn't larger than O(n), setting aside constant factors.
For a hash map's time to grow more than O(n) for n insertions starting from empty, suggests an implementation problem.