Hacker News new | ask | show | jobs
by matvore 2361 days ago
No, it's still O(N) amortized. Imagine if the hashmap doubles in capacity whenever it is full or hits its max load factor. Then you end up having O(N) copy operations. O(2 * N) = O(N)
1 comments

While your objection stands, repeated trainings of a hash table can be very impactful on the actual walltime spent, and it is a bad benchmark not to include the optimization of preallocating.