loulett

hash_table_separate_chaining

Mar 22nd, 2015
253
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.28 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <forward_list>
  4. #include <string>
  5.  
  6. class HashTable
  7. {
  8. public:
  9.     HashTable();
  10.     HashTable(size_t base, size_t startCapacity);
  11.     bool Add(const std::string &value);
  12.     bool Find(const std::string &value);
  13.     bool Delete(const std::string &value);
  14. private:
  15.     std::vector <std::forward_list<std::string>> hash_table;
  16.     size_t hash_base;
  17.     size_t size;
  18.     size_t hash(const std::string &value);
  19.     void rehash();
  20. };
  21.  
  22. HashTable::HashTable(size_t base, size_t startCapacity) : hash_table(startCapacity), hash_base(base), size(0)
  23. {}
  24.  
  25. void HashTable::rehash()
  26. {
  27.     auto old_data(std::move(hash_table));
  28.     hash_table.clear();
  29.     hash_table.resize(old_data.size() * 2);
  30.     for (auto& i : old_data)
  31.         for (auto j = i.begin(); j != i.end(); ++j)
  32.             Add(*j);
  33. }
  34.  
  35. size_t HashTable::hash(const std::string& value)
  36. {
  37.     size_t ans = 1;
  38.     for (size_t i = 0; i < value.size(); i++)
  39.         ans = (static_cast<size_t>(value[i]) + ans) * hash_base;
  40.     return ans;
  41. }
  42.  
  43. bool HashTable::Add(const std::string& value)
  44. {
  45.     if (Find(value))
  46.         return false;
  47.     size_t key = hash(value) % hash_table.size();
  48.     hash_table[key].push_front(value);
  49.     size++;
  50.     if (size >= 2 * hash_table.size())
  51.         rehash();
  52.     return true;
  53. }
  54.  
  55. bool HashTable::Find(const std::string& value)
  56. {
  57.     size_t key = hash(value) % hash_table.size();
  58.     for (auto i = hash_table[key].begin(); i != hash_table[key].end(); ++i)
  59.     {
  60.         if (value.compare(*i) == 0)
  61.             return true;
  62.     }
  63.     return false;
  64. }
  65.  
  66. bool HashTable::Delete(const std::string& value)
  67. {
  68.     if (!Find(value))
  69.         return false;
  70.     size_t key = hash(value) % hash_table.size();
  71.     hash_table[key].remove(value);
  72.     return true;
  73. }
  74.  
  75. void result(bool res)
  76. {
  77.     if (res)
  78.         std::cout << "OK\n";
  79.     else
  80.         std::cout << "FAIL\n";
  81. }
  82.  
  83. int main()
  84. {
  85.     size_t N = 8;
  86.     HashTable h(3, N);
  87.     char operation;
  88.     std::string str;
  89.     while (std::cin)
  90.     {
  91.         std::cin >> operation >> str;
  92.         if (operation == '+')
  93.             result(h.Add(str));
  94.         else if (operation == '-')
  95.             result(h.Delete(str));
  96.         else
  97.             result(h.Find(str));
  98.     }
  99.     return 0;
  100. }
Advertisement
Add Comment
Please, Sign In to add comment