Merge pull request #1 from ckrinitsin/hashtable

Hashtable

2 files changed, 116 insertions, 3 deletions

diff --git a/src/server/hashtable.h b/src/server/hashtable.h
new file mode 100644
index 0000000..0989a79
--- /dev/null
+++ b/src/server/hashtable.h
@@ -0,0 +1,92 @@
+#pragma once
+
+#include <algorithm>
+#include <iostream>
+#include <list>
+#include <optional>
+#include <vector>
+
+template <typename K, typename V>
+class HashTable {
+public:
+    HashTable(size_t size)
+        : size { size }
+        , table(size)
+    {
+    }
+
+    bool insert(K key, V value)
+    {
+        std::list<std::pair<K, V>>& list = get_bucket(key);
+
+        if (bucket_contains_key(list, key)) {
+            return false;
+        }
+
+        list.push_back(std::pair(key, value));
+
+        return true;
+    }
+
+    std::optional<V> get(K key)
+    {
+        std::list<std::pair<K, V>>& list = get_bucket(key);
+
+        auto iter = bucket_find_key(list, key);
+        if (iter != list.end()) {
+            return std::optional<V>((*iter).second);
+        }
+
+        return std::optional<V>();
+    }
+
+    bool remove(K key)
+    {
+        std::list<std::pair<K, V>>& list = get_bucket(key);
+
+        auto iter = bucket_find_key(list, key);
+        if (iter != list.end()) {
+            list.erase(iter);
+            return true;
+        }
+
+        return false;
+    }
+
+    void print()
+    {
+        size_t index { 0 };
+        for (auto bucket : table) {
+            std::cout << "Bucket " << index++ << ": [";
+            for (auto pair : bucket) {
+                std::cout << "(" << pair.first << ", " << pair.second << ")";
+            }
+            std::cout << "]" << "\n";
+        }
+    }
+
+private:
+    size_t size;
+
+    std::vector<std::list<std::pair<K, V>>> table;
+
+    std::hash<K> hash_function;
+
+    auto bucket_find_key(std::list<std::pair<K, V>>& list, K key)
+    {
+        return std::find_if(list.begin(), list.end(), [&key](const std::pair<K, V>& pair) {
+            return pair.first == key;
+        });
+    }
+
+    bool bucket_contains_key(std::list<std::pair<K, V>>& list, K key)
+    {
+        return list.begin() != list.end() && bucket_find_key(list, key) != list.end();
+    }
+
+    std::list<std::pair<K, V>>& get_bucket(K key)
+    {
+        size_t index = hash_function(key) % size;
+        return table.at(index);
+    }
+};
diff --git a/src/server/main.cpp b/src/server/main.cpp
index e04a1cf..b2f8bed 100644
--- a/src/server/main.cpp
+++ b/src/server/main.cpp
@@ -1,5 +1,4 @@
 #include <cstdint>
-#include <cstdio>
 #include <stdexcept>
 #include <string>
 
@@ -8,7 +7,7 @@
 int main(int argc, char* argv[])
 {
     if (argc != 2) {
-        std::printf("One argument required");
+        std::cout << "One argument required" << '\n';
         return 1;
     }
 
@@ -16,10 +15,32 @@ int main(int argc, char* argv[])
     try {
         size = std::stoi(std::string(argv[1]));
     } catch (const std::invalid_argument& e) {
-        std::printf("Invalid argument");
+        std::cout << "Invalid argument" << '\n';
         return 1;
     }
+  
+    HashTable<int, std::string> hash_table { size };
 
+    std::cout << "Add various kv-pairs" << '\n';
+    hash_table.insert(1, "1");
+    hash_table.insert(2, "2");
+    hash_table.insert(3, "3");
+    hash_table.insert(4, "4");
+    hash_table.insert(5, "5");
+    hash_table.insert(6, "6");
+    hash_table.insert(7, "7");
+
+    hash_table.print();
+
+    std::cout << '\n';
+
+    std::cout << "Value for key 8: " << hash_table.get(8).value_or("Key not found!") << '\n';
+    std::cout << "Value for key 4: " << hash_table.get(4).value_or("Key not found!") << '\n';
+
+    std::cout << '\n';
+    std::cout << "Remove pair with key 5" << '\n';
+    hash_table.remove(5);
+    hash_table.print();
 
     return 0;
 }