smatskevich

HashTable

Dec 22nd, 2020
611
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <utility>
  4. #include <vector>
  5.  
  6. const int kHashParam = 17;
  7. const int kModParam = 1000000007;
  8.  
  9. int Hash(const std::string& value) {
  10.   int result = 0;
  11.   for (const char c : value) {
  12.     result = (result * kHashParam + c) % kModParam;
  13.   }
  14.   return result;
  15. }
  16.  
  17. struct Node {
  18.   std::string Value;
  19.   Node* Next;
  20. };
  21.  
  22. class HashTable {
  23.  public:
  24.   HashTable() : table(20, nullptr) {}
  25.   ~HashTable() {/*TODO: clear*/}
  26.  
  27.   bool Has(const std::string& value) const {
  28.     const int hash = Hash(value) % table.size();
  29.     for (Node* p = table[hash]; p != nullptr; p = p->Next) {
  30.       if (p->Value == value) return true;
  31.     }
  32.     return false;
  33.   }
  34.  
  35.   bool Add(const std::string& value) {
  36.     const int hash = Hash(value) % table.size();
  37.     for (Node* p = table[hash]; p != nullptr; p = p->Next) {
  38.       if (p->Value == value) return false;
  39.     }
  40.     table[hash] = new Node{value, table[hash]};
  41.     return true;
  42.   }
  43.  
  44.   bool Remove(const std::string& value) {
  45.     const int hash = Hash(value) % table.size();
  46.     Node* p = table[hash];
  47.     if (p == nullptr) return false;
  48.     if (p->Value == value) {
  49.       table[hash] = p->Next;
  50.       delete p;
  51.       return true;
  52.     }
  53.     for (; p->Next != nullptr; p = p->Next) {
  54.       if (p->Next->Value == value) {
  55.         Node* tmp = p->Next;
  56.         p->Next = p->Next->Next;
  57.         delete tmp;
  58.         return true;
  59.       }
  60.     }
  61.     return false;
  62.   }
  63.  
  64.  private:
  65.   std::vector<Node*> table;
  66. };
  67.  
  68. int main() {
  69.   HashTable t;
  70.  
  71.   char command = 0;
  72.   std::string value;
  73.   while (std::cin >> command >> value) {
  74.     if (command == '?') {
  75.       std::cout << (t.Has(value) ? "OK" : "FAIL") << std::endl;
  76.     } else if (command == '+') {
  77.       std::cout << (t.Add(value) ? "OK" : "FAIL") << std::endl;
  78.     } else if (command == '-') {
  79.       std::cout << (t.Remove(value) ? "OK" : "FAIL") << std::endl;
  80.     }
  81.   }
  82.   return 0;
  83. }
  84.  
  85. #include <unordered_set>
  86.  
  87. int main1() {
  88.   std::unordered_set<std::string> t;
  89.   // В t будет использована std::hash<std::string>, имеющая реализацию в std.
  90.   char command = 0;
  91.   std::string value;
  92.   while (std::cin >> command >> value) {
  93.     if (command == '?') {
  94. //      std::cout << (t.Has(value) ? "OK" : "FAIL") << std::endl;
  95.     } else if (command == '+') {
  96. //      std::cout << (t.Add(value) ? "OK" : "FAIL") << std::endl;
  97.     } else if (command == '-') {
  98. //      std::cout << (t.Remove(value) ? "OK" : "FAIL") << std::endl;
  99.     }
  100.   }
  101.   return 0;
  102. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×