Template Class MinimalPerfectHash

• Defined in File MinimalPerfectHash.h

Class Documentation

template<class T, class H = DefaultHash<T>>
class MinimalPerfectHash

a minimal perfect hash function of a static set of keys by pilots

Public Types

using Key = T

the type of the keys

Public Functions

explicit MinimalPerfectHash(const std::vector<T> &keys, double lambda = 5, double alpha = 0.99, std::uint64_t seed = 1, H h = H())

the function of the distinct keys, with lambda keys per bucket on average and the load alpha of the table

Pre:

the keys are distinct (an audit) and fewer than 2^32, lambda >= 1 and 0.5 <= alpha <= 1

Post:

the keys are mapped onto { 0 , … , n - 1 } (an audit)

std::size_t operator()(const T &k) const

the value of k, in [ 0 , n ); some value in it for a key out of S

Pre:

size() >= 1

std::size_t size(void) const

the number n of keys

bool empty(void) const

std::size_t bits(void) const

the bits of the function: the pilots, the free places and the sizes

std::size_t buckets(void) const

the number of buckets

std::size_t trials(void) const

the seeds drawn by the build