Template Class OrderedMinimalPerfectHash

Class Documentation

template<class K>
class OrderedMinimalPerfectHash

the function of Czech, Havas and Majewski that maps keys[ i ] to i

Public Types

using Key = K

the type of the keys

Public Functions

explicit OrderedMinimalPerfectHash(const std::vector<K> &keys, int r = 2, double c = 0, std::uint64_t seed = 1)

the function of the distinct keys, on r = 2 or 3 functions and c n vertices; c = 0 stands for 3 if r = 2 and for 1.25 if r = 3

Pre:

the keys are distinct (an audit) and fewer than 2^32, r = 2 with c > 2 or r = 3 with c > 1.23 (or c = 0)

Post:

( *this )( keys[ i ] ) == i for each i (an audit)

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

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

Pre:

size() >= 1

std::size_t size(void) const

the number n of keys

std::size_t vertices(void) const

the number m’ of vertices, i.e., of values of g

std::size_t trials(void) const

the graphs drawn by the build

Public Static Functions

static std::optional<std::vector<std::uint32_t>> labelAcyclicGraph(std::size_t m, const std::vector<std::size_t> &E, const std::vector<std::size_t> &h, std::size_t n)

Algorithms 8.1 and 8.2: g on the m vertices such that g[ u ] + g[ v ] = h[ e ] mod n on each edge e = ( E[ 2 e ] , E[ 2 e + 1 ] ), each tree labelled from its least vertex with g = 0; nothing if a visit finds an edge that it cannot satisfy (a cycle whose values do not add up)

Pre:

n >= 1, E has 2 h.size() vertices below m

Post:

every edge is satisfied, if a labelling is returned

static std::optional<std::vector<std::uint32_t>> labelByPeeling(std::size_t m, const std::vector<std::size_t> &E, int r, const std::vector<std::size_t> &h, std::size_t n)

g on the m vertices such that the g of the r vertices of each hyperedge e add up to h[ e ] mod n, by the reverse order of the peeling; nothing if the hypergraph has a 2-core (is not peelable)

Pre:

n >= 1, r >= 2, E has r h.size() vertices below m, those of an edge distinct

Post:

every edge is satisfied, if a labelling is returned