What bucket_count value should I use if I know the intended number of map keys?

Question

I'm creating an std::unordered_map which I will immediately proceed to populate with n key-value pairs - and I know n. After that no more elements will be added - I will only be performing lookups.

What, therefore, should I pass as bucket_count to the constructor?

Notes:

• I know it's not terribly critical and I could simply not specify anything and it will work.
• This is related to, but not a dupe of, What should I pass to unordered_map's bucket count argument if I just want to specify a hash function?)
• If it helps your answer, you may assume I want to have a load factor between f_1 and f_2 (known in advance).
• I'm using the default hash function, and I don't know what the input is like, but it's unlikely to be adversarial to the hashing..

Answer 1

Given the fact you have a range for your load factor, the only missing information is the collision rate. You can simply use nb_buckets = n / f_2 and you will be sure to get a load factor less than or equal to f_2. Ensuring correctness about f_1 requires data about the collision rate.

Answer 2

According to n4296 in 23.5.4.2 [unord.map.cnstr] (this is the final draft of C++14) by default the max_load_factor for an unordered_map is 1.0, so you could just set the bucket_count to n.

There is obviously a space-time trade-off between increasing the bucket count for improved speed and decreasing it (and raising the max load factor) for improved space.

I would either not worry about it, or if it is a large map, set the bucket count to n. Then you can worry about optimizing when profiling shows you have a problem.

If you know the range of load factors you want, then you just set the bucket count to std::ceil(n/(std::max(f_1,f_2)), (and set the load factor before you fill the map).