Aleph-w 3.0
A C++ Library for Data Structures and Algorithms
Loading...
Searching...
No Matches
OhashCommon< HashTbl, Key > Class Template Reference

CRTP mixin providing common operations for open addressing hash tables. More...

#include <hashDry.H>

Inheritance diagram for OhashCommon< HashTbl, Key >:
[legend]

Classes

class  Iterator
 Bidirectional iterator for traversing hash table entries. More...
 
struct  Stats
 Statistics about hash table performance. More...
 

Public Member Functions

constexpr float get_lower_alpha () const noexcept
 Returns the lower load factor threshold for automatic shrinking.
 
constexpr float get_upper_alpha () const noexcept
 Returns the upper load factor threshold for automatic growing.
 
void copy_from_table (const HashTbl &other)
 Copies all entries from another hash table.
 
void clean_table ()
 Removes all entries from the table without deallocating storage.
 
void check_resize_before_insert ()
 Checks if resize is needed before inserting and performs it.
 
Key * insert (const Key &key)
 Inserts a key into the hash table (copy version).
 
Key * insert (Key &&key)
 Inserts a key into the hash table (move version).
 
Key * search_or_insert (const Key &key)
 Searches for a key, inserting it if not found (copy version).
 
Key * search_or_insert (Key &&key)
 Searches for a key, inserting it if not found (move version).
 
std::pair< Key *, boolcontains_or_insert (const Key &key)
 Searches for a key, inserting if not found, with existence flag (copy version).
 
std::pair< Key *, boolcontains_or_insert (Key &&key)
 Searches for a key, inserting if not found, with existence flag (move version).
 
Key * append (const Key &key)
 Alias for insert() (copy version).
 
Key * append (Key &&key)
 Alias for insert() (move version).
 
constexpr bool has (const Key &key) const noexcept
 Checks if a key exists in the table.
 
constexpr bool contains (const Key &key) const noexcept
 Alias for has().
 
Key & find (const Key &key)
 Finds a key and returns a reference to it.
 
const Key & find (const Key &key) const
 Finds a key and returns a const reference to it.
 
const Key & operator[] (const Key &key) const
 Subscript operator for const access.
 
const Key & operator[] (const Key &key)
 Subscript operator with insertion semantics.
 
void remove_ptr (Key *key)
 Removes an entry by pointer.
 
size_t resize (size_t new_size)
 Resizes the hash table to a new capacity.
 
void rehash ()
 Rebuilds the hash table with the same capacity.
 
void empty ()
 Clears all entries and resets to default capacity.
 
constexpr size_t size () const noexcept
 Returns the number of entries in the table.
 
constexpr bool is_empty () const noexcept
 Checks if the table is empty.
 
constexpr size_t capacity () const noexcept
 Returns the current capacity of the table.
 
DynList< Key > keys () const
 Returns a list containing all keys in the table.
 
auto items () const
 Alias for keys().
 
void print_stats (const Stats &stats) const
 Prints statistics to standard output.
 
constexpr float current_alpha () const noexcept
 Returns the current load factor (alpha).
 

Private Member Functions

HashTblme ()
 Returns a pointer to the derived class (CRTP pattern).
 
const HashTblconst_me () const
 Returns a const pointer to the derived class (CRTP pattern).
 

Detailed Description

template<class HashTbl, typename Key>
class OhashCommon< HashTbl, Key >

CRTP mixin providing common operations for open addressing hash tables.

This template class provides shared implementation for hash table operations that are common between ODhashTable (double hashing) and OLhashTable (linear probing). It uses CRTP to achieve static polymorphism, avoiding virtual function overhead while enabling code reuse.

Template Parameters
HashTblThe derived hash table class (ODhashTable or OLhashTable). Must provide: allocate_bucket(), hard_allocate_bucket(), deallocate_bucket(), test_resize(), search(), table, len, N, lower_alpha, upper_alpha, with_resize, current_alpha(), Bucket.
KeyThe type of keys stored in the table.
Provided Operations:
Automatic Resizing:
When with_resize is enabled in the derived class, the table automatically:
  • Grows when it becomes nearly full (before insert would fail)
  • Shrinks when load factor drops below lower_alpha threshold
Thread Safety:
This class is NOT thread-safe. External synchronization is required for concurrent access.
See also
ODhashTable
OLhashTable

Definition at line 100 of file hashDry.H.

Member Function Documentation

◆ append() [1/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::append ( const Key &  key)
inline

Alias for insert() (copy version).

Provides STL-like naming for insert operations.

Parameters
keyThe key to append/insert.
Returns
Pointer to the inserted key, or nullptr on failure.
See also
insert(const Key &)

Definition at line 389 of file hashDry.H.

References OhashCommon< HashTbl, Key >::insert().

◆ append() [2/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::append ( Key &&  key)
inline

Alias for insert() (move version).

Provides STL-like naming for insert operations.

Parameters
keyThe key to append/insert (will be moved from).
Returns
Pointer to the inserted key, or nullptr on failure.
See also
insert(Key &&)

Definition at line 402 of file hashDry.H.

References OhashCommon< HashTbl, Key >::insert().

◆ capacity()

template<class HashTbl , typename Key >
constexpr size_t OhashCommon< HashTbl, Key >::capacity ( ) const
inlineconstexprnoexcept

Returns the current capacity of the table.

Returns
The number of buckets in the internal array.

Definition at line 622 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

Referenced by demo_odhash(), and OhashCommon< HashTbl, Key >::print_stats().

◆ check_resize_before_insert()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::check_resize_before_insert ( )
inline

Checks if resize is needed before inserting and performs it.

Called before each insert operation to ensure there is at least one empty bucket available (required as a sentinel for probing). If automatic resizing is enabled and the table is nearly full, doubles the table capacity.

Definition at line 180 of file hashDry.H.

References Aleph::maps(), OhashCommon< HashTbl, Key >::me(), N, and Primes::next_prime().

Referenced by OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::contains_or_insert(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::insert(), OhashCommon< HashTbl, Key >::search_or_insert(), and OhashCommon< HashTbl, Key >::search_or_insert().

◆ clean_table()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::clean_table ( )
inline

Removes all entries from the table without deallocating storage.

Resets all buckets to their initial empty state and sets the entry count to zero. The table capacity remains unchanged.

Postcondition
size() == 0
capacity() unchanged

Definition at line 166 of file hashDry.H.

References OhashCommon< HashTbl, Key >::me().

Referenced by Aleph::ODhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::operator=().

◆ const_me()

◆ contains()

template<class HashTbl , typename Key >
constexpr bool OhashCommon< HashTbl, Key >::contains ( const Key &  key) const
inlineconstexprnoexcept

Alias for has().

Parameters
keyThe key to search for.
Returns
true if the key exists, false otherwise.
See also
has()

Definition at line 425 of file hashDry.H.

References OhashCommon< HashTbl, Key >::has().

◆ contains_or_insert() [1/2]

template<class HashTbl , typename Key >
std::pair< Key *, bool > OhashCommon< HashTbl, Key >::contains_or_insert ( const Key &  key)
inline

Searches for a key, inserting if not found, with existence flag (copy version).

Similar to search_or_insert(), but also indicates whether the key was already present in the table.

Parameters
keyThe key to search for or insert.
Returns
A pair containing:
  • first: Pointer to the key (existing or newly inserted), or nullptr on failure.
  • second: true if the key was already present, false if inserted.
Note
This function is marked [[nodiscard]].
Example:
auto [ptr, existed] = table.contains_or_insert(key);
if (ptr) {
if (existed) std::cout << "Key already existed\n";
else std::cout << "Key was inserted\n";
}
DynList< T > maps(const C &c, Op op)
Classic map operation.
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 332 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().

◆ contains_or_insert() [2/2]

template<class HashTbl , typename Key >
std::pair< Key *, bool > OhashCommon< HashTbl, Key >::contains_or_insert ( Key &&  key)
inline

Searches for a key, inserting if not found, with existence flag (move version).

Similar to search_or_insert(), but also indicates whether the key was already present in the table.

Parameters
keyThe key to search for or insert (moved from on insert).
Returns
A pair containing:
  • first: Pointer to the key (existing or newly inserted), or nullptr on failure.
  • second: true if the key was already present, false if inserted.
Note
This function is marked [[nodiscard]].
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 365 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().

◆ copy_from_table()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::copy_from_table ( const HashTbl other)
inline

Copies all entries from another hash table.

Copies all BUSY entries from the source table to this table. This table must be empty and have sufficient capacity.

Parameters
otherSource hash table to copy from.
Precondition
This table must be empty (N == 0).
This table must have capacity >= other.N.
Postcondition
This table contains all entries from other.

Definition at line 143 of file hashDry.H.

References Aleph::DynList< T >::insert(), Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.

Referenced by Aleph::ODhashTable< Key, Cmp >::ODhashTable(), Aleph::OLhashTable< Key, Cmp >::OLhashTable(), Aleph::ODhashTable< Key, Cmp >::operator=(), and Aleph::OLhashTable< Key, Cmp >::operator=().

◆ current_alpha()

template<class HashTbl , typename Key >
constexpr float OhashCommon< HashTbl, Key >::current_alpha ( ) const
inlineconstexprnoexcept

Returns the current load factor (alpha).

The load factor is the ratio of stored entries to table capacity. A higher load factor means more efficient memory usage but potentially longer probe sequences.

Returns
The load factor as N/capacity.

Definition at line 959 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

Referenced by OhashCommon< HashTbl, Key >::remove_ptr().

◆ empty()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::empty ( )
inline

Clears all entries and resets to default capacity.

Removes all entries and resets the table to its default initial capacity (Primes::DefaultPrime).

Postcondition
size() == 0
capacity() == Primes::DefaultPrime

Definition at line 601 of file hashDry.H.

References Primes::DefaultPrime, and OhashCommon< HashTbl, Key >::me().

◆ find() [1/2]

template<class HashTbl , typename Key >
Key & OhashCommon< HashTbl, Key >::find ( const Key &  key)
inline

Finds a key and returns a reference to it.

Searches for the key and returns a reference to it. If the key is not found, throws an exception.

Parameters
keyThe key to find.
Returns
Reference to the stored key.
Exceptions
std::domain_errorIf the key is not found.
Complexity: O(1) average, O(n) worst case.

Definition at line 438 of file hashDry.H.

References ah_domain_error_if, and OhashCommon< HashTbl, Key >::me().

Referenced by OhashCommon< HashTbl, Key >::find(), and OhashCommon< HashTbl, Key >::operator[]().

◆ find() [2/2]

template<class HashTbl , typename Key >
const Key & OhashCommon< HashTbl, Key >::find ( const Key &  key) const
inline

Finds a key and returns a const reference to it.

Const version of find().

Parameters
keyThe key to find.
Returns
Const reference to the stored key.
Exceptions
std::domain_errorIf the key is not found.
See also
find(const Key &)

Definition at line 456 of file hashDry.H.

References OhashCommon< HashTbl, Key >::find().

◆ get_lower_alpha()

template<class HashTbl , typename Key >
constexpr float OhashCommon< HashTbl, Key >::get_lower_alpha ( ) const
inlineconstexprnoexcept

Returns the lower load factor threshold for automatic shrinking.

When automatic resizing is enabled and the load factor drops below this value after a removal, the table shrinks.

Returns
The lower alpha threshold (typically 0.25).

Definition at line 121 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

◆ get_upper_alpha()

template<class HashTbl , typename Key >
constexpr float OhashCommon< HashTbl, Key >::get_upper_alpha ( ) const
inlineconstexprnoexcept

Returns the upper load factor threshold for automatic growing.

When automatic resizing is enabled and the load factor would exceed this value, the table grows before insertion.

Returns
The upper alpha threshold (typically 0.75).

Definition at line 130 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

◆ has()

template<class HashTbl , typename Key >
constexpr bool OhashCommon< HashTbl, Key >::has ( const Key &  key) const
inlineconstexprnoexcept

Checks if a key exists in the table.

Parameters
keyThe key to search for.
Returns
true if the key exists, false otherwise.
Complexity: O(1) average, O(n) worst case.

Definition at line 414 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

Referenced by OhashCommon< HashTbl, Key >::contains().

◆ insert() [1/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::insert ( const Key &  key)
inline

Inserts a key into the hash table (copy version).

Attempts to insert a copy of the key. If the key already exists, the insertion fails and nullptr is returned.

Parameters
keyThe key to insert.
Returns
Pointer to the inserted key, or nullptr if key already exists or allocation failed.
Note
This function is marked [[nodiscard]] - check the return value to detect insertion failures.
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 203 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), and OhashCommon< HashTbl, Key >::me().

Referenced by OhashCommon< HashTbl, Key >::append(), OhashCommon< HashTbl, Key >::append(), demo_odhash(), demo_performance(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ insert() [2/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::insert ( Key &&  key)
inline

Inserts a key into the hash table (move version).

Attempts to insert a key using move semantics. If the key already exists, the insertion fails and nullptr is returned.

Parameters
keyThe key to insert (will be moved from on success).
Returns
Pointer to the inserted key, or nullptr if key already exists or allocation failed.
Note
This function is marked [[nodiscard]] - check the return value to detect insertion failures.
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 231 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), and OhashCommon< HashTbl, Key >::me().

◆ is_empty()

template<class HashTbl , typename Key >
constexpr bool OhashCommon< HashTbl, Key >::is_empty ( ) const
inlineconstexprnoexcept

Checks if the table is empty.

Returns
true if size() == 0, false otherwise.

Definition at line 617 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

◆ items()

template<class HashTbl , typename Key >
auto OhashCommon< HashTbl, Key >::items ( ) const
inline

Alias for keys().

Returns
DynList<Key> containing all keys.
See also
keys()

Definition at line 906 of file hashDry.H.

References OhashCommon< HashTbl, Key >::keys().

◆ keys()

template<class HashTbl , typename Key >
DynList< Key > OhashCommon< HashTbl, Key >::keys ( ) const
inline

Returns a list containing all keys in the table.

Creates and returns a DynList containing copies of all keys stored in the hash table.

Returns
DynList<Key> containing all keys.
Complexity: O(n) where n is the number of entries.

Definition at line 897 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me(), and Aleph::maps().

Referenced by OhashCommon< HashTbl, Key >::items().

◆ me()

◆ operator[]() [1/2]

template<class HashTbl , typename Key >
const Key & OhashCommon< HashTbl, Key >::operator[] ( const Key &  key)
inline

Subscript operator with insertion semantics.

Returns a reference to the key. If the key doesn't exist, it is inserted first.

Parameters
keyThe key to access or insert.
Returns
Reference to the stored key.

Definition at line 482 of file hashDry.H.

References OhashCommon< HashTbl, Key >::search_or_insert().

◆ operator[]() [2/2]

template<class HashTbl , typename Key >
const Key & OhashCommon< HashTbl, Key >::operator[] ( const Key &  key) const
inline

Subscript operator for const access.

Returns a const reference to the key. Equivalent to find().

Parameters
keyThe key to access.
Returns
Const reference to the stored key.
Exceptions
std::domain_errorIf the key is not found.

Definition at line 469 of file hashDry.H.

References OhashCommon< HashTbl, Key >::find().

◆ print_stats()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::print_stats ( const Stats stats) const
inline

Prints statistics to standard output.

Displays formatted statistics including capacity, size, bucket states, load factor, and probe length distribution.

Parameters
statsStatistics object to print.

Definition at line 938 of file hashDry.H.

References OhashCommon< HashTbl, Key >::capacity(), OhashCommon< HashTbl, Key >::const_me(), OhashCommon< HashTbl, Key >::Stats::lens, OhashCommon< HashTbl, Key >::Stats::max_len, OhashCommon< HashTbl, Key >::Stats::num_busy, OhashCommon< HashTbl, Key >::Stats::num_deleted, OhashCommon< HashTbl, Key >::Stats::num_empty, OhashCommon< HashTbl, Key >::size(), and Aleph::DynArray< T >::size().

◆ rehash()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::rehash ( )
inline

Rebuilds the hash table with the same capacity.

Creates a new internal table with the same capacity and re-inserts all entries. This can help improve performance after many deletions by eliminating deleted bucket markers.

Complexity: O(n) where n is the number of entries.

Definition at line 569 of file hashDry.H.

References Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.

◆ remove_ptr()

template<class HashTbl , typename Key >
void OhashCommon< HashTbl, Key >::remove_ptr ( Key *  key)
inline

Removes an entry by pointer.

Removes the entry pointed to by the given pointer. The pointer must have been obtained from this table (via insert, search, etc.).

If automatic resizing is enabled and the load factor drops below the lower threshold, the table is shrunk.

Parameters
keyPointer to the key to remove (must be in this table).
Precondition
key must point to a valid entry in this table.
Postcondition
The entry is removed and size() decreases by 1.
Complexity: O(1) amortized.

Definition at line 502 of file hashDry.H.

References OhashCommon< HashTbl, Key >::current_alpha(), Aleph::maps(), OhashCommon< HashTbl, Key >::me(), Primes::next_prime(), and OhashCommon< HashTbl, Key >::resize().

◆ resize()

template<class HashTbl , typename Key >
size_t OhashCommon< HashTbl, Key >::resize ( size_t  new_size)
inline

Resizes the hash table to a new capacity.

Changes the table capacity to the specified size and rehashes all entries. The new size must be large enough to hold all current entries plus at least one empty sentinel bucket.

Parameters
new_sizeThe new capacity (should be a prime number).
Returns
The actual new capacity (may differ from requested if new_size was 0 or equal to current capacity).
Exceptions
std::overflow_errorIf new_size is too small for current entries.
Complexity: O(n) where n is the number of entries.

Definition at line 524 of file hashDry.H.

References ah_overflow_error_if, Aleph::maps(), OhashCommon< HashTbl, Key >::me(), and N.

Referenced by OhashCommon< HashTbl, Key >::remove_ptr().

◆ search_or_insert() [1/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::search_or_insert ( const Key &  key)
inline

Searches for a key, inserting it if not found (copy version).

If the key exists, returns a pointer to it. Otherwise, inserts a copy of the key and returns a pointer to the newly inserted key.

Parameters
keyThe key to search for or insert.
Returns
Pointer to the existing or newly inserted key, or nullptr if allocation failed.
Note
This function is marked [[nodiscard]] - the return value indicates success/failure and provides the key pointer.
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 259 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().

Referenced by OhashCommon< HashTbl, Key >::operator[]().

◆ search_or_insert() [2/2]

template<class HashTbl , typename Key >
Key * OhashCommon< HashTbl, Key >::search_or_insert ( Key &&  key)
inline

Searches for a key, inserting it if not found (move version).

If the key exists, returns a pointer to it. Otherwise, inserts the key using move semantics and returns a pointer to the newly inserted key.

Parameters
keyThe key to search for or insert (moved from on insert).
Returns
Pointer to the existing or newly inserted key, or nullptr if allocation failed.
Note
This function is marked [[nodiscard]] - the return value indicates success/failure and provides the key pointer.
Complexity:
  • Average case: O(1) amortized
  • Worst case: O(n) when rehashing is triggered

Definition at line 291 of file hashDry.H.

References OhashCommon< HashTbl, Key >::check_resize_before_insert(), Aleph::maps(), and OhashCommon< HashTbl, Key >::me().

◆ size()

template<class HashTbl , typename Key >
constexpr size_t OhashCommon< HashTbl, Key >::size ( ) const
inlineconstexprnoexcept

Returns the number of entries in the table.

Returns
The number of stored keys.

Definition at line 612 of file hashDry.H.

References OhashCommon< HashTbl, Key >::const_me().

Referenced by demo_odhash(), demo_performance(), OhashCommon< HashTbl, Key >::print_stats(), TEST(), TEST(), and TEST().


The documentation for this class was generated from the following file: