Solution.cpp

const int EMPTY = -1;
const int TOMBSTONE = -2;

class MyHashSet {
    int* buckets;
    size_t size = 0;
    size_t capacity;
    
    void resize() {
        int* oldBuckets = buckets;
        size_t oldCapacity = capacity;
        capacity *= 2;
        buckets = new int[capacity];
        std::fill_n(buckets, capacity, EMPTY);
        for (size_t i = 0; i < oldCapacity; ++i) {
            addImpl(oldBuckets[i]);
        }
    }
    
    void addImpl(int key) {
        for (size_t i = key % capacity; i < capacity; ++i) {
            if (buckets[i] == EMPTY || buckets[i] == TOMBSTONE) {
                buckets[i] = key;
                return;
            }
        }
        for (size_t i = 0; i < key % capacity; ++i) {
            if (buckets[i] == EMPTY || buckets[i] == TOMBSTONE) {
                buckets[i] = key;
                return;
            }
        }
    }
public:
    /** Initialize your data structure here. */
    MyHashSet() {
        capacity = 64;
        buckets = new int[capacity];
        std::fill_n(buckets, capacity, EMPTY);
    }
    
    void add(int key) {
        // cout << "add: " << key << endl;
        if (size > capacity * 0.9) {
            resize();
        }
        addImpl(key);
        ++size;
    }
    
    void remove(int key) {
        // cout << "del: " << key << endl;
        for (size_t i = key % capacity; i < capacity; ++i) {
            if (buckets[i] == key) {
                buckets[i] = TOMBSTONE;
            } else if (buckets[i] == EMPTY) {
                return;
            }
        }
        for (size_t i = 0; i < key % capacity; ++i) {
            if (buckets[i] == key) {
                buckets[i] = TOMBSTONE;
            } else if (buckets[i] == EMPTY) {
                return;
            }
        }
    }
    
    /** Returns true if this set contains the specified element */
    bool contains(int key) {
        // cout << "chk: " << key << endl;
        for (size_t i = key % capacity; i < capacity; ++i) {
            if (buckets[i] == key) {
                return true;
            } else if (buckets[i] == EMPTY) {
                return false;
            }
        }
        for (size_t i = 0; i < key % capacity; ++i) {
            if (buckets[i] == key) {
                return true;
            } else if (buckets[i] == EMPTY) {
                return false;
            }
        }
        return false;
    }
};