IOSS 2.0

Public Member Functions | Private Attributes | List of all members
tsl::hh::prime_growth_policy Class Reference

`#include <hopscotch_growth_policy.h>`

## Public Member Functions
| prime_growth_policy (std::size_t &min_bucket_count_in_out)
std::size_t | bucket_for_hash (std::size_t hash) const noexcept
std::size_t | next_bucket_count () const
std::size_t | max_bucket_count () const
void | clear () noexcept

## Private Attributes
unsigned int | m_iprime

## Detailed Description

Grow the hash table by using prime numbers as bucket count. Slower than tsl::hh::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 environement.

## Constructor & Destructor Documentation

## ◆ prime_growth_policy()

tsl::hh::prime_growth_policy::prime_growth_policy | ( | std::size_t & | min_bucket_count_in_out | ) |
| inline explicit

## Member Function Documentation

## ◆ bucket_for_hash()

std::size_t tsl::hh::prime_growth_policy::bucket_for_hash | ( | std::size_t | hash | ) | const
| inline noexcept

## ◆ clear()

void tsl::hh::prime_growth_policy::clear | ( |  | ) |
| inline noexcept

## ◆ max_bucket_count()

std::size_t tsl::hh::prime_growth_policy::max_bucket_count | ( |  | ) | const
| inline

## ◆ next_bucket_count()

std::size_t tsl::hh::prime_growth_policy::next_bucket_count | ( |  | ) | const
| inline

## Member Data Documentation

## ◆ m_iprime

unsigned int tsl::hh::prime_growth_policy::m_iprime
| private

The documentation for this class was generated from the following file:

- src/hash/hopscotch_growth_policy.h