Algorithms : complete 02-data_structures 03-hash_tables

1 files changed, 15 insertions, 11 deletions

diff --git a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp
index 8af47d2..64a1975 100644
--- a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp
+++ b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp
@@ -15,7 +15,7 @@ struct Query {
 class QueryProcessor {
     int bucket_count;
     // store all strings in one vector
-    vector<string> elems;
+    vector<vector<string>> elems;
     size_t hash_func(const string& s) const {
         static const size_t multiplier = 263;
         static const size_t prime = 1000000007;
@@ -26,7 +26,9 @@ class QueryProcessor {
     }
 
 public:
-    explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {}
+    explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {
+        elems.reserve(bucket_count);
+    }
 
     Query readQuery() const {
         Query query;
@@ -45,20 +47,22 @@ public:
     void processQuery(const Query& query) {
         if (query.type == "check") {
             // use reverse order, because we append strings to the end
-            for (int i = static_cast<int>(elems.size()) - 1; i >= 0; --i)
-                if (hash_func(elems[i]) == query.ind)
-                    std::cout << elems[i] << " ";
+            vector<string> *list = &elems[query.ind];
+            for (int i = static_cast<int>(list->size()) - 1; i >= 0; --i)
+                    std::cout << (*list)[i] << " ";
             std::cout << "\n";
         } else {
-            vector<string>::iterator it = std::find(elems.begin(), elems.end(), query.s);
+            size_t h = hash_func(query.s);
+            vector<string> *list = &elems[h];
+            vector<string>::iterator it = std::find(list->begin(), list->end(), query.s);
             if (query.type == "find")
-                writeSearchResult(it != elems.end());
+                writeSearchResult(it != list->end());
             else if (query.type == "add") {
-                if (it == elems.end())
-                    elems.push_back(query.s);
+                if (it == list->end())
+                    list->push_back(query.s);
             } else if (query.type == "del") {
-                if (it != elems.end())
-                    elems.erase(it);
+                if (it != list->end())
+                    list->erase(it);
             }
         }
     }