Dynamic hash table mapping keys to records with separate chaining. More...

#include <tpl_dynLhash.H>

Inheritance diagram for Aleph::DynLhashTable< Key, Record, Cmp >:

Collaboration diagram for Aleph::DynLhashTable< Key, Record, Cmp >:

Classes
struct	DLBucket

class	DLProxy

Public Types
using	Hash_Fct_Ptr = typename DynLhashTable< Key, Record >::Hash_Fct_Ptr
	The type of hash function pointer.

Public Types inherited from Aleph::LhashTableVtl< Key, Cmp >
using	Base = GenLhashTable< Key, LhashBucketVtl< Key >, Cmp >

Public Types inherited from Aleph::GenLhashTable< Key, BucketType, Cmp >
using	Bucket = BucketType

using	Hash_Fct = std::function< size_t(const Key &)>

using	Hash_Fct_Ptr = size_t(*)(const Key &)

using	Key_Type = Key

using	Item_Type = Key

Public Member Functions
void	swap (DynLhashTable &table) noexcept
	Swap contents with another table.

	DynLhashTable (size_t len=DefaultPrime, Hash_Fct_Ptr hash_fct=dft_hash_fct< Key >)
	Construct a dynamic hash table.

	DynLhashTable (const DynLhashTable &table)
	Copy constructor.

	DynLhashTable (DynLhashTable &&table) noexcept
	Move constructor.

DynLhashTable &	operator= (const DynLhashTable &table)
	Copy assignment operator.

DynLhashTable &	operator= (DynLhashTable &&table) noexcept
	Move assignment operator.

Record *	insert (const Key &key, const Record &record)
	Insert a key-record pair into the table.

Record *	insert (const Key &key, Record &&record=Record())
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Record *	insert (Key &&key, const Record &record)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Record *	insert (Key &&key, Record &&record)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Record *	search (const Key &key)
	Search for a key in the table.

void	remove (Record *record)
	Remove an entry from the table.

DLProxy	operator[] (const Key &key) const
	Access or insert an entry using subscript notation.

DLProxy	operator[] (const Key &key)
	This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Public Member Functions inherited from Aleph::GenLhashTable< Key, BucketType, Cmp >
Cmp &	get_compare ()

const Cmp &	get_compare () const

	GenLhashTable (size_t table_size=Primes::DefaultPrime, Hash_Fct_Ptr hash_fct=Aleph::dft_hash_fct< Key >, Cmp cmp=Cmp(), float lower_alpha=hash_default_lower_alpha, float upper_alpha=hash_default_upper_alpha, bool remove_all_buckets=true, bool with_resize=true)
	Instantiate a generic hash table.

void	swap (GenLhashTable &other) noexcept

	GenLhashTable (const GenLhashTable &)=delete

GenLhashTable &	operator= (const GenLhashTable &)=delete

	GenLhashTable (GenLhashTable &&other) noexcept

GenLhashTable &	operator= (GenLhashTable &&other) noexcept

void	empty () noexcept
	Empties the hash table; frees memory of all buckets.

Hash_Fct	get_hash_fct () const noexcept

void	set_hash_fct (Hash_Fct fct) noexcept
	Set the internal hash function.

void	set_hash_fct (Hash_Fct_Ptr fct) noexcept

float	current_alpha () const noexcept
	return the current table load

Bucket *	insert (Bucket *bucket)
	Inserts bucket into the table and returns its address if the key is not already in the table; otherwise returns nullptr.

Bucket *	search_or_insert (Bucket *bucket)

Bucket *	search (const Key &key) const noexcept
	Search in the table for a bucket with key.

Bucket *	remove (Bucket *bucket) noexcept
	Removes bucket from the table.

size_t	resize (const size_t new_size)
	Resizes the hash table to new_size and re-locates keys.

virtual	~GenLhashTable ()
	Frees the table memory and, if remove_all_buckets is true (specified in the constructor), also frees memory of all buckets.

Bucket *	search_next (Bucket *bucket) const
	Returns the next bucket that collides with bucket.

const size_t &	capacity () const noexcept
	Returns the table capacity.

const size_t &	size () const noexcept
	Returns the number of elements contained in the table.

const size_t &	get_num_busy_slots () const noexcept
	Returns the number of occupied entries in the array.

constexpr bool	is_empty () const noexcept

Public Member Functions inherited from HashStats< GenLhashTable< Key, BucketType, Cmp > >
Stats	stats () const
	Computes statistics about chain length distribution.

void	print_stats (const Stats &stats) const
	Prints statistics to standard output.

void	set_upper_alpha (float __upper_alpha)
	Sets the upper load factor threshold.

void	set_lower_alpha (float __lower_alpha)
	Sets the lower load factor threshold.

constexpr float	get_lower_alpha () const noexcept
	Returns the lower load factor threshold.

constexpr float	get_upper_alpha () const noexcept
	Returns the upper load factor threshold.

Private Member Functions
void	copy (const DynLhashTable &table)

Record *	__insert (DLBucket *bucket)

Static Private Member Functions
static DLBucket *	record_to_bucket (Record *rec)

Additional Inherited Members
Protected Member Functions inherited from Aleph::GenLhashTable< Key, BucketType, Cmp >
	GenLhashTable (const size_t table_size, Hash_Fct hash_f, Cmp cpm_fct, const float lower, const float upper, const bool remove_all, const bool resize)

template<typename HashFunc , typename SearchKey >
Bucket *	search_with_custom_hash (HashFunc hash_func, const SearchKey &search_key) const noexcept
	Helper method for derived classes to perform custom heterogeneous searches.

Protected Attributes inherited from Aleph::GenLhashTable< Key, BucketType, Cmp >
Hash_Fct	hash_fct

size_t	len

Cmp	cmp

float	lower_alpha

float	upper_alpha

Detailed Description

template<typename Key, typename Record, class Cmp = Aleph::equal_to<Key>>
class Aleph::DynLhashTable< Key, Record, Cmp >

Dynamic hash table mapping keys to records with separate chaining.

DynLhashTable implements a key-value mapping using a hash table with separate chaining for collision resolution. It provides O(1) average-case complexity for insertions, lookups, and deletions.

The table supports both traditional methods (insert, search, remove) and the subscript operator [] for convenient access:

table[key] = record inserts or updates the entry
record = table[key] retrieves the value (throws if key not found)

Pointers returned by insert() and search() remain valid until the corresponding entry is removed, allowing direct modification of stored records.

Template Parameters

Key	Type of the indexing key (must be hashable).
Record	Type of the value associated with each key.
Cmp	Equality comparison functor for keys (default: Aleph::equal_to<Key>).

Example: DynLhashTable<std::string, int> ages;

ages.insert("Alice", 30);

ages["Bob"] = 25;

int* ptr = ages.search("Alice");

if (ptr) std::cout << *ptr; // prints 30

int bob_age = ages["Bob"]; // bob_age = 25

Aleph::DynLhashTable
Dynamic hash table mapping keys to records with separate chaining.
Definition tpl_dynLhash.H:90

Aleph::DynList::insert
T & insert(const T &item)
Insert a new item by copy.
Definition htlist.H:1502

Aleph::maps
DynList< T > maps(const C &c, Op op)
Classic map operation.
Definition ahFunctional.H:693

See also: LhashTableVtl for the underlying hash table implementation

Definition at line 89 of file tpl_dynLhash.H.

Member Typedef Documentation

◆ Hash_Fct_Ptr

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

using Aleph::DynLhashTable< Key, Record, Cmp >::Hash_Fct_Ptr = typename DynLhashTable<Key, Record>::Hash_Fct_Ptr

The type of hash function pointer.

Definition at line 179 of file tpl_dynLhash.H.

Constructor & Destructor Documentation

◆ DynLhashTable() [1/3]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Aleph::DynLhashTable< Key, Record, Cmp >::DynLhashTable	(	size_t	len = `DefaultPrime`,
		Hash_Fct_Ptr	hash_fct = `dft_hash_fct<Key>`
	)

inline

Construct a dynamic hash table.

Parameters

[in]	len	Initial size of the hash table (default: DefaultPrime).
[in]	hash_fct	Hash function to use (default: dft_hash_fct<Key>).

Exceptions

std::bad_alloc If memory allocation fails.

Definition at line 196 of file tpl_dynLhash.H.

◆ DynLhashTable() [2/3]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Aleph::DynLhashTable< Key, Record, Cmp >::DynLhashTable ( const DynLhashTable< Key, Record, Cmp > & table )

inline

Copy constructor.

Parameters

[in] table The table to copy from.

Exceptions

std::bad_alloc If memory allocation fails.

Definition at line 219 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::copy(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::table.

◆ DynLhashTable() [3/3]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Aleph::DynLhashTable< Key, Record, Cmp >::DynLhashTable ( DynLhashTable< Key, Record, Cmp > && table )

inlinenoexcept

Move constructor.

Parameters

[in,out] table The table to move from.

Warning: After move, the source table is in a moved-from state and must not be used except for destruction or assignment.

Definition at line 230 of file tpl_dynLhash.H.

Member Function Documentation

◆ __insert()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::__insert ( DLBucket * bucket )

inlineprivate

Definition at line 266 of file tpl_dynLhash.H.

References Aleph::GenLhashTable< Key, BucketType, Cmp >::insert(), and Aleph::DynLhashTable< Key, Record, Cmp >::DLBucket::record.

Referenced by Aleph::DynLhashTable< Key, Record, Cmp >::insert(), Aleph::DynLhashTable< Key, Record, Cmp >::insert(), Aleph::DynLhashTable< Key, Record, Cmp >::insert(), and Aleph::DynLhashTable< Key, Record, Cmp >::insert().

◆ copy()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

void Aleph::DynLhashTable< Key, Record, Cmp >::copy ( const DynLhashTable< Key, Record, Cmp > & table )

inlineprivate

Definition at line 204 of file tpl_dynLhash.H.

References Aleph::GenLhashTable< Key, BucketType, Cmp >::Iterator::has_curr(), Aleph::DynLhashTable< Key, Record, Cmp >::insert(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::table.

Referenced by Aleph::DynLhashTable< Key, Record, Cmp >::DynLhashTable(), and Aleph::DynLhashTable< Key, Record, Cmp >::operator=().

◆ insert() [1/4]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::insert	(	const Key &	key,
		const Record &	record
	)

inline

Insert a key-record pair into the table.

If the key already exists, a new entry is added (duplicates allowed). The returned pointer remains valid until the entry is removed.

Parameters

[in]	key	The key to insert.
[in]	record	The record to associate with the key.

Returns: Pointer to the stored record within the table.

Exceptions

std::bad_alloc If memory allocation fails.

Definition at line 283 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::__insert().

Referenced by Aleph::DynLhashTable< Key, Record, Cmp >::copy(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST_F().

◆ insert() [2/4]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::insert	(	const Key &	key,
		Record &&	record = `Record()`
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 289 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::__insert().

◆ insert() [3/4]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::insert	(	Key &&	key,
		const Record &	record
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 295 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::__insert().

◆ insert() [4/4]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::insert	(	Key &&	key,
		Record &&	record
	)

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 301 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::__insert().

◆ operator=() [1/2]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

DynLhashTable & Aleph::DynLhashTable< Key, Record, Cmp >::operator= ( const DynLhashTable< Key, Record, Cmp > & table )

inline

Copy assignment operator.

Parameters

[in] table The table to copy from.

Returns: Reference to this table.

Exceptions

std::bad_alloc If memory allocation fails.

Definition at line 241 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::copy(), Aleph::GenLhashTable< Key, BucketType, Cmp >::empty(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::table.

◆ operator=() [2/2]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

DynLhashTable & Aleph::DynLhashTable< Key, Record, Cmp >::operator= ( DynLhashTable< Key, Record, Cmp > && table )

inlinenoexcept

Move assignment operator.

Parameters

[in,out] table The table to move from.

Returns: Reference to this table.

Warning: After move, the source table is in a moved-from state and must not be used except for destruction or assignment.

Definition at line 258 of file tpl_dynLhash.H.

References Aleph::GenLhashTable< Key, BucketType, Cmp >::operator=(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::table.

◆ operator[]() [1/2]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

DLProxy Aleph::DynLhashTable< Key, Record, Cmp >::operator[] ( const Key & key )

inline

This is an overloaded member function, provided for convenience. It differs from the above function only in what argument(s) it accepts.

Definition at line 351 of file tpl_dynLhash.H.

◆ operator[]() [2/2]

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

DLProxy Aleph::DynLhashTable< Key, Record, Cmp >::operator[] ( const Key & key ) const

inline

Access or insert an entry using subscript notation.

For assignment (table[key] = value): inserts or updates the entry.
For reading (value = table[key]): returns the value or throws.

Parameters

[in] key The key to access.

Returns: A proxy object that handles both read and write operations.

Exceptions

std::invalid_argument If reading a non-existent key.

Definition at line 345 of file tpl_dynLhash.H.

◆ record_to_bucket()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

static DLBucket * Aleph::DynLhashTable< Key, Record, Cmp >::record_to_bucket ( Record * rec )

inlinestaticprivate

Definition at line 118 of file tpl_dynLhash.H.

References Aleph::maps(), and offset.

Referenced by Aleph::DynLhashTable< Key, Record, Cmp >::DLProxy::DLProxy(), and Aleph::DynLhashTable< Key, Record, Cmp >::remove().

◆ remove()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

void Aleph::DynLhashTable< Key, Record, Cmp >::remove ( Record * record )

inline

Remove an entry from the table.

The record pointer must have been obtained from insert() or search(). After removal, the pointer becomes invalid.

Parameters

[in] record Pointer to the record to remove (must be valid).

Warning: Passing an invalid pointer results in undefined behavior.

Definition at line 329 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::record_to_bucket(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::remove().

Referenced by TEST(), TEST(), TEST(), TEST(), and TEST().

◆ search()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

Record * Aleph::DynLhashTable< Key, Record, Cmp >::search ( const Key & key )

inline

Search for a key in the table.

Parameters

[in] key The key to search for.

Returns: Pointer to the associated record if found, nullptr otherwise.

Note: The returned pointer can be used to modify the record in-place.

Definition at line 314 of file tpl_dynLhash.H.

References Aleph::DynLhashTable< Key, Record, Cmp >::DLBucket::record, and Aleph::GenLhashTable< Key, BucketType, Cmp >::search().

Referenced by Aleph::DynLhashTable< Key, Record, Cmp >::DLProxy::DLProxy(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), TEST(), and TEST().

◆ swap()

template<typename Key , typename Record , class Cmp = Aleph::equal_to<Key>>

void Aleph::DynLhashTable< Key, Record, Cmp >::swap ( DynLhashTable< Key, Record, Cmp > & table )

inlinenoexcept

Swap contents with another table.

Parameters

[in,out] table The table to swap with.

Definition at line 184 of file tpl_dynLhash.H.

References Aleph::GenLhashTable< Key, BucketType, Cmp >::swap(), and Aleph::GenLhashTable< Key, BucketType, Cmp >::table.

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

tpl_dynLhash.H

Classes

Public Types

Public Member Functions

Private Member Functions

Static Private Member Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ Hash_Fct_Ptr

Constructor & Destructor Documentation

◆ DynLhashTable() [1/3]

◆ DynLhashTable() [2/3]

◆ DynLhashTable() [3/3]

Member Function Documentation

◆ __insert()

◆ copy()

◆ insert() [1/4]

◆ insert() [2/4]

◆ insert() [3/4]

◆ insert() [4/4]

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ record_to_bucket()

◆ remove()

◆ search()

◆ swap()