template<typename TAllocator, typename TValueDescriptor, typename THash = std::hash <typename TValueDescriptor::KeyType>, typename TEqual = std::equal_to<typename TValueDescriptor::KeyType>,
lang::Caching THashCaching = lang::Caching::Auto,
Recycling TRecycling = Recycling::Private>
class alib::containers::HashTable< TAllocator, TValueDescriptor, THash, TEqual, THashCaching, TRecycling >
Contents
1. Introduction
2. Hash Sets vs. Hash Maps
3. Single And Multiple Entries
4. Re-Hashing
5. Iterators
6. Hash Codes
6.1 Caching Hash Codes
6.2 Hash Codes Pre-calculation
6.3 Hash Code Quality
7. Memory Use
8. Comparison To Standard Library Hash-Types
Reference Documentation
1. Introduction
This class implements a hash table 
that stores and retrieves objects very efficiently in respect to execution performance. All memory for the hash table and its entries are allocated using a template allocator type.
Two type definitions based on this class exist, which change the set of template parameters of this type by providing reasonable replacements. These types are:
In many cases, the use of one of these definitions is more convenient than instantiating this type directly. The meaning of these types is discussed in the next section.
2. Hash Sets vs. Hash Maps
A "hash set" is commonly understood as a type that contains custom values of StoredType, which are also used as the key to finding such stored objects. "Hash maps" are hash tables that store objects of a custom MappedType which are associated to a value of a key KeyType. In this "mode" the key is not contained in the custom value.
The template parameters and implementation of this class supports both concepts and they are covered by the two provided alternative type definitions mentioned in the previous section. Furthermore, those go along well with what is found in the standard C++ library:
HashSet Removes template parameter TValueDescriptor (by presetting it to a built-in helper-type) and instead denotes all three types, namely StoredType, KeyType and MappedType to the same new template parameter T. Functors THash and TEqual consequently expect the StoredType.
This type definition is similar to what types std::unordered_set and std::unordered_multiset of the standard C++ class library provide.
HashMap Removes template parameter TValueDescriptor (by presetting it to a built-in helper-type) and instead introduces template parameters TKey and TMapped. Here, only the key-portion is used for calculating hash values and testing elements for equality. The mapped-portion is the true custom type that is to be stored.
Consequently, HashMap defines the StoredType as std::pair<TKey, TMapped>.
The type definition is similar to what types std::unordered_map and std::unordered_multimap of the standard C++ class library provide.
To achieve this flexibility, template parameter TValueDescriptor, which is exposed as DescriptorType, is constrained to have two methods Key() and Mapped() to extract a reference to the corresponding portions out of the stored value.
One of the advantages of this approach is that this type supports a third "mode", besides implementing "hash sets" and "hash maps": Custom value type StoredType may have a key-portion embedded, instead of using the complete type as a search key.
While there is no specific type definition for this "key-embedded mode" available, the using code needs to create a custom version of template parameter TValueDescriptor which enables the extraction of the key and mapped portions of the stored type. The following table summarizes this:
| Working Mode | Type to Use | Value Descriptor Type |
| Hash Set | HashSet (A type definition on HashTable) | Automaticly chosen as built-in TIdentDescriptor |
| Hash Map | HashMap (A type definition on HashTable) | Automaticly chosen as built-in TPairDescriptor |
| Hash Set with embedded Key | HashTable (The original type) | A custom type has to be provided |
- Note
- The hash-table implementations of the standard C++ library do not support a similar approach. While with the provision of customized hash- and comparison-functors, of course only a portion of a type stored in a set can be used for hashing and comparing, still the interface functions require to receive a "complete" instance, which then is often "nulled" or "empty" in respect to the fields that are not used for the key.
Because of this limitation, ALib introduces template parameter TValueDescriptor in addition to parameters THash and TEqual.
As a sample for the advantage consider method EmplaceIfNotExistent(const KeyType&, TArgs&& ...). A corresponding method is found with type std::unordered_map::try_emplace, but not with std::unordered_set. In contrast with this implementation, the method is usable with hash maps as well as with hash sets!
The only precondition to the availability of this method, is that the StoredType has to be constructible from the combined list of given arguments, hence the KeyType argument along with given arguments of variadic template types TArgs. The same is true for method EmplaceOrAssign KeyType&, TArgs&&... args)
The set of available interface methods slightly changes with the two operation modes:
- Hash Set Mode:
Method overload EmplaceIfNotExistent(TArgs&& ...) is exclusively available with hash sets.
- Hash Map Mode:
The following method overloads are exclusively available with hash-maps:"
- InsertOrAssign(const KeyType&, MappedType&&)
- InsertOrAssign(const KeyType&, const MappedType&)
- InsertIfNotExistent(const KeyType&, MappedType&&)
- InsertIfNotExistent(const KeyType&, const MappedType&)
<br><br>
In addition, the following method overloads of inner types are also exclusively available
with hash-<em>maps</em>.
- Mapped
- Mapped
- Mapped
A hint to restrictions is given with the documentation of each method of concern.
Note that methods that expect a single KeyType are usable with both operation modes, because
with hash sets the key-type equals type StoredType.
\note
Technically, the availability of the methods is selected at compile-time.
@section alib_ns_containers_hashtable_single_multi 3. Single And Multiple Entries
The standard C++ library differentiates between hashing containers that accept only one
element with a specific <em>key-portion</em> of the value (see <c>std::unordered_set</c> and
<c>std::unordered_map</c>) and those that accept multiple insertions of objects with the
same <em>key-portion</em> (see <c>std::unordered_multiset</c> <c>std::unordered_multimap</c>).
This library does \b not provide separate types and any instantiation of this class allows
multiple entries. But this is rather an extension of functionality, than a restriction
and does not impose a penalty on performance.
If unique entries are to be achieved, the user of the type has to make sure for herself that
no multiple entries are inserted. This can be guaranteed, with the exclusive use of the
following set of (partly overloaded) methods, which prevent the creation of multiple entries:
- InsertUnique(const StoredType&) / EmplaceUnique
- InsertOrAssign(const KeyType&, const MappedType&) / EmplaceOrAssign
- InsertIfNotExistent(const StoredType&) /
EmplaceIfNotExistent(const KeyType&, TArgs&& ...)
In contrast to this, methods Insert(const StoredType&) and Emplace
(and their overloads) will insert an equal value without giving further notice.
(For example, by providing a special return value that indicates if the inserted key existed
before).<br>
Method EraseUnique(const KeyType&) is more efficient than erase(const KeyType&)
and a further advantage is that it asserts (in debug-compilations) that not more than one
element is found in the table.
\note
If uniqueness of key values is needed, it might be seen by the reader to be a "disadvantage"
that the burden is on the user of the class to guarantee such uniqueness.
However, such burden exists with the set-types of the standard library likewise:
There, result values have to be evaluated to determine if an insertion was successful or not.
The various smaller changes and extensions of the <c>std</c>-types with C++ 14 and 17 reflect
the design problems of the approach to provide "unique" and "multi" types.
\note
The approach that \b %ALib takes here has three small benefits:
1. A user is free to choose a "mixed mode" by allowing duplicates of certain values (keys)
and not allowing duplicates for others.
While this can be achieved with <c>std::unordered_multimap/set</c> as well, a performance
penalty is given, unless the extended interface of C++17 standard is used with great care.
2. The code is better readable, due to explicit naming of the invocations, in contrast
to the need to knowing a container's type with each invocation.
3. The use of the type and this documentation is less confusing, because only one type exists.
In contrast, the two types found in <c>std</c> have equally named methods that act
differently and return different result types.
@section alib_ns_containers_hashtable_rehashing 4. Re-Hashing
A check for the need to perform re-hashing is made with every insertion of an element.
The policy for re-hashing is described as follows:
- With insertions, the new average bucket size is calculated as Size divided by BucketCount.
- This value is compared with MaxLoadFactor and if higher the number of buckets is increased.
- When increased, the new minimum number of buckets is calculated as Size divided by
BaseLoadFactor. Starting from this minimum, the effective number of buckets is chosen as the
next higher prime number from a static table.
- Automatic rehashes may be disabled by setting MaxLoadFactor to a very high value, e.g.
<c>std::numeric_limits<float>::max()</c>
The number of buckets is never decreased, unless the method Reset is invoked.
Manual re-hashing is not supported by design. In our view, with monotonic growth (or stability
in size) and hence the absence of dynamic increase/decrease scenarios, manual rehashing is not
needed. Only the base and maximum load factors are of concern, which both can be
specified with construction and with the methods
MaxLoadFactor respectively MaxLoadFactor(float).<br>
What can be done, however, is to use the method MaxLoadFactor to "disable" rehashing
temporarily and thus to allow an efficient mass insertion. Nevertheless, if the number of
elements to be inserted is known upfront, the use of method Reserve, respectively
ReserveRecyclables is the preferred approach.
@section alib_ns_containers_hashtable_iterators 5. Iterators
@subsection autotoc_md25 5.1 Iterator Types
There are two types of iterators provided:
- Iterator and its constant sibling
ConstIterator, used to iterate over all elements of the
hash table,
- LocalIterator and its constant sibling
ConstLocalIterator used to iterate over the elements
of a certain bucket only.
Both types satisfy the C++ standard library concept
<a href="https://en.cppreference.com/w/cpp/named_req/ForwardIterator" >ForwardIterator <img src="external_link.svg" height="12" width="10"></a>.
@subsection autotoc_md26 5.2 Validity Rules
The following rules define the validity of existing iterator instances on table operations:
- <b>Element Insertions:</b>
- If no rehashing is performed (see previous section) all iterators remain valid.
- If rehashing is performed, existing iterators become invalid in respect to allowance
of increments and comparison. The elements that existing iterators referred to
before the insertion remain valid. Consequently, existing iterators may still be used
to access the custom element value and modify the mapped portion of it. They may just
not be traversed then.
- <b>Element Removals:</b><br>
All existing iterators that referred to elements that have been removed become invalid.
All others remain fully intact.<br>
The order of the elements that are not erased is preserved, which makes it possible to
erase individual elements during iteration.
@section alib_ns_containers_hashtable_hashcodes 6. Hash Codes
@subsection alib_ns_containers_hashtable_caching 6.1 Caching Hash Codes
Template parameter <span>THashCaching</span> may be used to control if hash codes are cached.
Caching the hash codes increases the memory consumption of this class by <c>sizeof(size_t)</c>
per inserted element. While this is only a small amount and memory consumption should not
be a great concern when monotonic allocation is used, caching the hash codes may impose a
reasonable performance impact. This impact depends on the performance of functor <span>THash</span>
working on the <c>key-portion</c> of the inserted value.
The cached hash code is used when the table is
re-hashed. In addition, the cached
hash code is also used with almost all interface methods (insertion, deletion and search
operations): If cached, any needed comparison of two elements will first compare the hash
codes and only invoke templated functor <span>TEqual</span> if those match.
If template parameter <span>THashCaching</span> evaluates to <b>Caching::Auto</b> then this class
defaults to use caching if type KeyType is not arithmetic
(using <c>std::is_arithmetic<TKey></c> for this check).<br>
The caching option of an instance of this class can be queried with enum CachedHashCodes.
@subsection alib_ns_containers_hashtable_hashprecalc 6.2 Hash Codes Pre-calculation
The following overloaded methods accept parameter <span>hashCode</span> in addition to the parameters
accepted by their corresponding base version:
- Find(const KeyType&, size_t)
- Insert(const StoredType&, size_t)
- Insert(StoredType&&, size_t)
- InsertUnique(StoredType&&, size_t)
- InsertOrAssign(const KeyType&, MappedType&&, size_t)
- InsertIfNotExistent(const KeyType&, MappedType&&, size_t)
- InsertIfNotExistent(StoredType&&, size_t)
- Extract(const KeyType&, size_t)
- Erase(const KeyType&, size_t)
- EraseUnique(const KeyType&, size_t)
The rationale for the provision of these methods is to allow to "pre-calculate" a key's hash
code before invoking the method. This is efficient in situations where one or more subsequent
operations with the same key are performed. For example:
- Insertions of multiple objects with the same key.
- Insertions of an object into multiple hash tables.
- Situations where the result of a find operation may lead to further operations with the
same object.
@subsection alib_ns_containers_hashtable_hashquality 6.3 Hash Code Quality
To have hash tables perform in constant time <em>O(1)</em> in the average case, a
well-implemented calculation of hash-codes has to be provided for template type <span>TKey</span> with
template functor <span>THash</span>. This is an obligation of the user of this type.
This <b>ALib %Module</b> supports the configuration macro ALIB_DEBUG_CONTAINERS which enables extra
features.
The entities relevant for this type are:
- DbgGetHashTableDistribution,
- DbgDumpDistribution and
- DbgDumpHashtable.
These methods may be used to assert the quality of custom hash algorithms.
@section alib_ns_containers_hashtable_memory 7. Memory Use
With the template parameter <span>TRecycling</span> being either Private
(the default) or Shared, the internal
<em>"node objects"</em> are remembered when deleted, and "recycled" with future insertions.
The rationale for this lies in the simple fact that memory cannot be returned to
the monotonic allocator. The recycling mechanism is very lightweight and does not cost measurable
performance. If it is assured that no deletions are made during the life-cycle of an instance,
type None may be used to eliminate this little overhead
of recycling. This is why type-definition MonoAllocator is recommended to be used
with this container.
If the table is re-hashed, the former bucket list is likewise recycled and sliced into as many
internal node objects as possible. The precondition for this is that the allocator
interface method allowsMemSplit returns \c true. This is true for type
MonoAllocator.
With these two mechanisms in place, the use of monotonic allocation with this container
is very safe in respect to avoid memory exhaustion.
The use of this class, even in scenarios where a lot of (theoretically an endless amount of)
erase and insert operations are performed, will not increase memory consumption, as long it is
guaranteed that the overall size of the table is limited.<br>
If a maximum number of possible insertions is known, method #ReserveRecyclables might be used
to allocate all needed memory at once. With that, a
snapshot of the allocator can be taken and
later used to reset the allocator to the minimum that preserves all memory in the according
hash table instance.<br>
For advanced usage, it is advisable to fully understand the concept of monotonic allocation
implemented with this module \ref alib_mods_contmono "ALib Containers".
@section alib_ns_containers_hashtable_comparison 8. Comparison To Standard Library Hash-Types
In the previous sections, it was already referred several times to types
- <c>std::unordered_map</c>,
- <c>std::unordered_multimap,</c>
- <c>std::unordered_set</c> and
- <c>std::unordered_multiset</c>
of the C++ standard library. The use cases and features of these four compared to this type are
generally the same and this type can be used to replace the standard tyes without general
limitations and vice versa.
Then with C++17, the standard library was extended by a new set of types, namely
- <c>std::pmr::unordered_map</c>,
- <c>std::pmr::unordered_multimap,</c>
- <c>std::pmr::unordered_set</c> and
- <c>std::pmr::unordered_multiset</c>
which, likewise this type, may use monotonic allocation (for example, in combination with C++17
type <c>std::pmr::monotonic_buffer_resource</c>).
On the one hand, \b %ALib in the past needed support of monotonic allocation already for
C++ 11, and on the other hand, the C++17 library extensions follow slightly different design
goals. Details of these were given in the previous section.
Besides these general differences, the specific similarities and differences can be summarized
as follows:
- This \b %ALib type does not distinguish sets and maps but provides a more flexible approach:
Mapped types do not necessarily need to be build using a <c>std::pair</c> of key and value
elements.
For convenience, when the use of <c>std::pair</c> is suitable, type definition
HashMap offers exactly this.
- This \b %ALib type does not distinguish sets/maps from multi-sets/maps.
The rationale for this design decision has been described in section
3. Single And Multiple Entries.
- Almost all members of the four standard library types are implemented with this type
in a very compatible fashion. The member names were translated from <em>lower_snake_case</em>
to <em>UpperCamelCase</em> and then sometimes slightly changed.<br>
C++17 extensions of the standard types were reflected.
- Method #Find provides additional overloads that accept an externally (pre-) calculated
hash code. This allows efficiently using the same key with a series of searches within
different hash table instances. Note that C++20 offers a templated version of <c>find</c>,
which allows performing the same optimization.
- Erase methods that accept a #LocalIterator (bucket iterators) that are not available with
the four standard library types, are provided with this type.
- There is no <c>operator[]</c> defined. The rationale to omit this - at first sight convenient
and intuitive - operator, is that it imposes insert operation even if used in r-value
expressions. This is considered an unwanted side effect.
- The caching of hash-codes can be controlled with this type, while it is an
implementation-dependent feature with the standard library.
- The automatic increase (re-hashing) of the bucket number can be tweaked with
constructor parameter <span>pBaseLoadFactor</span> (and method #BaseLoadFactor(float)), which is not
specified with the standard library types.
- Assignment <c>operator=</c> is not available with this implementation.
If needed, such has to be implemented by a user (full iteration with copying elements from one
instance to another).
@see
- Chapter 4.1 Provided Containers of the joint Programmer's Manuals of modules
\ref alib_mods_contmono "ALib Containers" and \ref alib_mods_contmono "ALib Monomem".
- Chapter 1.4.2 Asserting Critical Sections' Entry And Exit of the Programmer's Manual of module
\ref alib_mod_threads "ALib Threads" for information about debugging multithreaded access on instances of this
type.
@section alib_ns_containers_hashtable_referencedoc Reference Documentation
@tparam TAllocator The allocator type to use.
@tparam TValueDescriptor Defines the #StoredType, #KeyType and #MappedType. Furthermore has to
proving methods that to extract key- and mapped values out of the
stored type.<br>
For details on required type definitions and method signatures, see
provided implementations
TIdentDescriptor and
TPairDescriptor as a sample.<br>
The type is published as
DescriptorType.
@tparam THash The hash functor applicable to the key-type defined by
<span>TValueDescriptor</span>.
Defaults to <c>std::hash<typename TValueDescriptor::KeyType></c>
and is published as HashType.
@tparam TEqual The comparison functor on the key-type defined by <span>TValueDescriptor</span>.
Defaults to <c>std::equal_to<typename TValueDescriptor::KeyType></c>
and is published as EqualType.
@tparam THashCaching Determines if hash codes are cached when elements are inserted.
Defaults to <b>Caching::Auto</b>, which enables caching if
<c>std::is_arithmetic<TKey>::value</c> evaluates to \c false.
@tparam TRecycling Denotes the type of recycling that is to be performed. Possible values
are
Private (the default),
Shared or
None.
Definition at line 427 of file hashtable.hpp.
|
| template<bool TRequires = TRecycling!= Recycling::Shared> |
| | HashTable (AllocatorType &pAllocator, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0) |
| template<typename TSharedRecycler = SharedRecyclerType> |
| | HashTable (AllocatorType &pAllocator, TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0) |
| template<bool TRequires = TRecycling!= Recycling::Shared> |
| | HashTable (float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0) |
| template<typename TSharedRecycler = SharedRecyclerType> |
| | HashTable (TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0) |
| AllocatorType & | GetAllocator () noexcept |
| void | Clear () |
| void | Reset () |
| integer | Size () const noexcept |
| bool | IsEmpty () const noexcept |
| void | Reserve (integer expected, lang::ValueReference reference) |
| void | ReserveRecyclables (integer expected, lang::ValueReference reference) |
| integer | RecyclablesCount () const noexcept |
| void | BaseLoadFactor (float newBaseLoadFactor) noexcept |
| float | BaseLoadFactor () const noexcept |
| void | MaxLoadFactor (float newMaxLoadFactor) noexcept |
| float | MaxLoadFactor () const noexcept |
| uinteger | BucketCount () const noexcept |
| uinteger | BucketSize (uinteger bucketNumber) const noexcept |
| uinteger | BucketNumber (const KeyType &key) const noexcept |
| Iterator | Insert (const StoredType &value) |
| Iterator | Insert (const StoredType &value, size_t hashCode) |
| Iterator | Insert (StoredType &&value) |
| Iterator | Insert (StoredType &&value, size_t hashCode) |
| Iterator | Insert (ElementHandle &handle) |
| Iterator | InsertUnique (const StoredType &value) |
| Iterator | InsertUnique (const StoredType &value, size_t hashCode) |
| Iterator | InsertUnique (StoredType &&value) |
| Iterator | InsertUnique (StoredType &&value, size_t hashCode) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertOrAssign (const KeyType &key, const MappedType &mapped) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertOrAssign (const KeyType &key, MappedType &&mapped) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertOrAssign (const KeyType &key, MappedType &&mapped, size_t hashCode) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertIfNotExistent (const KeyType &key, const MappedType &mapped) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertIfNotExistent (const KeyType &key, MappedType &&mapped, size_t hashCode) |
| template<typename TRequires = MappedType> |
| std::pair< Iterator, bool > | InsertIfNotExistent (const KeyType &key, MappedType &&mapped) |
| std::pair< Iterator, bool > | InsertIfNotExistent (const StoredType &value) |
| std::pair< Iterator, bool > | InsertIfNotExistent (StoredType &&value) |
| std::pair< Iterator, bool > | InsertIfNotExistent (StoredType &&value, size_t hashCode) |
| Iterator | InsertIfNotExistent (ElementHandle &handle) |
| template<typename... TArgs> |
| Iterator | Emplace (TArgs &&... args) |
| template<typename... TArgs> |
| Iterator | EmplaceUnique (TArgs &&... args) |
| template<typename TRequires = MappedType, typename... TArgs> |
| std::pair< Iterator, bool > | EmplaceOrAssign (const KeyType &key, TArgs &&... args) |
| template<typename TRequires = MappedType, typename... TArgs> |
| std::pair< Iterator, bool > | EmplaceIfNotExistent (TArgs &&... args) |
| template<typename... TArgs> |
| std::pair< Iterator, bool > | EmplaceIfNotExistent (const KeyType &key, TArgs &&... args) |
| Iterator | Find (const KeyType &key) |
| ConstIterator | Find (const KeyType &key) const |
| Iterator | Find (const KeyType &key, size_t hashCode) |
| ConstIterator | Find (const KeyType &key, size_t hashCode) const |
| bool | Contains (const KeyType &key) const |
| std::pair< Iterator, Iterator > | EqualRange (const KeyType &key) |
| std::pair< ConstIterator, ConstIterator > | EqualRange (const KeyType &key) const |
| ElementHandle | Extract (const KeyType &key) |
| ElementHandle | Extract (const KeyType &key, size_t hashCode) |
| ElementHandle | Extract (ConstIterator pos) |
| integer | erase (const KeyType &key) |
| integer | Erase (const KeyType &key, size_t hashCode) |
| bool | EraseUnique (const KeyType &key) |
| bool | EraseUnique (const KeyType &key, size_t hashCode) |
| Iterator | erase (ConstIterator pos) |
| ALIB_ALLOW_NOTHING_RETURNED Iterator | erase (ConstIterator start, ConstIterator end) |
| ALIB_POP_ALLOWANCE LocalIterator | erase (ConstLocalIterator pos) |
| LocalIterator | erase (ConstLocalIterator start, ConstLocalIterator end) |
| Iterator | begin () |
| Iterator | end () |
| ConstIterator | begin () const |
| ConstIterator | end () const |
| ConstIterator | cbegin () const |
| ConstIterator | cend () const |
| LocalIterator | begin (uinteger bucketNumber) |
| LocalIterator | end (uinteger bucketNumber) |
| ConstLocalIterator | begin (uinteger bucketNumber) const |
| ConstLocalIterator | end (uinteger bucketNumber) const |
| ConstLocalIterator | cbegin (uinteger bucketNumber) const |
| ConstLocalIterator | cend (uinteger bucketNumber) const |
|
| static size_t | getHashCode (Element *elem) |
| static constexpr bool | IsCachingHashes () |
| float | baseLoadFactor |
| | The load factor that is set when the table is rehashed automatically.
|
| uinteger | bucketCount |
| | The number of buckets managed by this tree.
|
| FwdList * | buckets |
| | The list of buckets.
|
| float | maxLoadFactor |
| integer | size |
| | The number of elements stored.
|
| integer | sizeLimitToRehash |
| | Calculated once with rehash. Product of maxLoadFactor and bucketCount.
|
| template<typename TIf = TAllocator> |
| | HashTableBase (float pBaseLoadFactor, float pMaxLoadFactor) |
| | HashTableBase (TAllocator &pAllocator, float pBaseLoadFactor, float pMaxLoadFactor) |
| template<typename TSharedRecycler = SharedRecyclerType, typename TIf = TAllocator> |
| | HashTableBase (TSharedRecycler &pSharedRecycler, float pBaseLoadFactor=1.0, float pMaxLoadFactor=2.0) |
| | ~HashTableBase () |
| Element * | allocElement (const size_t hashCode) |
| bool | areEqual (Element *elem, const TKey &key, size_t keyHashCode) const |
| bool | areEqual (Element *lhs, Element *rhs) const |
| void | clear () |
| | Destructs and removes all entries from this hash table.
|
| Element * | findElement (uinteger bucketIdx, const TKey &key, size_t keyHashCode) const |
| Node * | findElementBefore (uinteger bucketIdx, size_t keyHashCode, const TKey &key) const |
| std::pair< TIterator< T >, TIterator< T > > | findRange (const TKey &key) |
| size_t | increaseSize (integer increase, const size_t hashCode=0) |
| std::pair< TIterator< T >, bool > | insertIfNotExists (const TKey &key, size_t hashCode) |
| uinteger | insertInBucket (Element *element, const size_t hashCode) |
| std::pair< TIterator< T >, bool > | insertOrGet (const TKey &key, size_t hashCode) |
| void | rehash (uinteger newMinBucketCount) |
| void | setMaxLoadFactor (float pMaxLoadFactor) |
