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
For a start, many Standard Library implementations hash integers with an identity function, i.e. `hash(x) == x`. This is usually ok, especially if the implementation ensures the bucket count is prime (e.g. GCC), but some implementations use power-of-two bucket counts (e.g. Visual C++). You could run some numbers through your hash function and see if it's an identity function: if so, consider whether your inputs are sufficiently random for that not to matter. For example, if your numbers are all multiples of 4, then a power-of-two bucket count means you're only using a quarter of your buckets. If they tend to vary most in the high-order bits that's also a problem because bitwise-AND with a power-of-two bucket count effectively throws some number of high order bits away (for example, with 1024 buckets only the 10 least significant bits of the hash value will affect the bucket selection).

A good way to check for this type of problem is to iterate over your buckets and create a histogram of the number of colliding elements, for example - given `unordered_map` `m`:

```
std::map<int, int> histogram;
for (size_t i = 0; i < m.bucket_count(); ++i)
    ++histogram[m.bucket_size(i)];
for (auto& kv : histogram)
    std::cout << ".bucket_size() " << kv.first << " seen "
              << kv.second << " times\n";

```

(You can see such code run [here](http://coliru.stacked-crooked.com/a/83b4cfdcfbf4b11c)).

You'd expect the frequency of larger `bucket_size()` values to trail away quickly: if not, work on your hash function.

On the other hand, if you've gone over-the-top and instantiated your `unordered_map` with a 512-bit cryptographic hash or something, that will unnecessarily slow down your table operations too. The strongest hash you need consider for day-to-day use with tables having less than 4 billion elements is a 32 bit murmur hash. Still, use the Standard Library provided one unless the collisions reported above are problematic.

Switching to a closed addressing / open hashing hash table implementation (you could Google for one) is very likely to be dramatically faster *if* you don't have a lot of "churn": deleting hash table elements nearly as much as you insert new ones, with lookups interspersed. Closed addressing means the hash table keys are stored directly in buckets, and you get far better cache hits and much faster rehashing as the table size increases. If the values your integral keys map to are large (memory wise, as in `sizeof(My_Map::value_type)`), then do make sure the implementation's only storing pointers to them in the table itself, so the entire objects do not need to be copied during resizing.

Note: the above assumes the hash table really is causing your performance problems. If there's any doubt, do use a profiler to confirm that if you haven't already.