Template Class FingerprintPerfectHash

Class Documentation

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

a minimal perfect hash function of a static set of keys by levels of fingerprints

Public Types

using Key = T

the type of the keys

Public Functions

explicit FingerprintPerfectHash(const std::vector<T> &keys, double gamma = 2, std::uint64_t seed = 1, H h = H())

the function of the distinct keys, with gamma bits per key in each level

Pre:

the keys are distinct (an audit) and fewer than 2^32, gamma >= 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 levels, their ranks and their sizes

std::size_t levels(void) const

the number of levels