|
| 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.
|
|
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
-
T | defines object type, it should inherit HashmapNode and additionally implement three methods: |
static bool key_equal(Key key1, Key key2);
Key key() const;
size_t hashsum_t
Hash type.
"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
-
EmbeddedCapacity | defines 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. |
OwnershipPolicy | defines 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.