[C++] Elegant Solution Explained, ~90% Time, ~90% Space
The core idea of a hashset is to have O(1) (or close to that) operations, sacrificing some extra memory in order to achieve it - to do we can create a signfiica
The core idea of a hashset is to have O(1) (or close to that) operations, sacrificing some extra memory in order to achieve it - to do we can create a signfiicant amount of buckets to store our values and then address each single value to be stored, looked up or deleted in a matching bucket, doing the match part with a hash function.\n\nEach `Bucket` is a structure capable of doing those operations on each value, for a tiny fraction of the cost you would have putting all of them together. You might get probably even better performances for deletion using a sorted linked list or the like inside each `Bucket`, but assuming few collisions, a vector works just fine.\n\nFor simplicity, I decided to just hash the values with the modulus of the number of buckets - a decent approximation for the numbers at hand, but better hashing alternative of course exist; after some experimentation I seemed to have found an ideal number of buckets in the lower 3 digits ranges, but again hard to say with random inputs and your luck might vary significantly.\n\nThe code - have fun tweaking the default value of `keySpace` to see how time and space performances change accordingly:\n\n```cpp\nstruct Bucket {\n    vector<int> bucket = {};\n    void add(int val) {\n        if (!contains(val)) bucket.push_back(val);\n    }\n    bool contains(int val) {\n        return find(begin(bucket), end(bucket), val) != end(bucket);\n    }\n    void remove(int val) {\n        auto pos = find(begin(bucket), end(bucket), val);\n        if (pos != end(bucket)) bucket.erase(pos);\n    }\n};\n\nclass MyHashSet {\npublic:\n    vector<Bucket> buckets;\n    int hashSize;\n    MyHashSet(int keySpace = 137) {\n        hashSize = keySpace;\n        buckets.resize(keySpace);\n    }\n    void add(int key) {\n        buckets[key % hashSize].add(key);\n    }\n    void remove(int key) {\n        buckets[key % hashSize].remove(key);\n    }\n    bool contains(int key) {\n        return buckets[key % hashSize].contains(key);\n    }\n};\n```
['C', 'Hash Function', 'C++']