Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

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.

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?

like image 302
zneak Avatar asked Jan 06 '13 04:01

zneak


People also ask

What is bucket in unordered_ set?

unordered_set bucket() function in C++ STL The bucket is a slot in the unordered_set's internal hash table where elements are stored. Note: Buckets in unordered_set are numbered from 0 to n-1, where n is the total number of buckets.

What is a hash map in c++?

Hash table (also, hash map) is a data structure that basically maps keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the corresponding value can be found.

How does unordered_ map work in c++?

The associated container unordered_map in c++ stores elements that are generated by combining a key value and a mapped value. The mapped value is the material associated with the key, and the key value is used to uniquely identify the element. Both the key and the value may be of any predefined or custom kind.

Is unordered_map a hash table?

Unordered_map IS a hash table actually. You may want to use a better example as, as is the second insert will fail since it has the same key.


1 Answers

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.

like image 64
Jonathan Wakely Avatar answered Sep 29 '22 02:09

Jonathan Wakely