Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <forward_list>
- #include <string>
- class HashTable
- {
- public:
- HashTable();
- HashTable(size_t base, size_t startCapacity);
- bool Add(const std::string &value);
- bool Find(const std::string &value);
- bool Delete(const std::string &value);
- private:
- std::vector <std::forward_list<std::string>> hash_table;
- size_t hash_base;
- size_t size;
- size_t hash(const std::string &value);
- void rehash();
- };
- HashTable::HashTable(size_t base, size_t startCapacity) : hash_table(startCapacity), hash_base(base), size(0)
- {}
- void HashTable::rehash()
- {
- auto old_data(std::move(hash_table));
- hash_table.clear();
- hash_table.resize(old_data.size() * 2);
- for (auto& i : old_data)
- for (auto j = i.begin(); j != i.end(); ++j)
- Add(*j);
- }
- size_t HashTable::hash(const std::string& value)
- {
- size_t ans = 1;
- for (size_t i = 0; i < value.size(); i++)
- ans = (static_cast<size_t>(value[i]) + ans) * hash_base;
- return ans;
- }
- bool HashTable::Add(const std::string& value)
- {
- if (Find(value))
- return false;
- size_t key = hash(value) % hash_table.size();
- hash_table[key].push_front(value);
- size++;
- if (size >= 2 * hash_table.size())
- rehash();
- return true;
- }
- bool HashTable::Find(const std::string& value)
- {
- size_t key = hash(value) % hash_table.size();
- for (auto i = hash_table[key].begin(); i != hash_table[key].end(); ++i)
- {
- if (value.compare(*i) == 0)
- return true;
- }
- return false;
- }
- bool HashTable::Delete(const std::string& value)
- {
- if (!Find(value))
- return false;
- size_t key = hash(value) % hash_table.size();
- hash_table[key].remove(value);
- return true;
- }
- void result(bool res)
- {
- if (res)
- std::cout << "OK\n";
- else
- std::cout << "FAIL\n";
- }
- int main()
- {
- size_t N = 8;
- HashTable h(3, N);
- char operation;
- std::string str;
- while (std::cin)
- {
- std::cin >> operation >> str;
- if (operation == '+')
- result(h.Add(str));
- else if (operation == '-')
- result(h.Delete(str));
- else
- result(h.Find(str));
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment