zneak zneak - 1 month ago 7
C++ Question

What should I pass to unordered_map's bucket count argument if I just want to specify a hash function?

C++11's

unordered_map
's default constructor looks like this:

explicit unordered_map( size_type bucket_count = /*implementation-defined*/,
const hasher& hash = hasher(),
const key_equal& equal = key_equal(),
const allocator_type& alloc = allocator_type() );


I want to create an
unordered_map
with a custom hasher function, but it's the second argument to the constructor. I know the basics of hash maps and I could (probably) implement an awful one, but from what I remember, some bucket counts are better than others, and that's somehow related to prime numbers.

What bucket count should I use? Is there a magic value I can use to tell the container to decide for itself? Otherwise, is there a heuristic I can use to guesstimate a good bucket number based on something like the number of keys I expect my map to contain? Should I even care?

Answer

I wouldn't worry too much about it.

The container guarantees the bucket count will be at least the value you provide, i.e. it will increase it if needed. You could pass zero as the bucket count and the implementation will either do something like std::max(count, 10) and override the zero value, or it will just rehash on the first insertion.

Another alternative would be to copy the value from a default-constructed object:

H hasher;
unordered_map<K,T,H,P> m{ unordered_map<K,T,H,P>{}.bucket_count(), hasher };

This will set the bucket count to whatever the implementation's default is (but does require the H hash function type to be DefaultConstructible.)

FWIW GCC's unordered_map uses 10 as the default for the constructor you showed (so that's probably a reasonable default too) and uses 0 for the constructors taking a pair of iterators or an initializer_list.

Comments