From 3c72a02284dad4ddd9df1ff6910ed1a0a4550a30 Mon Sep 17 00:00:00 2001 From: Stoycho Kyosev Date: Sun, 22 Dec 2024 13:19:05 -0500 Subject: Add seminar 10 and 11 --- Seminar10/src/hashmap/separate-chaining.hpp | 153 ++++++++++++++++++++++++++++ 1 file changed, 153 insertions(+) create mode 100644 Seminar10/src/hashmap/separate-chaining.hpp (limited to 'Seminar10/src/hashmap/separate-chaining.hpp') diff --git a/Seminar10/src/hashmap/separate-chaining.hpp b/Seminar10/src/hashmap/separate-chaining.hpp new file mode 100644 index 0000000..5a3eb8a --- /dev/null +++ b/Seminar10/src/hashmap/separate-chaining.hpp @@ -0,0 +1,153 @@ +#pragma once +#include +#include +#include +#include + +template > +class separate_chaining_hashmap +{ + private: + using pair_type = std::pair; + using pair_iterator_type = typename std::list::iterator; + using bucket_type = std::list; + + // Keeps all the data inserten in the hashmap; + std::list _data; + std::vector _hash_map; + Hash _hash; + double _load_factor; + + size_t get_hash_index(const Key& key) const + { + return _hash(key) % _hash_map.size(); + } + + public: + separate_chaining_hashmap() + : separate_chaining_hashmap(10, 0.75) + {} + + separate_chaining_hashmap(size_t initial_capacity, double load_factor) + : _hash_map(initial_capacity) + , _load_factor(load_factor) + {} + + void insert(const Key& key, const Value& value); + + const Value& find(const Key& key) const; + Value& modify(const Key& key); + + void erase(const Key& key); + + // Return the number of elements in the hashmap. + size_t size() const + { + return _data.size(); + } + + // Returns the load factor. + double load_factor() const + { + return _load_factor; + } + + // Return the number of buckets. + size_t bucket_count() const + { + return _hash_map.size(); + } + + bool empty() const + { + return size() == 0; + } + + void resize(size_t count); +}; + +template +void separate_chaining_hashmap::insert(const Key& key, const Value& value) +{ + size_t current_index = get_hash_index(key); + bucket_type& current_bucket = _hash_map[current_index]; + + auto equal_key_iterator = std::find_if(current_bucket.begin(), current_bucket.end(), + [&key](const pair_iterator_type& element) -> bool { return element->first == key; }); + + if(equal_key_iterator != current_bucket.end()) + { + (*equal_key_iterator)->second = value; + return; + } + + _data.push_back(std::make_pair(key, value)); + current_bucket.push_back(--_data.end()); + + if(size() >= load_factor() * bucket_count()) + { + resize(2 * bucket_count()); + } +} + +template +const Value& separate_chaining_hashmap::find(const Key& key) const +{ + size_t current_index = get_hash_index(key); + bucket_type& current_bucket = _hash_map[current_index]; + + auto equal_key_iterator = std::find_if(current_bucket.begin(), current_bucket.end(), + [&key](const pair_iterator_type& element) -> bool { return element->first == key; }); + + if(equal_key_iterator != current_bucket.end()) + { + return (*equal_key_iterator)->second; + } + + throw std::runtime_error("Element not found."); +} + +template +Value& separate_chaining_hashmap::modify(const Key& key) +{ + size_t current_index = get_hash_index(key); + bucket_type& current_bucket = _hash_map[current_index]; + + auto equal_key_iterator = std::find_if(current_bucket.begin(), current_bucket.end(), + [&key](const pair_iterator_type& element) -> bool { return element->first == key; }); + + if(equal_key_iterator != current_bucket.end()) + { + return (*equal_key_iterator)->second; + } + + throw std::runtime_error("Element not found."); +} + +template +void separate_chaining_hashmap::erase(const Key& key) +{ + size_t current_index = get_hash_index(key); + bucket_type& current_bucket = _hash_map[current_index]; + + auto equal_key_iterator = std::find_if(current_bucket.begin(), current_bucket.end(), + [&key](const pair_iterator_type& element) -> bool { return element->first == key; }); + + if(equal_key_iterator != current_bucket.end()) + { + _data.erase(*equal_key_iterator); + current_bucket.erase(equal_key_iterator); + } +} + +template +void separate_chaining_hashmap::resize(size_t count) +{ + _hash_map.clear(); + _hash_map.resize(count); + + for(auto it = _data.begin(); it != _data.end(); ++it) + { + _hash_map[get_hash_index(it->first)].push_back(it); + } +} -- cgit v1.3.1-26-gb76a