Re: number of calls to hash function in unordered_set

[Jonathan Wakely <jwakely dot gcc at gmail dot com>]

On 11 June 2018 at 17:24, Frank Tetzel wrote:
> Hi,
>
> can anybody give me a reasonable explanation why the hash function for
> a simple unordered_set is called twice as much as I would expect.
>
> Example:
>
>
> #include <iostream>
> #include <unordered_set>
>
> struct MyHash{
>         static int numberOfCalls;
>
>         size_t operator()(int i) const noexcept{
>                 ++numberOfCalls;
>                 //return std::hash<int>{}(i);
>                 return i;
>         }
> };
> int MyHash::numberOfCalls = 0;
>
> int main(){
>         std::unordered_set<int,MyHash> set;
>
>         std::cout << MyHash::numberOfCalls << '\n';
>         set.reserve(1024);
>         std::cout << MyHash::numberOfCalls << '\n';
>         for(int i=0; i<1024; ++i){
>                 set.emplace(i);
>         }
>         std::cout << MyHash::numberOfCalls << '\n';
>
>         return 0;
> }
>
>
>
>
> output:
> 0
> 0
> 2047
>
> It seems to always be (inserted_elements * 2) - 1.
> When adding 2 elements, it hashes 3 times. When adding 1 element, it
> only hashes once. What is happening here? Why is the hash calculated
> twice? What is so special about the last or first element?

The code is free for anyone to inspect. You can use a debugger to set
a breakpoint in your hash function and see when it's called.