diff options
Add seminar 10 and 11
1 files changed, 153 insertions, 0 deletions
| -rw-r--r-- | Seminar10/src/hashmap/separate-chaining.hpp | 153 |
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 <algorithm> +#include <list> +#include <vector> +#include <stdexcept> + +template <class Key, class Value, class Hash = std::hash<Key>> +class separate_chaining_hashmap +{ + private: + using pair_type = std::pair<Key, Value>; + using pair_iterator_type = typename std::list<pair_type>::iterator; + using bucket_type = std::list<pair_iterator_type>; + + // Keeps all the data inserten in the hashmap; + std::list<pair_type> _data; + std::vector<bucket_type> _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 <class Key, class Value, class Hash> +void separate_chaining_hashmap<Key, Value, Hash>::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 <class Key, class Value, class Hash> +const Value& separate_chaining_hashmap<Key, Value, Hash>::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 <class Key, class Value, class Hash> +Value& separate_chaining_hashmap<Key, Value, Hash>::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 <class Key, class Value, class Hash> +void separate_chaining_hashmap<Key, Value, Hash>::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 <class Key, class Value, class Hash> +void separate_chaining_hashmap<Key, Value, Hash>::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); + } +} |
