[C++] Bitset vs. Array vs. Bucketing Solution, ~100% Time (63ms), ~92% Space (39.9MB)
I wanted to improve a bit from my previous idea, so I wanted to try first of all just a more brute-force approach, using a pre-sized bitset to store all the pos
I wanted to improve a bit from [my previous idea](https://leetcode.com/problems/design-hashset/solutions/768723/c-elegant-solution-explained-90-time-90-space/), so I wanted to try first of all just a more brute-force approach, using a pre-sized bitset to store all the possible inputs as present or not; and while it worked as quickly as I thought and more, the space consumption was not even so bad.\n\nThe code:\n\n```cpp\nclass MyHashSet {\npublic:\n    bitset<1000001> store = {};\n    MyHashSet() {}\n    void add(int key) {\n        store[key] = true;\n    }\n    void remove(int key) {\n        store[key] = false;\n    }\n    bool contains(int key) {\n        return store[key];\n    }\n};\n```\n\nWhat I did not expect, was for a `bool` array to go significantly faster than that (I guess the bitset wrapper still makes things more expensive),  while of course consuming almost double memory overall:\n\n```cpp\nclass MyHashSet {\npublic:\n    bool store[1000001] = {};\n    MyHashSet() {}\n    void add(int key) {\n        store[key] = true;\n    }\n    void remove(int key) {\n        store[key] = false;\n    }\n    bool contains(int key) {\n        return store[key];\n    }\n};\n```\n\nBut I knew I could do even better taking some ideas from my previous attempt and perfecting them.\n\nFor my more sophisticated approach, I decided to go back to the bucketing approach, having a `bucketAmount` of `137` and a `bucketSize` of `100`, which worked surprisingly well, despite the amount of operations we might be expecting.\n\nIn our class, I declared an array of `int` pointers `store` of size `bucketsAmount` and `storePos`, to store the pointers I. will use to write on each store - both containers initialised to have all their initial values set to `NULL`/`0`.\n\nWith no need for a constructor, in the `add` method I:\n* check if we already have that `key` present (`contains[key]`), in which case we can just `return`;\n* if not, we will:\n\t* declare `pos` as the value of `key` modulo `bucketsAmount`, to find out which bucket we want to use;\n\t* assign `store[pos]` to `currBucket`;\n* check if `currStore == NULL` (ie: this bucket is empty) and, if so, make it point to a new bucket of `bucketSize` items;\n* write `key` as the last element of the current bucket (`currBucket[storePos[pos]]`);\n* increase `storePos[pos]` by `1`, to make it ready to write the next element in.\n\nIn the `remove` method, we will:\n* declare `pos` as the value of `key` modulo `bucketsAmount`, to find out which bucket we want to use;\n* exit if `currBucket` is empty (`NULL`);\n* loop through the elements in `currBucket` with `i` going from `0` to the last index (`storePos[pos] - 1`) included and:\n\t* if we find that the currently pointed item `(currBucket[i]`) equals `key`, we wil:\n\t* write the value of the last element in `currBucket[i]`;\n\t* pop the last value out of the bucket reducing `storePos[pos]` by `1`;\n\t* if by now `storePos[pos] == 0` (ie: we just popped the last element from the bucket) we will also:\n\t\t* `delete` `store[pos]`;\n\t\t* reset `store[pos]` to be `NULL`.\n\nFinally in the `contains` method, we will:\n* declare `pos` as the value of `key` modulo `bucketsAmount`, to find out which bucket we want to use;\n* exit if `currBucket` is empty (`NULL`);\n* loop through the elements in `currBucket` with `i` going from `0` to the past index (`storePos[pos]`) included and `return` `true` if we find a match (`currBucket[i] == key`);\n* `return` false` if we reach the end of the loop.\n\nThe code:\n\n```cpp\nconstexpr unsigned int bucketsAmount = 137, bucketSize = 100;\n\nclass MyHashSet {\npublic:\n    int *store[bucketsAmount] = {}, storePos[bucketsAmount] = {};\n    MyHashSet() {}\n    void add(int key) {\n        // avoiding double insertions\n        if (contains(key)) return;\n        // support variables\n        int pos = key % bucketsAmount, *currBucket = store[pos];\n        // initialising buckets if it is the first element\n        if (!currBucket) currBucket = store[pos] = new int[bucketSize];\n        // adding key to the matching store and advancing pos\n        currBucket[storePos[pos]++] = key;\n    }\n    void remove(int key) {\n        // support variables\n        int pos = key % bucketsAmount, *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return;\n        for (int i = 0, last = storePos[pos] - 1; i <= last; i++) {\n            // finding the target value\n            if (currBucket[i] == key) {\n                // writing the last value of the bucket in place of key\n                currBucket[i] = currBucket[last];\n                // popping the last element from the bucket \n                storePos[pos]--;\n                // extra: deallocating memory if the bucket is now empty\n                if (!storePos[pos]) {\n                    delete [] store[pos];\n                    store[pos] = NULL;\n                }\n            }\n        }\n    }\n    bool contains(int key) {\n        // support variables\n        int pos = key % bucketsAmount, *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return false;\n        for (int i = 0, lmt = storePos[pos]; i < lmt; i++) if (currBucket[i] == key) return true;\n        return false;\n    }\n};\n```\n\nYou might have noticed that we still loop through the buckets, which would seem not too efficient (while in reality we hardly get more than a handful keys in the same bucket); to obviate to this, I tried to get the best of both worlds, dealing with buckets made of boolean arrays.\n\nIt works, I conjured up a solution that passes all the tests despite being a bit flaky; if you want to have a solider one, just pick `bucketsAmount` and `bucketSize` to be two primes whose product goes above the limit of `1000000` to avoid possible collisions; the latter should be also be picked to be smaller, if you want to micro-optimise and do a more efficient `fill` operation whenever it is needed.\n\nThe code:\n\n```cpp\nconstexpr unsigned int bucketsAmount = 1337, bucketSize = 137;\n\nclass MyHashSet {\npublic:\n    bool *store[bucketsAmount] = {};\n    MyHashSet() {}\n    void add(int key) {\n        // avoiding double insertions\n        if (contains(key)) return;\n        // support variables\n        int pos = key % bucketsAmount, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // initialising buckets if it is the first element\n        if (!currBucket) {\n            currBucket = store[pos] = new bool[bucketSize];\n            fill(currBucket, currBucket + bucketSize, false);\n        }\n        // adding key to the matching store and advancing pos\n        currBucket[bucketPos] = true;\n    }\n    void remove(int key) {\n        // support variables\n        int pos = key % bucketsAmount, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return;\n        currBucket[bucketPos] = false;\n    }\n    bool contains(int key) {\n        // support variables\n        int pos = key % bucketsAmount, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return false;\n        return currBucket[bucketPos];\n    }\n};\n```\n\nDid I say the two numbers have to be primes, right above? Well, I was wrong: being coprime is just enough.\n\nAnd, if so, we can turn one of them (the most frequently used) into a power of `2` to conveniently get the modulo with a super cheap bitwise `&`; even better performance \uD83C\uDF89 :\n\n```cpp\nconstexpr unsigned int bucketsAmount = 1024, bucketSize = 137, bucketBits = bucketsAmount - 1;\n\nclass MyHashSet {\npublic:\n    bool *store[bucketsAmount] = {};\n    MyHashSet() {}\n    void add(int key) {\n        // avoiding double insertions\n        if (contains(key)) return;\n        // support variables\n        int pos = key & bucketBits, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // initialising buckets if it is the first element\n        if (!currBucket) {\n            currBucket = store[pos] = new bool[bucketSize];\n            fill(currBucket, currBucket + bucketSize, false);\n        }\n        // adding key to the matching store and advancing pos\n        currBucket[bucketPos] = true;\n    }\n    void remove(int key) {\n        // support variables\n        int pos = key & bucketBits, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return;\n        currBucket[bucketPos] = false;\n    }\n    bool contains(int key) {\n        // support variables\n        int pos = key & bucketBits, bucketPos = key % bucketSize;\n        bool *currBucket = store[pos];\n        // leaving if no element is in the bucket\n        if (!currBucket) return false;\n        return currBucket[bucketPos];\n    }\n};\n```\n\nFinally, a review of [my previous solution](https://leetcode.com/problems/design-hashset/solutions/768723/c-elegant-solution-explained-90-time-90-space/) using a mere array with a pointer instead of vectors and erasing by just swapping the last value of an array where the one to be removed should be:\n\n```cpp\nconstexpr int bucketSize = 1024;\n\nstruct Bucket {\n    int bucket[bucketSize], w = 0;\n    void add(int val) {\n        if (!contains(val)) bucket[w++] = val;\n    }\n    bool contains(int val) {\n        return w > 0 && find(bucket, bucket + w, val) != bucket + w;\n    }\n    void remove(int val) {\n        for (int i = 0; i < w; i++) {\n            if (bucket[i] == val) {\n                // overwriting val with the last value and popping it out\n                bucket[i] = bucket[--w];\n                break;\n            }\n        }\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```
['Array', 'C', 'Hash Function', 'C++']