[#BloombergLP-bslstl-HashTable-09]
= xref:BloombergLP.adoc[BloombergLP]::xref:BloombergLP/bslstl.adoc[bslstl]::xref:BloombergLP/bslstl/HashTable-06.adoc[HashTable]<xref:BloombergLP/bslstl/UnorderedMapKeyConfiguration-0f.adoc[UnorderedMapKeyConfiguration<basic_string<char> const, pair<basic_string<char> const, Json>>], xref:BloombergLP/bdlb/TransparentHash.adoc[TransparentHash], xref:BloombergLP/bdlb/TransparentEqualTo.adoc[TransparentEqualTo], xref:bsl/allocator-0df.adoc[allocator<pair<basic_string<char> const, Json>>]>
:relfileprefix: ../../
:mrdocs:

This class template implements a value‐semantic container type holding an unordered sequence of (possibly duplicate) elements, that can be rapidly accessed using their key, with the constraint on the container that elements whose keys compare equal according to the specified `COMPARATOR` will be stored in a stable, contiguous sequence within the container. The value type and key type of the elements maintained by a `HashTable` are determined by aliases provided through the (template parameter) type `KEY_CONFIG`. Elements in a `HashTable` are stored in "nodes" that are allocated using an allocator of the specified `ALLOCATOR` type (rebound to the node type), and elements are constructed directly in the node using the allocator as described in the C++11 standard under the allocator‐aware container requirements in ([container.requirements.general], C++11 23.2.1). The (template parameter) types `HASHER` and `COMPARATOR` shall be `copy‐constructible` function‐objects. `HASHER` shall support a function call operator compatible with the following statements: ` HASHER hash; KEY_CONFIG::KeyType key; std::size_t result = hash(key); ` where the definition of the called function meets the requirements of a hash function, as specified in {`bslstl_hash`}. `COMPARATOR` shall support the a function call operator compatible with the following statements: ` COMPARATOR compare; KEY_CONFIG::KeyType key1, key2; bool result = compare(key1, key2); ` where the definition of the called function defines an equivalence relationship on keys that is both reflexive and transitive. The `HASHER` and `COMPARATOR` attributes of this class are further constrained, such for any two objects whose keys compare equal by the comparator, shall produce the same value from the hasher.

== Synopsis

Declared in `<bslstl_hashtable.h>`

[source,cpp,subs="verbatim,replacements,macros,-callouts"]
----
template<>
class xref:BloombergLP/bslstl/HashTable-06.adoc[HashTable]<xref:BloombergLP/bslstl/UnorderedMapKeyConfiguration-0f.adoc[UnorderedMapKeyConfiguration<basic_string<char> const, pair<basic_string<char> const, Json>>], xref:BloombergLP/bdlb/TransparentHash.adoc[TransparentHash], xref:BloombergLP/bdlb/TransparentEqualTo.adoc[TransparentEqualTo], xref:bsl/allocator-0df.adoc[allocator<pair<basic_string<char> const, Json>>]>;
----

== Description

This class: * supports a complete set of _value‐semantic_ operations

* except for `bdex` serialization * is _exception‐neutral_ (agnostic except for the `at` method) * is _alias‐safe_ * is `const` _thread‐safe_ For terminology see {`bsldoc_glossary`}.

== Type Aliases

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bslstl/HashTable-09/AllocatorTraits.adoc[`AllocatorTraits`] 
| This `typedef` is an alias to `bsl::allocator_traits<AllocatorType>`.
| xref:BloombergLP/bslstl/HashTable-09/AllocatorType.adoc[`AllocatorType`] 
| This `typedef` is an alias to the (template parameter) `ALLOCATOR`.
| xref:BloombergLP/bslstl/HashTable-09/KeyType.adoc[`KeyType`] 
| This `typedef` is an alias to `KEY_CONFIG::KeyType`.
| xref:BloombergLP/bslstl/HashTable-09/NodeType.adoc[`NodeType`] 
| Node type stored in the hash table.
| xref:BloombergLP/bslstl/HashTable-09/NonConstKeyType.adoc[`NonConstKeyType`] 
| This `typedef` is an alias to the non‐`const` form of `KeyType`.
| xref:BloombergLP/bslstl/HashTable-09/SizeType.adoc[`SizeType`] 
| This `typedef` is an alias to `AllocatorTraits::size_type`.
| xref:BloombergLP/bslstl/HashTable-09/ValueType.adoc[`ValueType`] 
| Alias to the `ValueType` defined in the (template parameter) `KEY_CONFIG`.
|===


== Member Functions

[cols="1,4"]
|===
| Name| Description
| xref:BloombergLP/bslstl/HashTable-09/2constructor-0c.adoc[`HashTable`]         [.small]#[constructor]#
| Constructors
| xref:BloombergLP/bslstl/HashTable-09/2destructor.adoc[`~HashTable`] [.small]#[destructor]#
| Destroy this object.
| xref:BloombergLP/bslstl/HashTable-09/operator_assign-04.adoc[`operator=`] 
| Assignment operators
| xref:BloombergLP/bslstl/HashTable-09/allocator.adoc[`allocator`] 
| Return a copy of the allocator used to construct this hash table. Note that this is not the allocator used to allocate elements for this hash table, which is instead a copy of that allocator rebound to allocate the nodes used by the internal data structure of this hash table.
| xref:BloombergLP/bslstl/HashTable-09/bucketAtIndex.adoc[`bucketAtIndex`] 
| Return a reference offering non‐modifiable access to the `HashTableBucket` at the specified `index` position in the array of buckets of this table. The behavior is undefined unless 'index < numBuckets()'.
| xref:BloombergLP/bslstl/HashTable-09/bucketIndexForKey-05.adoc[`bucketIndexForKey`] 
| `bucketIndexForKey` overloads
| xref:BloombergLP/bslstl/HashTable-09/comparator.adoc[`comparator`] 
| Return a reference providing non‐modifiable access to the key‐equality comparison functor used by this hash table.
| xref:BloombergLP/bslstl/HashTable-09/countElementsInBucket.adoc[`countElementsInBucket`] 
| Return the number elements contained in the bucket at the specified `index`. Note that this operation has linear run‐time complexity with respect to the number of elements in the indexed bucket.
| xref:BloombergLP/bslstl/HashTable-09/elementListRoot.adoc[`elementListRoot`] 
| Return the address of the first element in this hash table, or a null pointer value if this hash table is empty.
| xref:BloombergLP/bslstl/HashTable-09/emplace.adoc[`emplace`] 
| Insert into this hash‐table a newly‐created `ValueType` object, constructed by forwarding the specified (variable number of) `arguments` to the corresponding constructor of `ValueType`, and return the address of the newly inserted node. If a key equivalent to that of the newly‐created object already exists in this hash‐table, then insert the newly‐created object immediately before the first such element. Additional buckets are allocated, as needed, to preserve the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's `SizeType`, a `std::length_error` exception is thrown. This method requires that the `ValueType` defined in the (template parameter) type `KEY_CONFIG` be `emplace‐constructible` into this hash‐table from `arguments` (see {Requirements on `KEY_CONFIG`});
| xref:BloombergLP/bslstl/HashTable-09/emplaceIfMissing.adoc[`emplaceIfMissing`] 
| Insert into this hash‐table a newly‐created `ValueType` object, constructed by forwarding the specified (variable number of) `arguments` to the corresponding constructor of `ValueType`, if a key equivalent to that of the newly‐created object does not already exist in this hash‐table. Return the address of the (possibly newly created and inserted) element in this hash table whose key is equivalent to that of an object created from `arguments`. Load `true` into the specified `isInsertedFlag` if a new value was inserted, and `false` if an equivalent key was already present. If this hash‐table contains more than one element with an equivalent key, return the first such element (from the contiguous sequence of elements having a matching key). Additional buckets are allocated, as needed, to preserve the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's `SizeType`, a `std::length_error` exception is thrown. This method requires that the `ValueType` defined in the (template parameter) type `KEY_CONFIG` be `emplace‐constructible` into this hash‐table from `arguments` (see {Requirements on `KEY_CONFIG`});
| xref:BloombergLP/bslstl/HashTable-09/emplaceWithHint.adoc[`emplaceWithHint`] 
| Insert into this hash‐table a newly‐created `ValueType` object, constructed by forwarding the specified (variable number of) `arguments` to the corresponding constructor of `ValueType` (immediately preceding the specified `hint` if `hint` is not null and the key of the node pointed to by `hint` is equivalent to that of the newly‐created object), and return the address of the newly inserted node. If `hint` is null or the key of the node pointed to by `hint` is not equivalent to that of the newly created object, and a key equivalent to that of the newly‐created object already exists in this hash‐table, then insert the newly‐created object immediately before the first such element. Additional buckets will be allocated, as needed, to preserve the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash table's `SizeType`, a `std::length_error` exception is thrown. This method requires that `ValueType` defined in the (template parameter) type `KEY_CONFIG` be `emplace‐constructible` into this hash‐table from `arguments` (see {Requirements on `KEY_CONFIG`}). The behavior is undefined unless `hint` is either null or points to a node in this hash table.
| xref:BloombergLP/bslstl/HashTable-09/find-03.adoc[`find`] 
| `find` overloads
| xref:BloombergLP/bslstl/HashTable-09/findEndOfRange.adoc[`findEndOfRange`] 
| Return the address of the first node after any nodes holding a value having the same key as the specified `first` node (according to this hash‐table's `comparator`), and a null pointer value if all nodes following `first` hold values with the same key as `first`. The behavior is undefined unless `first` is a link in this hash‐table. Note that this hash‐table ensures all elements having the same key form a contiguous sequence.
| xref:BloombergLP/bslstl/HashTable-09/findRange-03.adoc[`findRange`] 
| `findRange` overloads
| xref:BloombergLP/bslstl/HashTable-09/hasSameValue.adoc[`hasSameValue`] 
| Return `true` if the specified `other` has the same value as this object, and `false` otherwise. Two `HashTable` objects have the same value if they have the same number of elements, and for every subset of elements in this object having keys that compare equal (according to that hash table's `comparator`), a corresponding subset of elements exists in the `other` object, having the same number of elements, where, for some permutation of the subset in this object, every element in that subset compares equal (using `operator==`) to the corresponding element in the `other` subset. The behavior is undefined unless both the `hasher` and `comparator` of this object and the `other` return the same value for every valid input. Note that this method requires that the `ValueType` of the parameterized `KEY_CONFIG` be "equality‐comparable" (see {Requirements on `KEY_CONFIG`}).
| xref:BloombergLP/bslstl/HashTable-09/hasher.adoc[`hasher`] 
| Return a reference providing non‐modifiable access to the hash functor used by this hash‐table.
| xref:BloombergLP/bslstl/HashTable-09/insert-04.adoc[`insert`] 
| `insert` overloads
| xref:BloombergLP/bslstl/HashTable-09/insertIfMissing-09.adoc[`insertIfMissing`] 
| `insertIfMissing` overloads
| xref:BloombergLP/bslstl/HashTable-09/insertIfMissingTransparent.adoc[`insertIfMissingTransparent`] 
| Insert into this hash‐table a `ValueType` object created from the specified `value` if a key equivalent to that of such an object does not already exist in this hash‐table. Return the address of the (possibly newly inserted) element in this hash‐table whose key is equivalent to that of the object created from `value`. Load `true` into the specified `isInsertedFlag` if a new value was inserted, and `false` if an equivalent key was already present. If this hash‐table contains more than one element with an equivalent key, return the first such element (from the contiguous sequence of elements having a matching key). Additional buckets are allocated, as needed, to preserve the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash‐table's `SizeType`, a `std::length_error` exception is thrown. This method requires that the `ValueType` defined in the (template parameter) type `KEY_CONFIG` be `move‐insertable` into this hash‐table (see {Requirements on `KEY_CONFIG`}) and the (template parameter) type `SOURCE_TYPE` be implicitly convertible to `ValueType`.
| xref:BloombergLP/bslstl/HashTable-09/insertOrAssign.adoc[`insertOrAssign`] 
| If a key equivalent to the specified `key` already exists in this hash‐table, assign the specified `obj` to the value associated with that key, load `false` into the specified `isInsertedFlag` and return a pointer to the existing entry. Otherwise, insert into this hash‐table a newly‐created `value_type` object, constructed from `key` and `obj`, load `true` into `isInsertedFlag`, and return a pointer to the newly‐created entry. Use the optionally specified `hint` as a starting place for the search for the existing key.
| xref:BloombergLP/bslstl/HashTable-09/insertOrAssignTransparent.adoc[`insertOrAssignTransparent`] 
| If a key equivalent to the specified `key` already exists in this hash‐table, assign the specified `obj` to the value associated with that key, load `false` into the specified `isInsertedFlag` and return a pointer to the existing entry. Otherwise, insert into this hash‐table a newly‐created `value_type` object, constructed from `key` and `obj`, load `true` into `isInsertedFlag`, and return a pointer to the newly‐created entry. Use the optionally specified `hint` as a starting place for the search for the existing key.
| xref:BloombergLP/bslstl/HashTable-09/loadFactor.adoc[`loadFactor`] 
| Return the current load factor for this table. The load factor is the statistical mean number of elements per bucket.
| xref:BloombergLP/bslstl/HashTable-09/maxLoadFactor.adoc[`maxLoadFactor`] 
| Return the maximum load factor permitted by this hash table object, where the load factor is the statistical mean number of elements per bucket. Note that this hash table will enforce the maximum load factor by rehashing into a larger array of buckets on any any insertion operation where a successful insertion would exceed the maximum load factor. The maximum load factor may actually be less than the current load factor if the maximum load factor has been reset, but no insert operations have yet occurred.
| xref:BloombergLP/bslstl/HashTable-09/maxNumBuckets.adoc[`maxNumBuckets`] 
| Return a theoretical upper bound on the largest number of buckets that this hash‐table could possibly have. Note that there is no guarantee that the hash‐table can successfully maintain that number of buckets, or even close to that number of buckets without running out of resources.
| xref:BloombergLP/bslstl/HashTable-09/maxSize.adoc[`maxSize`] 
| Return a theoretical upper bound on the largest number of elements that this hash‐table could possibly hold. Note that there is no guarantee that the hash‐table can successfully grow to the returned size, or even close to that size without running out of resources.
| xref:BloombergLP/bslstl/HashTable-09/numBuckets.adoc[`numBuckets`] 
| Return the number of buckets contained in this hash table.
| xref:BloombergLP/bslstl/HashTable-09/rehashForNumBuckets.adoc[`rehashForNumBuckets`] 
| Re‐organize this hash‐table to have at least the specified `newNumBuckets`, preserving the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash table's `SizeType`, a `std::length_error` exception is thrown. This operation provides the strong exception guarantee (see {`bsldoc_glossary`}) unless the `hasher` throws, in which case this operation provides the basic exception guarantee, leaving the hash‐table in a valid, but otherwise unspecified (and potentially empty), state. Note that more buckets than requested may be allocated in order to preserve the bucket allocation strategy of the hash table (but never fewer).
| xref:BloombergLP/bslstl/HashTable-09/rehashThreshold.adoc[`rehashThreshold`] 
| Return the number of elements this hash table can hold without requiring a rehash operation in order to respect the `maxLoadFactor`.
| xref:BloombergLP/bslstl/HashTable-09/remove.adoc[`remove`] 
| Remove the specified `node` from this hash‐table, and return the address of the node immediately after `node` in this hash‐table (prior to its removal), or a null pointer value if `node` is the last node in the table. This method invalidates only iterators and references to the removed node and previously saved values of the `end()` iterator, and preserves the relative order of the nodes not removed. The behavior is undefined unless `node` refers to a node in this hash‐table.
| xref:BloombergLP/bslstl/HashTable-09/removeAll.adoc[`removeAll`] 
| Remove all the elements from this hash‐table. Note that this hash‐table is empty after this call, but allocated memory may be retained for future use. The destructor of each (non‐trivial) element that is remove shall be run.
| xref:BloombergLP/bslstl/HashTable-09/reserveForNumElements.adoc[`reserveForNumElements`] 
| Re‐organize this hash‐table to have a sufficient number of buckets to accommodate at least the specified `numElements` without exceeding the `maxLoadFactor`, and ensure that there are sufficient nodes pre‐allocated in this object's node pool. If this function tries to allocate a number of buckets larger than can be represented by this hash table's `SizeType`, a `std::length_error` exception is thrown. This operation provides the strong exception guarantee (see {`bsldoc_glossary`}) unless the `hasher` throws, in which case this operation provides the basic exception guarantee, leaving the hash‐table in a valid, but otherwise unspecified (and potentially empty), state.
| xref:BloombergLP/bslstl/HashTable-09/setMaxLoadFactor.adoc[`setMaxLoadFactor`] 
| Set the maximum load factor permitted by this hash table to the specified `newMaxLoadFactor`, where load factor is the statistical mean number of elements per bucket. If 'newMaxLoadFactor < loadFactor', allocate at least enough buckets to re‐establish the invariant `loadFactor <= maxLoadFactor`. If this function tries to allocate a number of buckets larger than can be represented by this hash table's `SizeType`, a `std::length_error` exception is thrown. The behavior is undefined unless `0 < maxLoadFactor`.
| xref:BloombergLP/bslstl/HashTable-09/size.adoc[`size`] 
| Return the number of elements in this hash table.
| xref:BloombergLP/bslstl/HashTable-09/swap.adoc[`swap`] 
| Exchange the value of this object, its `comparator` functor, its `hasher` functor, and its `maxLoadFactor` with those of the specified `other` object. Additionally, if `bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap` is `true`, then exchange the allocator of this object with that of the `other` object, and do not modify either allocator otherwise. This method provides the no‐throw exception‐safety guarantee unless any of the `comparator` or `hasher` functors throw when swapped, leaving both objects in a safely destructible, but otherwise unusable, state. The operation guarantees `O[1]` complexity. The behavior is undefined unless either this object has an allocator that compares equal to the allocator of `other`, or the trait `bslstl::AllocatorTraits<ALLOCATOR>::propagate_on_container_swap` is `true`.
| xref:BloombergLP/bslstl/HashTable-09/tryEmplace-0d3.adoc[`tryEmplace`] 
| `tryEmplace` overloads
|===



[.small]#Created with https://www.mrdocs.com[MrDocs]#