Luna::HashMap

An container that contains key-value pairs with unique keys using open-addressing hashing algorithm.

template <typename _Kty, typename _Ty, typename _Hash, typename _KeyEqual, typename _Alloc>
class Luna::HashMap

Remark

LunaSDK provides two kinds of hashing-based containers: open-addressing containers and closed-addressing containers. The following containers are open-addressing containers, implemented using Robinhood hashing:

1. HashMap

2. HashSet

3. SelfIndexedHashmap The following containers are closed-addressing containers, implemented using buckets and per-bucket linked-lists:

4. UnorderedMap

5. UnorderedSet

6. UnorderedMultiMap

7. UnorderedMultiSet

8. SelfIndexedUnorderedMap

9. SelfIndexedUnorderedMultiMap

Open addressing (also known as closed hashing) algorithms store elements directly in hash table arrays, while closed addressing (also known as open hashing) algorithms allocate dedicated memory for every element, and stores pointers to such elements in hash table arrays. In open-addressing containers, one hash table slot can only store on element, the second element with the same hash value must be relocated to another empty slot; in closed-addressing containers, all elements with the same hash value can be stored in the same hash table slot, usually stored as linked lists. See Open vs Closed Addressing for a detailed comparison of open addressing and closed addressing.

Prefer HashMap and HashSet instead of UnorderedMap and UnorderedSet, since it performs better in memory fragmentation, memory locality and cache performance. Use UnorderedMap and UnorderedSet if you have the following requirements:

1. You want to insert multiple elements with the same key to the map, which is only supported by closed-addressing maps. Use UnorderedMultiMap, SelfIndexedUnorderedMultiMap and UnorderedMultiSet in such case.

2. You element type has very big size, usually larger than 256, causing allocating element memory in data table become unacceptable because it will waste a lot of memory when the load factor is low. Closed-addressing maps only allocate memory for alive elements, making it consuming much less memory than open-addressing maps when the element size is big. Closed-addressing maps also support extracting element nodes from one map and insert them to another maps without the need of allocating memory for elements, making it efficient to transfer elements between maps.

Member functions

• HashMap()

  Constructs an empty map.

• HashMap(const allocator_type &alloc)

  Constructs an empty map with an custom allocator.

• HashMap(const HashMap &rhs)

  Constructs a map by coping elements from another map.

• HashMap(const HashMap &rhs, const allocator_type &alloc)

  Constructs a map with an custom allocator and with elements copied from another map.

• HashMap(HashMap &&rhs)

  Constructs a map by moving elements from another map.

• HashMap(HashMap &&rhs, const allocator_type &alloc)

  Constructs a map with an custom allocator and with elements moved from another map.

• HashMap & operator=(const HashMap &rhs)

  Replaces elements of the map by coping elements from another map.

• HashMap & operator=(HashMap &&rhs)

  Replaces elements of the map by moving elements from another map.

• iterator begin()

  Gets one iterator to the first element of the map.

• const_iterator begin() const

  Gets one constant iterator to the first element of the map.

• const_iterator cbegin() const

  Gets one constant iterator to the first element of the map.

• iterator end()

  Gets one iterator to the one past last element of the map.

• const_iterator end() const

  Gets one constant iterator to the one past last element of the map.

• const_iterator cend() const

  Gets one constant iterator to the one past last element of the map.

• bool empty() const

  Checks whether this map is empty, that is, the size of this map is 0.

• usize size() const

  Gets the size of the map, that is, the number of elements in the map.

• usize capacity() const

  Gets the capacity of the map, that is, the number of elements the hash table can hold before expanding the hash table.

• usize hash_table_size() const

  Gets the hash table size of the map, that is, the number of slots of the hash table array.

• f32 load_factor() const

  Gets the load factor of the map, which can be computed by (f32)size() / (f32)hash_table_size().

• f32 max_load_factor() const

  Gets the maximum load factor allowed for the map.

• void max_load_factor(f32 ml)

  Sets the maximum load factor allowed for the map.

• void clear()

  Removes all elements in the map.

• void shrink_to_fit()

  Reduces the hash table size to a minimum value that satisfy the maximum load factor limitation.

• hasher hash_function() const

  Gets the hash function used by this map.

• key_equal key_eq() const

  Gets the equality comparison function used by this map.

• void rehash(usize new_data_table_size)

  Changes the data table size and rehashes all elements to insert them to the new data table.

• void reserve(usize new_cap)

  Expands the data table size to the specified value.

• iterator find(const key_type &key)

  Finds the specified element in the map.

• const_iterator find(const key_type &key) const

  Finds the specified element in the map.

• usize count(const key_type &key) const

  Gets the number of elements whose key is equal to the specified key.

• bool contains(const key_type &key) const

  Checks whether at least one element with the specified key exists.

• Pair< iterator, bool > insert(const value_type &value)

  Inserts the specified key-value pair to the map.

• Pair< iterator, bool > insert(value_type &&value)

  Inserts the specified key-value pair to the map.

• Pair< iterator, bool > insert_or_assign(const key_type &key, _M &&value)

  Assigns the value to the element with the specified key, or inserts the key-value pair to the map if such element is not found.

• Pair< iterator, bool > insert_or_assign(key_type &&key, _M &&value)

  Assigns the value to the element with the specified key, or inserts the key-value pair to the map if such element is not found.

• Pair< iterator, bool > emplace(_Args &&... args)

  Constructs one element directly in the map using the provided arguments.

• iterator erase(const_iterator pos)

  Removes one element from the map.

• usize erase(const key_type &key)

  Removes elements with the specified key from the map.

• void swap(HashMap &rhs)

  Swaps elements of this map with the specified map.

• allocator_type get_allocator() const

  Gets the allocator used by this map.