Class Probing

Class Documentation

class Probing

a sequence of inspection H( k , i ) of an OpenHashTable

Public Types

enum class Kind

Values:

enumerator LINEAR
enumerator QUADRATIC
enumerator DOUBLE
enumerator TRIANGULAR
enumerator RANDOM
using Step = std::function<std::size_t(std::size_t)>

the second function of the double hashing, of the hash h( k )

Public Functions

Kind kind(void) const
std::size_t at(std::size_t h, std::size_t i, std::size_t m) const

the place H( k , i ) in a table of size m, from h = h( k )

Pre:

m > 0

Post:

the result is below m

std::size_t stride(std::size_t h, std::size_t m) const

the constant difference H( k , i + 1 ) - H( k , i ) mod m of the linear inspection and of the double hashing, so that a scan adds it instead of computing H( k , i ); 0 for the other inspections

Pre:

m > 0

bool works(std::size_t m) const

whether the sequence can work with a table of size m

void check(std::size_t m) const
Pre:

works( m )

Public Static Functions

static Probing linear(long delta = 1)

H( k , i ) = ( H0( k ) + delta i ) mod m.

static Probing quadratic(long c1, long c2)

H( k , i ) = ( H0( k ) + c1 i + c2 i^2 ) mod m, m prime.

static Probing double_hashing(void)

H( k , i ) = ( H0( k ) + Hdelta( k ) i ) mod m.

static Probing double_hashing(Step g)

H( k , i ) = ( H0( k ) + Hdelta( k ) i ) mod m, the step from g( h( k ) )

static Probing triangular(void)

H( k , i ) = ( H0( k ) + i ( i + 1 ) / 2 ) mod m, m a power of two.

static Probing pseudo_random(unsigned long seed = 1)

H( k , i ) = ( H0( k ) + p_i ) mod m, p a random permutation of 0 , … , m - 1 with p_0 = 0, drawn from the seed for each m.

static std::size_t step(std::size_t h, std::size_t m)

the step Hdelta( k ) of the double hashing, coprime with m when m is prime or a power of two

Pre:

m > 0