Question: I have an unordered\_map with key as ULONG. 

I know that there can be a huge number of entries but not sure how many. So can't specify the bucket count before hand. I was expecting the time complexity for inserts to be O(1) since the keys are unique. But it seems like the inserts are taking very long time. 

I've read that this might be possible if there have been lots of re-hashing since the bucket count is unspecified which takes indeterministic time. 

Is there anything I can do to improve the time complexity of insert here. Or am I missing something?

Answer: 
Couple of things that might help:

1. You can actually compute when a rehash will take place and work out if that is the issue. From [cplusplus.com](http://www.cplusplus.com/reference/unordered_map/unordered_map/insert/):

"A rehash is forced if the new container size after the insertion operation would increase above its capacity threshold (calculated as the container's bucket\_count multiplied by its max\_load\_factor)."

2. Try to isolate the insert operation and see if it does indeed take as long as it seems, otherwise write a simple timer and place it at useful places in the code to see where the time is being eaten
Between [`max_load_factor`](http://www.cplusplus.com/reference/unordered_map/unordered_map/max_load_factor/) and preemptively calling [`reserve`](http://www.cplusplus.com/reference/unordered_map/unordered_map/reserve/), you should be able to both minimize rehashing, and minimize bucket collisions. Getting the balance right is mostly a matter of performance testing.