Website Summary Files Commits Branches @commit @diff @stats
path: root / Seminar10 / src / hashmap / separate-chaining.hpp
diff options
context:
space:
mode:
Commit3c72a02284dad4ddd9df1ff6910ed1a0a4550a30 (patch)
Author
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-22 13:19:05 -0500
Committer
 Stoycho Kyosev <stoycho.kk@gmail.com>
2024-12-22 13:19:05 -0500
Filese5921b4ff115ae1a1cd570559ea539ecae5a0962 /Seminar10/src/hashmap/separate-chaining.hpp
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.tar
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.tar.gz
Data-structures-and-algorithms-3c72a02284dad4ddd9df1ff6910ed1a0a4550a30.zip
Parentd8fb59b4d45197c9b3a2b100a3d94b1c2e92b2ef (diff)
Add seminar 10 and 11
1 files changed, 153 insertions, 0 deletions
-rw-r--r--Seminar10/src/hashmap/separate-chaining.hpp153
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);
+ }
+}