Added C++ Hash table implementation

mik30s · mik30s · commit 30c8dcc138aa · 2017-02-11T22:47:37.000-06:00
Uses separate chaining to resolve collisions
diff --git a/Hash_Table/C++/mike168m/hashtable.h b/Hash_Table/C++/mike168m/hashtable.h
@@ -0,0 +1,82 @@
+#ifndef _HASH_TABLE
+#define _HASH_TABLE
+
+// A hash table implemented using Horner's rule and separate chaining
+
+#include <vector>
+#include <list>
+#include <string>
+#include <iostream>
+#include <algorithm>
+
+class Hashtable
+{
+private:
+    unsigned int size;
+    std::vector<std::list<std::string>> table;
+
+    // calculate hash using horner's rule for values of type std::string
+    unsigned int calculateHash(const std::string& key) const {
+        unsigned hash = 0;
+
+        for (char ch: key) {
+            hash = 37 * hash + static_cast<unsigned>(ch);
+        }
+
+        return hash % size;
+    }
+
+    // check the linked list for a value
+    // return true if found and false other wise
+    inline bool checkList(std::list<std::string>& linkedList, const std::string& value) const {
+        if (std::find(begin(linkedList), end(linkedList), value) != end(linkedList)) {
+            return true;
+        }
+        return false;
+    }
+
+    // Prints an std::list
+    inline void print(const std::list<std::string>& list, std::ostream& os = std::cout) const {
+        for (auto& val : list) { os << "[" << val << "]->"; }
+    }
+
+public:
+    // Constructor - tableSize is the size of the table
+    // the defualt size is 11
+    explicit Hashtable(int tableSize = 11)
+        :size(tableSize)
+    {
+        table = std::vector<std::list<std::string>>(tableSize);
+    }
+
+    // adds an element to the table
+    void insert(const std::string& value) {
+        auto& chainList = table[calculateHash(value)];
+
+        // check if value exists in linked list
+        if (!checkList(chainList, value)) {
+            chainList.push_back(value);
+        }
+    }
+
+    // Removes an element from the table
+    void remove(const std::string& value) {
+        auto& chainList = table[calculateHash(value)];
+
+        if (std::find(begin(chainList), end(chainList), value) != end(chainList)) {
+            // element found remove it
+            chainList.remove(value);
+            std::cout << "value removed\n";
+        }
+    }
+
+    // Prints the hash table
+    void print(std::ostream& os = std::cout) const {
+        for (auto& val : table) {
+            print(val, os);
+        }
+        os << "\n";
+    }
+};
+
+#endif // _HASH_TABLE
diff --git a/Hash_Table/C++/mike168m/hashtabletest.cpp b/Hash_Table/C++/mike168m/hashtabletest.cpp
@@ -0,0 +1,12 @@
+#include <iostream>
+#include "hashtable.h"
+
+int main() {
+	Hashtable table;
+	table.insert("abc");
+	table.insert("yoga"); 
+	table.insert("abc"); // adding value again not allowed
+
+	table.remove("xyz"); // value not removed -- does not exist in chain
+	table.remove("abc"); // value removed
+}
