Class PerfectHashTable

• Defined in File PerfectHashing.h

Nested Relationships

Nested Types

• Struct PerfectHashTable::Bucket

• Struct PerfectHashTable::Places

Class Documentation

class PerfectHashTable

a static SET of integers on the two-level perfect hashing

Public Types

using Key = std::uint64_t

the type of the keys

using value_type = std::uint64_t

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const std::uint64_t&

using const_reference = const std::uint64_t&

using const_iterator = SlotIterator<PerfectHashTable, Places>

using iterator = const_iterator

Public Functions

explicit PerfectHashTable(const std::vector<std::uint64_t> &S, std::uint64_t seed = 1)

the table of the keys of S

Pre:

the keys are distinct (an audit) and below 2^61 - 1

Post:

each key of S is there (an audit), and sum_j n_j^2 < 2 n

bool contains(std::uint64_t k) const

any k, in O( 1 ) time in the worst case

std::size_t size(void) const

the number of keys

std::size_t space(void) const

the places of the second level, sum_j n_j^2

std::size_t trials(void) const

the functions drawn by the build, of both levels

inline const_iterator begin(void) const

inline const_iterator end(void) const

inline const_iterator cbegin(void) const

inline const_iterator cend(void) const

struct Places

the places of the second level, for SlotIterator

Public Static Functions

static inline std::size_t size(const auto &o)

static inline bool occupied(const auto &o, std::size_t i)

static inline const std::uint64_t &read(const auto &o, std::size_t i)