Implementation of a hashset. More...

#include <HashSet.h>

Inheritance diagram for ezHashSetBase< KeyType, Hasher >:

[legend]

Classes
class	ConstIterator
	Const iterator. More...

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

	EZ_ADD_DEFAULT_OPERATOR_NOTEQUAL (const ezHashSetBase< KeyType, Hasher > &)

void	Reserve (ezUInt32 uiCapacity)
	Expands the hashset 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 hashset to avoid wasting memory.

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

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

void	Clear ()
	Clears the table.

template<typename CompatibleKeyType >
bool	Insert (CompatibleKeyType &&key)
	Inserts the key. Returns whether the key was already existing.

template<typename CompatibleKeyType >
bool	Remove (const CompatibleKeyType &key)
	Removes the entry with the given key. Returns if an entry was removed.

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

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

bool	ContainsSet (const ezHashSetBase< KeyType, Hasher > &operand) const
	Checks whether all keys of the given set are in the container.

void	Union (const ezHashSetBase< KeyType, Hasher > &operand)
	Makes this set the union of itself and the operand.

void	Difference (const ezHashSetBase< KeyType, Hasher > &operand)
	Makes this set the difference of itself and the operand, i.e. subtracts operand.

void	Intersection (const ezHashSetBase< KeyType, Hasher > &operand)
	Makes this set the intersection of itself and the operand.

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

ConstIterator	GetEndIterator () const
	Returns a constant Iterator to the first element that is not part of the hashset. Needed to implement range based for loop support.

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 (ezHashSetBase< KeyType, Hasher > &other)
	Swaps this map with the other one.

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

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

template<typename CompatibleKeyType >
EZ_FORCE_INLINE ezHashSetBase< K, H >::ConstIterator	Find (const CompatibleKeyType &key) const

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

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

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

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

	~ezHashSetBase ()
	Destructor.

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

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

Detailed Description

template<typename KeyType, typename Hasher>
class ezHashSetBase< KeyType, Hasher >

Implementation of a hashset.

The hashset stores values by using the hash as an index into the table. This implementation uses linear-probing to resolve hash collisions which means all values are stored in a linear array. Automatic resizing maintains a load factor below 60% for optimal performance.

Performance characteristics:

Average case: O(1) - insertion, erasure, lookup
Worst case: O(n) - when all keys hash to the same location (very rare with good hash functions)
Resizing: O(n) - occurs when load factor exceeds 60%, amortized cost is still O(1) per operation
Memory usage: More memory efficient than tree-based containers, ~1.67x element storage
Iteration: O(n) in hash order (not sorted)
Set operations (union, intersection, difference): O(n + m) average case

Use when:

Fast lookup/insertion/removal is the primary concern
You don't need sorted iteration
Memory efficiency is important
You have a good hash function for your key type

Consider ezSet instead when:

You need sorted iteration
You need stable element addresses (no reallocation)
Predictable O(log n) performance is more important than average O(1)

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 H >

void ezHashSetBase< K, H >::Compact ( )

Tries to compact the hashset to avoid wasting memory.

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

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

/home/runner/work/ezEngine/ezEngine/Code/Engine/Foundation/Containers/HashSet.h
/home/runner/work/ezEngine/ezEngine/Code/Engine/Foundation/Containers/Implementation/HashSet_inl.h

Classes

Public Member Functions

Protected Member Functions

Detailed Description

Member Function Documentation

◆ Compact()