ezEngine  Milestone 9
ezHashTableBase< KeyType, ValueType, Hasher > Class Template Reference

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

#include <HashTable.h>

Inheritance diagram for ezHashTableBase< KeyType, ValueType, Hasher >:

Classes

struct  ConstIterator
 Const iterator. More...
 
struct  Iterator
 Iterator with write access. More...
 

Public Member Functions

bool operator== (const ezHashTableBase< KeyType, ValueType, Hasher > &rhs) const
 Compares this table to another table.
 
bool operator!= (const ezHashTableBase< KeyType, ValueType, Hasher > &rhs) const
 Compares this table to another table.
 
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_oldValue=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_oldValue=nullptr)
 Removes the entry with the given key. Returns if 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.
 
template<typename CompatibleKeyType >
bool TryGetValue (const CompatibleKeyType &key, ValueType &out_value) const
 Returns if 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 if 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)
 Returns if 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 >
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.
 
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.
 
ConstIterator GetIterator () const
 Returns a constant Iterator to the very first element.
 
ezAllocatorBaseGetAllocator () 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 >
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 (ezAllocatorBase *pAllocator)
 Creates an empty hashtable. Does not allocate any data yet.
 
 ezHashTableBase (const ezHashTableBase< KeyType, ValueType, Hasher > &rhs, ezAllocatorBase *pAllocator)
 Creates a copy of the given hashtable.
 
 ezHashTableBase (ezHashTableBase< KeyType, ValueType, Hasher > &&rhs, ezAllocatorBase *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.
 

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 K , typename V, typename H >
template<typename CompatibleKeyType , typename CompatibleValueType >
bool ezHashTableBase< K, V, H >::Insert ( CompatibleKeyType &&  key,
CompatibleValueType &&  value,
V *  out_oldValue = 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: