ezEngine  Milestone 7
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

class  ConstIterator
 Const iterator. More...
 
struct  Entry
 
class  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.
 
bool Insert (const KeyType &key, const ValueType &value, ValueType *out_oldValue=nullptr)
 Inserts the key value pair or replaces value if an entry with the given key already exists. More...
 
bool Remove (const KeyType &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.
 
bool TryGetValue (const KeyType &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.
 
bool TryGetValue (const KeyType &key, 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.
 
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.
 
bool Contains (const KeyType &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.
 

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 ()
 Destructor.
 
void operator= (const ezHashTableBase< KeyType, ValueType, Hasher > &rhs)
 Copies the data from another hashtable into this one.
 

Private Types

enum  {
  FREE_ENTRY = 0, VALID_ENTRY = 1, DELETED_ENTRY = 2, FLAGS_MASK = 3,
  CAPACITY_ALIGNMENT = 32
}
 

Private Member Functions

void SetCapacity (ezUInt32 uiCapacity)
 
ezUInt32 FindEntry (const KeyType &key) const
 
ezUInt32 FindEntry (ezUInt32 uiHash, const KeyType &key) const
 
ezUInt32 GetFlagsCapacity () const
 
ezUInt32 GetFlags (ezUInt32 *pFlags, ezUInt32 uiEntryIndex) const
 
void SetFlags (ezUInt32 uiEntryIndex, ezUInt32 uiFlags)
 
bool IsFreeEntry (ezUInt32 uiEntryIndex) const
 
bool IsValidEntry (ezUInt32 uiEntryIndex) const
 
bool IsDeletedEntry (ezUInt32 uiEntryIndex) const
 
void MarkEntryAsFree (ezUInt32 uiEntryIndex)
 
void MarkEntryAsValid (ezUInt32 uiEntryIndex)
 
void MarkEntryAsDeleted (ezUInt32 uiEntryIndex)
 

Private Attributes

Entrym_pEntries
 
ezUInt32 * m_pEntryFlags
 
ezUInt32 m_uiCount
 
ezUInt32 m_uiCapacity
 
ezAllocatorBasem_pAllocator
 

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

Class Documentation

struct ezHashTableBase::Entry

template<typename KeyType, typename ValueType, typename Hasher>
struct ezHashTableBase< KeyType, ValueType, Hasher >::Entry

Class Members
KeyType key
ValueType value

Member Function Documentation

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.

template<typename K, typename V, typename H >
bool ezHashTableBase< K, V, H >::Insert ( const K &  key,
const V &  value,
V *  out_oldValue = nullptr 
)

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

Returns 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: