implementation of the hash_map; using constant number of buckets and chaining. More...

#include <hash-map.hpp>

Public Member Functions
	hash_map ()
	creates the instance of the hash_map.

	hash_map (size_t hash_map_capacity)
	creates the instance of the hash_map.

	~hash_map ()
	frees the memory allocated for the buckets.

	hash_map (const hash_map &)=delete
	deleted copy constructor.

hash_map &	operator= (const hash_map &)=delete
	deleted assignment operator.

	hash_map (hash_map &&other) noexcept
	constructs the hash_map instance from an existing one.

hash_map &	operator= (hash_map &&other) noexcept
	constructs new hash_map by assigning it an existing one.

template<typename KK , typename VV > requires std::is_constructible_v<K, KK&&> && std::is_constructible_v<V, VV&&>
void	insert (KK &&key, VV &&value)
	inserts new (key, value) pair; or updates value if key already exists.

V *	find (const K &key) noexcept
	looks up element in a hash_map.

const V *	find (const K &key) const noexcept
	looks up element in a hash_map.

bool	erase (const K &key)
	removes the (key, value) pair from the hash_map.

bool	contains (const K &key) const noexcept
	looks up if element exists in a hash_map.

V &	operator[] (const K &key)
	gets the value for the specific key.

const V &	operator[] (const K &key) const
	gets the value for the specific key.

map_entry **	get_buckets () noexcept
	gets the first bucket

size_t	get_size () const noexcept
	gets the size of the hash_map.

size_t	get_capacity () const noexcept
	gets the capacity of the hash_map.

bool	empty () const noexcept
	checks if the hash_map is empty.

void	clear ()
	clears all entries from the hash_map.

Private Types
using	map_entry = hash_map_entry< K, V >

Private Member Functions
size_t	calculate_bucket (const K &key) const noexcept
	calculates the index of the bucket.

void	delete_entries_from_bucket (map_entry *head) noexcept
	frees all entries from a bucket.

void	clear_buckets () noexcept
	frees all entries from each bucket.

double	load_factor () const noexcept
	calculates the current load factor.

void	resize ()
	resizes the hash_map and rehashes all entries.

Private Attributes
map_entry **	buckets
	list containing the linked-list of entries.

size_t	size
	number of entries in the hash_map.

size_t	capacity
	number of buckets.

Hash	hash_function
	hash function for key hashing.

Detailed Description

template<typename K, typename V, typename Hash = std::hash<K>>
class hash_map< K, V, Hash >

implementation of the hash_map; using constant number of buckets and chaining.

Template Parameters

K	- type of the key.
V	- type of the value. Hash - hash function; defaults to std::hash<K>.

Member Typedef Documentation

◆ map_entry

template<typename K , typename V , typename Hash = std::hash<K>>

using hash_map< K, V, Hash >::map_entry = hash_map_entry<K, V>

private

Constructor & Destructor Documentation

◆ hash_map() [1/4]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map< K, V, Hash >::hash_map ( )

inline

creates the instance of the hash_map.

allocates DEFAULT_MAP_CAPACITY buckets. size defaults to 0. capacity set to DEFAULT_MAP_CAPACITY. sets each bucket linked list to nullptr.

◆ hash_map() [2/4]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map< K, V, Hash >::hash_map ( size_t hash_map_capacity )

inline

creates the instance of the hash_map.

Parameters

hash_map_capacity - number of buckets.

Exceptions

std::invalid_argument if hash_map_capacity is 0.

allocates hash_map_capacity buckets. size defaults to 0. sets each bucket linked list to nullptr.

◆ ~hash_map()

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map< K, V, Hash >::~hash_map ( )

inline

frees the memory allocated for the buckets.

◆ hash_map() [3/4]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map< K, V, Hash >::hash_map ( const hash_map< K, V, Hash > & )

delete

deleted copy constructor.

◆ hash_map() [4/4]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map< K, V, Hash >::hash_map ( hash_map< K, V, Hash > && other )

inlinenoexcept

constructs the hash_map instance from an existing one.

Parameters

other - rvalue of the existing hash_map.

moves the ownership of the buckets, size and capacity from other to this.

Member Function Documentation

◆ calculate_bucket()

template<typename K , typename V , typename Hash = std::hash<K>>

size_t hash_map< K, V, Hash >::calculate_bucket ( const K & key ) const

inlineprivatenoexcept

calculates the index of the bucket.

Parameters

key	- const reference to a key.

Returns: index of the bucket.

◆ clear()

template<typename K , typename V , typename Hash = std::hash<K>>

void hash_map< K, V, Hash >::clear ( )

inline

clears all entries from the hash_map.

◆ clear_buckets()

template<typename K , typename V , typename Hash = std::hash<K>>

void hash_map< K, V, Hash >::clear_buckets ( )

inlineprivatenoexcept

frees all entries from each bucket.

◆ contains()

template<typename K , typename V , typename Hash = std::hash<K>>

bool hash_map< K, V, Hash >::contains ( const K & key ) const

inlinenoexcept

looks up if element exists in a hash_map.

Parameters

key	- const reference to a key.

Returns: true if hash_map contains element; false otherwise.

◆ delete_entries_from_bucket()

template<typename K , typename V , typename Hash = std::hash<K>>

void hash_map< K, V, Hash >::delete_entries_from_bucket ( map_entry * head )

inlineprivatenoexcept

frees all entries from a bucket.

Parameters

head	- pointer to the first element of the bucket linked list.

◆ empty()

template<typename K , typename V , typename Hash = std::hash<K>>

bool hash_map< K, V, Hash >::empty ( ) const

inlinenoexcept

checks if the hash_map is empty.

Returns: true if hash_map is empty; false otherwise.

◆ erase()

template<typename K , typename V , typename Hash = std::hash<K>>

bool hash_map< K, V, Hash >::erase ( const K & key )

inline

removes the (key, value) pair from the hash_map.

Parameters

key	- const reference to a key.

Returns: true if element was erased; false otherwise.

◆ find() [1/2]

template<typename K , typename V , typename Hash = std::hash<K>>

const V * hash_map< K, V, Hash >::find ( const K & key ) const

inlinenoexcept

looks up element in a hash_map.

Parameters

key	- const reference to a key.

Returns: const pointer to the value associated with the key; nullptr if not found.

◆ find() [2/2]

template<typename K , typename V , typename Hash = std::hash<K>>

V * hash_map< K, V, Hash >::find ( const K & key )

inlinenoexcept

looks up element in a hash_map.

Parameters

key	- const reference to a key.

Returns: pointer to the value associated with the key; nullptr if not found.

◆ get_buckets()

template<typename K , typename V , typename Hash = std::hash<K>>

map_entry ** hash_map< K, V, Hash >::get_buckets ( )

inlinenoexcept

gets the first bucket

Returns: pointer to the first bucket

◆ get_capacity()

template<typename K , typename V , typename Hash = std::hash<K>>

size_t hash_map< K, V, Hash >::get_capacity ( ) const

inlinenoexcept

gets the capacity of the hash_map.

Returns: number of buckets in the hash_map.

◆ get_size()

template<typename K , typename V , typename Hash = std::hash<K>>

size_t hash_map< K, V, Hash >::get_size ( ) const

inlinenoexcept

gets the size of the hash_map.

Returns: number of entries in the hash_map.

◆ insert()

template<typename K , typename V , typename Hash = std::hash<K>>

template<typename KK , typename VV >
requires std::is_constructible_v<K, KK&&> && std::is_constructible_v<V, VV&&>

void hash_map< K, V, Hash >::insert	(	KK &&	key,
		VV &&	value
	)

inline

inserts new (key, value) pair; or updates value if key already exists.

Template Parameters

KK	- Key forwarding type.
VV	- Value forwarding type.

Parameters

key	- rvalue of the key.
value	- rvalue of the value.

◆ load_factor()

template<typename K , typename V , typename Hash = std::hash<K>>

double hash_map< K, V, Hash >::load_factor ( ) const

inlineprivatenoexcept

calculates the current load factor.

Returns: load factor.

◆ operator=() [1/2]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map & hash_map< K, V, Hash >::operator= ( const hash_map< K, V, Hash > & )

delete

deleted assignment operator.

◆ operator=() [2/2]

template<typename K , typename V , typename Hash = std::hash<K>>

hash_map & hash_map< K, V, Hash >::operator= ( hash_map< K, V, Hash > && other )

inlinenoexcept

constructs new hash_map by assigning it an existing one.

Parameters

other - rvalue of the existing hash_map.

moves the ownership of the buckets, size and capacity from other to this.

◆ operator[]() [1/2]

template<typename K , typename V , typename Hash = std::hash<K>>

V & hash_map< K, V, Hash >::operator[] ( const K & key )

inline

gets the value for the specific key.

Parameters

key	- const reference to a key of the element.

Returns: reference to a value.

Exceptions

std::out_of_range if key doesn't exist.

◆ operator[]() [2/2]

template<typename K , typename V , typename Hash = std::hash<K>>

const V & hash_map< K, V, Hash >::operator[] ( const K & key ) const

inline

gets the value for the specific key.

Parameters

key	- const reference to a key of the element.

Returns: reference to a value.

Exceptions

std::out_of_range if key doesn't exist.

◆ resize()

template<typename K , typename V , typename Hash = std::hash<K>>

void hash_map< K, V, Hash >::resize ( )

inlineprivate

resizes the hash_map and rehashes all entries.

doubles the capacity and redistributes all entries.

Member Data Documentation

◆ buckets

template<typename K , typename V , typename Hash = std::hash<K>>

map_entry** hash_map< K, V, Hash >::buckets

private

list containing the linked-list of entries.

◆ capacity

template<typename K , typename V , typename Hash = std::hash<K>>

size_t hash_map< K, V, Hash >::capacity

private

number of buckets.

◆ hash_function

template<typename K , typename V , typename Hash = std::hash<K>>

Hash hash_map< K, V, Hash >::hash_function

private

hash function for key hashing.

◆ size

template<typename K , typename V , typename Hash = std::hash<K>>

size_t hash_map< K, V, Hash >::size

private

number of entries in the hash_map.

The documentation for this class was generated from the following file:

ikp-team-16/src/common/hash-map/hash-map.hpp

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ map_entry

Constructor & Destructor Documentation

◆ hash_map() [1/4]

◆ hash_map() [2/4]

◆ ~hash_map()

◆ hash_map() [3/4]

◆ hash_map() [4/4]

Member Function Documentation

◆ calculate_bucket()

◆ clear()

◆ clear_buckets()

◆ contains()

◆ delete_entries_from_bucket()

◆ empty()

◆ erase()

◆ find() [1/2]

◆ find() [2/2]

◆ get_buckets()

◆ get_capacity()

◆ get_size()

◆ insert()

◆ load_factor()

◆ operator=() [1/2]

◆ operator=() [2/2]

◆ operator[]() [1/2]

◆ operator[]() [2/2]

◆ resize()

Member Data Documentation

◆ buckets

◆ capacity

◆ hash_function

◆ size