Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <fstream>
- #include <memory>
- using namespace std;
- struct Node
- {
- int hash;
- int key;
- int value;
- Node* next;
- Node(int hash, int key, int value)
- {
- next = NULL;
- this->hash = hash;
- this->key = key;
- this->value = value;
- }
- };
- struct HashSet
- {
- unsigned int MOD;
- vector<Node*> table;
- HashSet()
- {
- MOD = 96557;
- table.resize(MOD);
- }
- int hash(int x)
- {
- x = x ^ (x >> 16);
- return x;
- }
- Node* get(int key)
- {
- Node* node = table[hash(key) % MOD];
- while (node != NULL)
- {
- if (node->key == key)
- {
- return node;
- }
- node = node->next;
- }
- return NULL;
- }
- bool exists(int key)
- {
- return (get(key) != NULL);
- }
- void add(int key)
- {
- if (exists(key))
- {
- return;
- }
- int h = hash(key);
- Node* node = new Node(h, key, key);
- node->next = table[h % MOD];
- table[h % MOD] = node;
- }
- void remove(int key)
- {
- int h = hash(key);
- Node* node = table[h % MOD];
- Node* prev_node = NULL;
- while (node != NULL)
- {
- if (node->key == key)
- {
- if (prev_node == NULL)
- {
- table[h % MOD] = node->next;
- }
- else
- {
- prev_node->next = node->next;
- node->next = NULL;
- }
- return;
- }
- prev_node = node;
- node = node->next;
- }
- }
- };
- int main()
- {
- HashSet set;
- while (!cin.eof())
- {
- string op;
- int key;
- cin >> op >> key;
- if (op == "insert")
- {
- set.add(key);
- }
- if (op == "delete")
- {
- set.remove(key);
- }
- if (op == "exists")
- {
- cout << (set.exists(key) ? "true" : "false") << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement