Implementation of a hashtable which stores key/value pairs. More...

#include <HashTable.h>

Public Types
using	Iterator = plHashTableBaseIterator<KeyType, ValueType, Hasher>

using	ConstIterator = plHashTableBaseConstIterator<KeyType, ValueType, Hasher>

Public Member Functions
bool	operator== (const plHashTableBase< KeyType, ValueType, Hasher > &rhs) const
	Compares this table to another table.

	PL_ADD_DEFAULT_OPERATOR_NOTEQUAL (const plHashTableBase< KeyType, ValueType, Hasher > &)

void	Reserve (plUInt32 uiCapacity)
	Expands the hashtable by over-allocating the internal storage so that the load factor is lower or equal to 60% when inserting the given number of entries.

void	Compact ()
	Tries to compact the hashtable to avoid wasting memory.

plUInt32	GetCount () const
	Returns the number of active entries in the table.

bool	IsEmpty () const
	Returns true, if the hashtable does not contain any elements.

void	Clear ()
	Clears the table.

template<typename CompatibleKeyType , typename CompatibleValueType >
bool	Insert (CompatibleKeyType &&key, CompatibleValueType &&value, ValueType *out_pOldValue=nullptr)
	Inserts the key value pair or replaces value if an entry with the given key already exists.

template<typename CompatibleKeyType >
bool	Remove (const CompatibleKeyType &key, ValueType *out_pOldValue=nullptr)
	Removes the entry with the given key. Returns whether an entry was removed and optionally writes out the old value to out_oldValue.

Iterator	Remove (const Iterator &pos)
	Erases the key/value pair at the given Iterator. Returns an iterator to the element after the given iterator.

void	Remove (const ConstIterator &pos)=delete
	Cannot remove an element with just a plHashTableBaseConstIterator.

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, ValueType &out_value) const
	Returns whether an entry with the given key was found and if found writes out the corresponding value to out_value.

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, const ValueType *&out_pValue) const
	Returns whether an entry with the given key was found and if found writes out the pointer to the corresponding value to out_pValue.

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, ValueType *&out_pValue) const
	Returns whether an entry with the given key was found and if found writes out the pointer to the corresponding value to out_pValue.

template<typename CompatibleKeyType >
ConstIterator	Find (const CompatibleKeyType &key) const
	Searches for key, returns a plHashTableBaseConstIterator to it or an invalid iterator, if no such key is found. O(1) operation.

template<typename CompatibleKeyType >
Iterator	Find (const CompatibleKeyType &key)
	Searches for key, returns an Iterator to it or an invalid iterator, if no such key is found. O(1) operation.

template<typename CompatibleKeyType >
const ValueType *	GetValue (const CompatibleKeyType &key) const
	Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr.

template<typename CompatibleKeyType >
ValueType *	GetValue (const CompatibleKeyType &key)
	Returns a pointer to the value of the entry with the given key if found, otherwise returns nullptr.

ValueType &	operator[] (const KeyType &key)
	Returns the value to the given key if found or creates a new entry with the given key and a default constructed value.

ValueType &	FindOrAdd (const KeyType &key, bool *out_pExisted=nullptr)
	Returns the value stored at the given key. If none exists, one is created. bExisted indicates whether an element needed to be created.

template<typename CompatibleKeyType >
bool	Contains (const CompatibleKeyType &key) const
	Returns if an entry with given key exists in the table.

Iterator	GetIterator ()
	Returns an Iterator to the very first element.

Iterator	GetEndIterator ()
	Returns an Iterator to the first element that is not part of the hash-table. Needed to support range based for loops.

ConstIterator	GetIterator () const
	Returns a constant Iterator to the very first element.

ConstIterator	GetEndIterator () const
	Returns a plHashTableBaseConstIterator to the first element that is not part of the hash-table. Needed to support range based for loops.

plAllocator *	GetAllocator () const
	Returns the allocator that is used by this instance.

plUInt64	GetHeapMemoryUsage () const
	Returns the amount of bytes that are currently allocated on the heap.

void	Swap (plHashTableBase< KeyType, ValueType, Hasher > &other)
	Swaps this map with the other one.

template<typename CompatibleKeyType , typename CompatibleValueType >
bool	Insert (CompatibleKeyType &&key, CompatibleValueType &&value, V *out_pOldValue)

template<typename CompatibleKeyType >
bool	Remove (const CompatibleKeyType &key, V *out_pOldValue)

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, V &out_value) const

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, const V *&out_pValue) const

template<typename CompatibleKeyType >
bool	TryGetValue (const CompatibleKeyType &key, V *&out_pValue) const

template<typename CompatibleKeyType >
const V *	GetValue (const CompatibleKeyType &key) const

template<typename CompatibleKeyType >
V *	GetValue (const CompatibleKeyType &key)

template<typename CompatibleKeyType >
PL_FORCE_INLINE bool	Contains (const CompatibleKeyType &key) const

template<typename CompatibleKeyType >
PL_ALWAYS_INLINE plUInt32	FindEntry (const CompatibleKeyType &key) const

Protected Member Functions
	plHashTableBase (plAllocator *pAllocator)
	Creates an empty hashtable. Does not allocate any data yet.

	plHashTableBase (const plHashTableBase< KeyType, ValueType, Hasher > &rhs, plAllocator *pAllocator)
	Creates a copy of the given hashtable.

	plHashTableBase (plHashTableBase< KeyType, ValueType, Hasher > &&rhs, plAllocator *pAllocator)
	Moves data from an existing hashtable into this one.

	~plHashTableBase ()
	Destructor.

void	operator= (const plHashTableBase< KeyType, ValueType, Hasher > &rhs)
	Copies the data from another hashtable into this one.

void	operator= (plHashTableBase< KeyType, ValueType, Hasher > &&rhs)
	Moves data from an existing hashtable into this one.

Friends
struct	plHashTableBaseConstIterator< KeyType, ValueType, Hasher >

struct	plHashTableBaseIterator< KeyType, ValueType, Hasher >

Detailed Description

template<typename KeyType, typename ValueType, typename Hasher>
class plHashTableBase< KeyType, ValueType, Hasher >

Implementation of a hashtable which stores key/value pairs.

The hashtable maps keys to values by using the hash of the key as an index into the table. This implementation uses linear-probing to resolve hash collisions which means all key/value pairs are stored in a linear array. All insertion/erasure/lookup functions take O(1) time if the table does not need to be expanded, which happens when the load gets greater than 60%. The hash function can be customized by providing a Hasher helper class like plHashHelper.

See also: plHashHelper

Member Function Documentation

◆ Compact()

template<typename K , typename V , typename H >

void plHashTableBase< K, V, H >::Compact ( )

Tries to compact the hashtable to avoid wasting memory.

The resulting capacity is at least 'GetCount' (no elements get removed). Will deallocate all data, if the hashtable is empty.

◆ Insert()

template<typename KeyType , typename ValueType , typename Hasher >

template<typename CompatibleKeyType , typename CompatibleValueType >

bool plHashTableBase< KeyType, ValueType, Hasher >::Insert	(	CompatibleKeyType &&	key,
		CompatibleValueType &&	value,
		ValueType *	out_pOldValue = nullptr )

Inserts the key value pair or replaces value if an entry with the given key already exists.

Returns true if an existing value was replaced and optionally writes out the old value to out_oldValue.

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

Code/Engine/Foundation/Containers/HashTable.h
Code/Engine/Foundation/Containers/Implementation/HashTable_inl.h

Public Types

Public Member Functions

Protected Member Functions

Friends

Detailed Description

Member Function Documentation

◆ Compact()

◆ Insert()