Perfect hash map using displacement-based perfect hashing for immutable datasets.
More...
|
| using | key_type = TKey |
| | Type alias for key type.
|
| using | mapped_type = TValue |
| | Type alias for mapped value type.
|
| using | value_type = std::pair<TKey, TValue> |
| | Type alias for key-value pair type.
|
| using | hasher = Hasher |
| | Type alias for hasher type.
|
| using | key_equal = KeyEqual |
| | Type alias for key equality comparator.
|
| using | hash_type = HashType |
| | Type alias for hash type (uint32_t or uint64_t).
|
| using | seed_type = std::make_signed_t<hash_type> |
| | Type alias for signed seed type (used internally for displacement seeds).
|
| using | size_type = size_t |
| | Type alias for size type.
|
| using | difference_type = std::ptrdiff_t |
| | Type alias for difference type.
|
| using | iterator = Iterator |
| | Primary iterator class.
|
| using | const_iterator = Iterator |
| | Type alias for const iterator (same as iterator since map is immutable).
|
| using | ConstIterator = Iterator |
| | Alias for const iterator.
|
|
| | PerfectHashMap (std::vector< std::pair< TKey, TValue > > &&items) |
| | Constructs a perfect hash map from a vector of key-value pairs.
|
| | PerfectHashMap ()=default |
| | Default constructor creates an empty map.
|
|
| PerfectHashMap (const PerfectHashMap &)=default |
| | Copy constructor.
|
|
| PerfectHashMap (PerfectHashMap &&) noexcept=default |
| | Move constructor.
|
|
| ~PerfectHashMap ()=default |
| | Destructor.
|
| PerfectHashMap & | operator= (const PerfectHashMap &)=default |
| | Copy assignment operator.
|
| PerfectHashMap & | operator= (PerfectHashMap &&) noexcept=default |
| | Move assignment operator.
|
| bool | operator== (const PerfectHashMap &other) const noexcept |
| | Equality comparison operator.
|
| bool | operator!= (const PerfectHashMap &other) const noexcept |
| | Inequality comparison operator.
|
| template<typename K> |
| const TValue & | at (const K &key) const |
| | Access element with bounds checking.
|
| template<typename K> |
| bool | contains (const K &key) const noexcept |
| | Check if a key exists in the map.
|
| template<typename K> |
| const TValue * | find (const K &key) const noexcept |
| | Fast lookup with heterogeneous key types (C++ idiom: pointer return).
|
| size_type | size () const noexcept |
| | Get the total size of the hash table.
|
| size_type | count () const noexcept |
| | Get the number of elements in the map.
|
| bool | isEmpty () const noexcept |
| | Check if the map is empty.
|
| Iterator | begin () const noexcept |
| | Get iterator to beginning of occupied slots.
|
| Iterator | end () const noexcept |
| | Get iterator to end (past last occupied slot).
|
| ConstIterator | cbegin () const noexcept |
| | Get const iterator to beginning of occupied slots (explicit const).
|
| ConstIterator | cend () const noexcept |
| | Get const iterator to end (explicit const).
|
| hasher | hash_function () const |
| | Get the hash function object.
|
| key_equal | key_eq () const |
| | Get the key equality comparison function object.
|
template<typename TKey, typename TValue, hashing::Hash32or64 HashType = uint32_t, HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ), typename Hasher = hashing::Hasher<HashType, Seed>, typename KeyEqual = std::equal_to<>>
class nfx::containers::PerfectHashMap< TKey, TValue, HashType, Seed, Hasher, KeyEqual >
Perfect hash map using displacement-based perfect hashing for immutable datasets.
- Template Parameters
-
| TKey | Key type (supports heterogeneous lookup for compatible types) |
| TValue | Mapped value type |
| HashType | Hash type - either uint32_t or uint64_t (default: uint32_t) |
| Seed | Hash seed value for initialization (default: FNV offset basis for HashType) |
| Hasher | Hash functor type (default: hashing::Hasher<HashType, Seed>) |
| KeyEqual | Key equality comparator (default: std::equal_to<> for transparent comparison) |
Provides O(1) guaranteed lookups with zero collision overhead using displacement-based perfect hashing. The algorithm creates a perfect hash function where each key maps to a unique table position with no collisions, enabling true constant-time lookups.
Construction uses bucket-based displacement with seed mixing to resolve collisions:
- Keys are distributed into buckets by their hash value
- Buckets are processed largest-first to minimize displacement attempts
- Each multi-item bucket finds a unique seed that displaces items to empty slots
- Single-item buckets are placed directly without displacement
Memory overhead: Table size is 2x the number of keys for efficient seed finding. This trade-off provides guaranteed O(1) lookups with simple, maintainable code.
- Note
- The map is immutable after construction. Use HashMap for mutable scenarios.
Definition at line 85 of file PerfectHashMap.h.
template<typename TKey, typename TValue, hashing::Hash32or64 HashType = uint32_t, HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ), typename Hasher = hashing::Hasher<HashType, Seed>, typename KeyEqual = std::equal_to<>>
Constructs a perfect hash map from a vector of key-value pairs.
- Parameters
-
| items | Vector of key-value pairs (moved into the map) |
- Exceptions
-
| std::invalid_argument | if duplicate keys are detected in items |
Uses displacement-based perfect hashing to build a collision-free hash table. Construction is O(n) expected time. The resulting map is immutable.
template<typename TKey, typename TValue, hashing::Hash32or64 HashType = uint32_t, HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ), typename Hasher = hashing::Hasher<HashType, Seed>, typename KeyEqual = std::equal_to<>>
Default constructor creates an empty map.
Creates an empty PerfectHashMap with no elements. Use the explicit constructor with a vector of key-value pairs to build a functional perfect hash map.
template<typename TKey, typename TValue, hashing::Hash32or64 HashType = uint32_t, HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ), typename Hasher = hashing::Hasher<HashType, Seed>, typename KeyEqual = std::equal_to<>>
template<typename K>
Access element with bounds checking.
- Template Parameters
-
| K | Key type (supports heterogeneous lookup for compatible types) |
- Parameters
-
- Returns
- Const reference to the mapped value
- Exceptions
-
| std::out_of_range | if key is not found in the map |
Provides checked access to elements. For unchecked access, use find(). Supports heterogeneous lookup (e.g., string_view for string keys).
template<typename TKey, typename TValue, hashing::Hash32or64 HashType = uint32_t, HashType Seed = ( sizeof( HashType ) == 4 ? hashing::constants::FNV_OFFSET_BASIS_32 : hashing::constants::FNV_OFFSET_BASIS_64 ), typename Hasher = hashing::Hasher<HashType, Seed>, typename KeyEqual = std::equal_to<>>
template<typename K>
Check if a key exists in the map.
- Template Parameters
-
| K | Key type (supports heterogeneous lookup for compatible types) |
- Parameters
-
- Returns
- true if key exists in the map, false otherwise
O(1) guaranteed lookup time using perfect hashing. Supports heterogeneous lookup (e.g., string_view for string keys).
- Note
- This function is marked [[nodiscard]] - the return value should not be ignored
1.15.0