template<class T, size_t EmbeddedCapacity = 0, template< class TT > class OwnershipPolicy = RefCountedOwnership, class Node = HashmapNode<>>
class roc::core::Hashmap< T, EmbeddedCapacity, OwnershipPolicy, Node >
Intrusive hash table.
Characteristics: 1) Intrusive. Hash table nodes are stored directly in elements. No allocations are needed to insert a node. Arena 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 arena. 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. 6) Allows to iterate elements in insertion order. Implements safe iteration with regards to element insertion and deletion. Elements deleted during iteration won't be visited. Elements inserted during iteration will be visited.
Incremental rehashing technique is inspired by Go's map implementation, though there are differences. Load factor value is taken from it as well. Prime numbers for sizes are from https://planetmath.org/goodhashtableprimes.
- Template Parameters
-
| T | defines object type, it must inherit HashmapNode and additionally implement three methods: |
Key key() const;
static bool key_equal(Key key1, Key key2);
size_t hashsum_t
Hash type.
"Key" can be any type. Hashmap doesn't use it directly. It is never stored 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. |
| Node | defines base class of hashmap nodes. It is needed if HashmapNode is used with non-default tag. |
Definition at line 87 of file hashmap.h.
1.9.1