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

#include <HashTable.h>

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

using	ConstIterator = ezHashTableBaseConstIterator< KeyType, ValueType, Hasher >

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

	EZ_ADD_DEFAULT_OPERATOR_NOTEQUAL (const ezHashTableBase< KeyType, ValueType, Hasher > &)

void	Reserve (ezUInt32 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. More...

ezUInt32	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. More...

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 ezHashTableBaseConstIterator.

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 ezHashTableBaseConstIterator 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 ezHashTableBaseConstIterator to the first element that is not part of the hash-table. Needed to support range based for loops.

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

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

void	Swap (ezHashTableBase< 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 >
EZ_FORCE_INLINE bool	Contains (const CompatibleKeyType &key) const

template<typename CompatibleKeyType >
EZ_ALWAYS_INLINE ezUInt32	FindEntry (const CompatibleKeyType &key) const

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

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

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

	~ezHashTableBase ()
	Destructor.

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

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

Friends
struct	ezHashTableBaseConstIterator< KeyType, ValueType, Hasher >

struct	ezHashTableBaseIterator< KeyType, ValueType, Hasher >

Detailed Description

template<typename KeyType, typename ValueType, typename Hasher>
class ezHashTableBase< 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 ezHashHelper.

See also: ezHashHelper

Member Function Documentation

◆ Compact()

template<typename K , typename V , typename H >

void ezHashTableBase< 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 ezHashTableBase< 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:

/home/runner/work/ezEngine/ezEngine/Code/Engine/Foundation/Containers/HashTable.h
/home/runner/work/ezEngine/ezEngine/Code/Engine/Foundation/Containers/Implementation/HashTable_inl.h

Public Types

Public Member Functions

Protected Member Functions

Friends

Detailed Description

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

Member Function Documentation

◆ Compact()

◆ Insert()

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