Roc Toolkit internal modules
Roc Toolkit: real-time audio streaming
Loading...
Searching...
No Matches
roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy > Class Template Reference

Intrusive hash table. More...

#include <hashmap.h>

Inheritance diagram for roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >:
roc::core::NonCopyable< T >

Public Types

typedef OwnershipPolicy< T >::Pointer Pointer
 Pointer type.
 

Public Member Functions

 Hashmap (IAllocator &allocator)
 Initialize empty hashmap.
 
 ~Hashmap ()
 Release ownership of all elements.
 
size_t capacity () const
 Get maximum number of elements that can be added to hashmap before grow() should be called.
 
size_t size () const
 Get number of elements added to hashmap.
 
bool contains (const T &element) const
 Check if element belongs to hashmap.
 
template<class Key >
Pointer find (const Key &key) const
 Find element in the hashmap by key.
 
void insert (T &element)
 Insert element into hashmap.
 
void remove (T &element)
 Remove element from hashmap.
 
bool grow ()
 Grow hashtable capacity.
 

Detailed Description

template<class T, size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
class roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >

Intrusive hash table.

Characteristics: 1) Intrusive. Hash table nodes are stored directly in elements. No allocations are needed to insert a node. Allocator is used only to allocate an array of buckets. 2) Collision-chaining. Implemented as an array of buckets, where a bucket is the head of a doubly-linked lists of bucket elements. 3) Controllable allocations. Allocations and deallocations are performed only when the hash table is explicitly growed. All other operations don't touch allocator. 4) Zero allocations for small hash tables. A fixed number of buckets can be embedded directly into hash table object. 5) Incremental rehashing. After hash table growth, rehashing is performed incrementally when inserting and removing elements. The slower hash table size growth is, the less overhead rehashing adds to each operation.

Incremental rehashing technique is inspired by Go's map implementation, though there are differeces. Load factor value is from Java's Hashmap implementation. Prime numbers for sizes are from https://planetmath.org/goodhashtableprimes.

Template Parameters
Tdefines object type, it should inherit HashmapNode and additionally implement three methods:
// compute key hash
static core::hashsum_t key_hash(Key key);
// compare two keys for equality
static bool key_equal(Key key1, Key key2);
// get object key
Key key() const;
size_t hashsum_t
Hash type.
Definition hashsum.h:21

"Key" can be any type. Hashmap doesn't use it directly. It is never copied and is always accessed via the three methods above. The hash is computed for a key only once when an object is inserted into hash table.

Template Parameters
EmbeddedCapacitydefines the capacity embedded directly into Hashmap. It is used instead of dynamic memory while the number of elements is smaller than this capacity. The actual object size occupied to provide the requested capacity is implementation defined.
OwnershipPolicydefines ownership policy which is used to acquire an element ownership when it's added to the hashmap and release ownership when it's removed from the hashmap.

Definition at line 78 of file hashmap.h.

Member Typedef Documentation

◆ Pointer

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
typedef OwnershipPolicy<T>::Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::Pointer

Pointer type.

Remarks
either raw or smart pointer depending on the ownership policy.

Definition at line 83 of file hashmap.h.

Constructor & Destructor Documentation

◆ Hashmap()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::Hashmap ( IAllocator allocator)
inline

Initialize empty hashmap.

Definition at line 86 of file hashmap.h.

◆ ~Hashmap()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::~Hashmap ( )
inline

Release ownership of all elements.

Definition at line 103 of file hashmap.h.

Member Function Documentation

◆ capacity()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
size_t roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::capacity ( ) const
inline

Get maximum number of elements that can be added to hashmap before grow() should be called.

Definition at line 112 of file hashmap.h.

◆ contains()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::contains ( const T &  element) const
inline

Check if element belongs to hashmap.

Note
  • has O(1) complexity
  • doesn't compute key hashes

Definition at line 126 of file hashmap.h.

◆ find()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
template<class Key >
Pointer roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::find ( const Key &  key) const
inline

Find element in the hashmap by key.

Returns
Pointer to the element with given key or NULL if it's not found.
Note
  • has O(1) complexity in average and O(n) in the worst case
  • computes key hash
The worst case is achieved when the hash function produces many collisions.

Definition at line 151 of file hashmap.h.

◆ grow()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
bool roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::grow ( )
inline

Grow hashtable capacity.

Remarks
Check if hash table is full (size is equal to capacity), and if so, increase hash table capacity and initiate incremental rehashing. Rehashing will be performed during subsequent insertions and removals.
Returns
  • true if no growth needed or growth succeeded
  • false if allocation failed
Note
  • has O(1) complexity
  • doesn't computes key hashes
  • makes allocations and deallocations
  • doesn't proceed lazy rehashing

Definition at line 253 of file hashmap.h.

◆ insert()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
void roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::insert ( T &  element)
inline

Insert element into hashmap.

Remarks
  • acquires ownership of element
Precondition
  • hashmap size() should be smaller than hashmap capacity()
  • element should not be member of any hashmap
  • hashmap shouldn't have an element with the same key
Note
  • has O(1) complexity in average and O(n) in the worst case
  • computes key hash
  • doesn't make allocations or deallocations
  • proceedes lazy rehashing
Insertion speed is higher when insert to remove ratio is close to one or lower, and slows down when it becomes higher than one. The slow down is caused by the incremental rehashing algorithm.

Definition at line 177 of file hashmap.h.

◆ remove()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
void roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::remove ( T &  element)
inline

Remove element from hashmap.

Remarks
  • releases ownership of element
Precondition
element should be member of this hashmap.
Note
  • has O(1) complexity
  • doesn't compute key hash
  • doesn't make allocations or deallocations
  • proceedes lazy rehashing

Definition at line 221 of file hashmap.h.

◆ size()

template<class T , size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership>
size_t roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy >::size ( ) const
inline

Get number of elements added to hashmap.

Definition at line 117 of file hashmap.h.


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