class tsl::rh::prime_growth_policy

Overview

Grow the hash table by using prime numbers as bucket count. Slower than tsl::rh::power_of_two_growth_policy in general but will probably distribute the values around better in the buckets with a poor hash function.

To allow the compiler to optimize the modulo operation, a lookup table is used with constant primes numbers.

With a switch the code would look like:

switch(iprime) { // iprime is the current prime of the hash table
    case 0: hash % 5ul;
            break;
    case 1: hash % 17ul;
            break;
    case 2: hash % 29ul;
            break;
    ...
}

Due to the constant variable in the modulo the compiler is able to optimize the operation by a series of multiplications, substractions and shifts.

The ‘hash % 5’ could become something like ‘hash - (hash * 0xCCCCCCCD) >> 34)

• 5’ in a 64 bits environment.

#include <robin_growth_policy.h>

class prime_growth_policy
{
public:
    // construction

    prime_growth_policy(std::size_t& min_bucket_count_in_out);

    // methods

    std::size_t bucket_for_hash(std::size_t hash) const;
    std::size_t next_bucket_count() const;
    std::size_t max_bucket_count() const;
    void clear();
};