Template Class BrentHashTable

• Defined in File KnuthHashing.h

Nested Relationships

Nested Types

• Struct BrentHashTable::Places

Class Documentation

template<class K, class V, class H = std::hash<K>>
class BrentHashTable

a hash table with double hashing and the insertion of Brent

Public Types

using value_type = std::pair<K, V>

using size_type = std::size_t

using difference_type = std::ptrdiff_t

using reference = const std::pair<K, V>&

using const_reference = const std::pair<K, V>&

using const_iterator = SlotIterator<BrentHashTable, Places>

using iterator = const_iterator

Public Functions

explicit BrentHashTable(std::size_t m, H h = H())

a table of m places

Pre:

m >= 2 is prime

std::optional<V> lookup(const K &k) const

void insert(const K &k, const V &v)

associates v to k

Pre:

k is there, or the table is not full

Post:

k has the value v

std::size_t size(void) const

std::size_t probes(void) const

the places examined by the last lookup()

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 table, 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::pair<K, V> &read(const auto &o, std::size_t i)