[C++] 3 Approaches
This is textbook problem, I\'d highly recommend brushing up some basics if you have gotten rusty.\n\nFind solutions to this and many other problems on my GitHub
This is textbook problem, I\'d highly recommend brushing up some basics if you have gotten rusty.\n\nFind solutions to [this](https://github.com/Mohammed-Shoaib/Coding-Problems/blob/master/LeetCode/Solutions/LC0705.cpp) and many other problems on my [GitHub repository](https://github.com/Mohammed-Shoaib/Coding-Problems).\n\n### **Approach 1: Basic Implementation**\n\n```cpp\nclass MyHashSet {\nprivate:\n\tint prime;\n\tvector<list<int>> table;\n\n\tint hash(int key) {\n\t\treturn key % prime;\n\t}\n\n\tlist<int>::iterator search(int key) {\n\t\tint h = hash(key);\n\t\treturn find(table[h].begin(), table[h].end(), key);\n\t}\n\npublic:\n\tMyHashSet() : prime(10007), table(prime) {}\n\t\n\tvoid add(int key) {\n\t\tint h = hash(key);\n\t\tif (!contains(key))\n\t\t\ttable[h].push_back(key);\n\t}\n\t\n\tvoid remove(int key) {\n\t\tint h = hash(key);\n\t\tauto it = search(key);\n\t\tif (it != table[h].end())\n\t\t\ttable[h].erase(it);\n\t}\n\t\n\tbool contains(int key) {\n\t\tint h = hash(key);\n\t\treturn search(key) != table[h].end();\n\t}\n};\n```\n\n**Complexity**\n* Time: `O(n)`, average `O(1)`\n* Space: `O(n)`\n\n### **Approach 2: Table-Doubling**\n\n```cpp\nclass MyHashSet {\nprivate:\n\tint m_size, capacity;\n\tdouble load_factor;\n\tvector<list<int>> table;\n\n\tint hash(int key) {\n\t\treturn key % capacity;\n\t}\n\n\tlist<int>::iterator search(int key) {\n\t\tint h = hash(key);\n\t\treturn find(table[h].begin(), table[h].end(), key);\n\t}\n\n\tvoid rehash() {\n\t    m_size = 0;\n\t\tcapacity = max(2, capacity);\n\t\tvector<list<int>> old_table(move(table));\n\t\ttable = vector<list<int>>(capacity);\n\t\t\n\t\tfor (list<int>& chain: old_table)\n\t\t\tfor (int& key: chain)\n\t\t\t\tadd(key);\n\t}\n\npublic:\n\tMyHashSet() : m_size(0), capacity(2), load_factor(0.75), table(capacity) {}\n\t\n\tvoid add(int key) {\n\t\tif (contains(key))\n\t\t\treturn;\n\t\t\n\t\tm_size++;\n\t\tint h = hash(key);\n\t\ttable[h].push_back(key);\n\t\t\n\t\tif (m_size >= load_factor * capacity) {\n\t\t\tcapacity *= 2;\n\t\t\trehash();\n\t\t}\n\t}\n\t\n\tvoid remove(int key) {\n\t\tint h = hash(key);\n\t\tauto it = search(key);\n\t\t\n\t\tif (it == table[h].end())\n\t\t\treturn;\n\t\t\n\t\tm_size--;\n\t\ttable[h].erase(it);\n\t\t\n\t\tif (m_size <= 0.5 * load_factor * capacity) {\n\t\t\tcapacity /= 2;\n\t\t\trehash();\n\t\t}\n\t}\n\t\n\tbool contains(int key) {\n\t\tint h = hash(key);\n\t\treturn search(key) != table[h].end();\n\t}\n};\n```\n\n**Complexity**\n* Time: `O(n)`, amortized `O(1)`\n* Space: `O(n)`\n\n### **Approach 3: Troll Implementation**\n\n```cpp\nclass MyHashSet {\nprivate:\n\tvector<bool> table;\npublic:\n\tMyHashSet() : table(1e6 + 1, false) {}\n\t\n\tvoid add(int key) {\n\t\ttable[key] = true;\n\t}\n\t\n\tvoid remove(int key) {\n\t\ttable[key] = false;\n\t}\n\t\n\tbool contains(int key) {\n\t\treturn table[key];\n\t}\n};\n```\n\n**Complexity**\n* Time: `O(1)`\n* Space: `O(n)`\n\nI hope this helps :)
['C', 'C++']