Design HashSet

To be specific, your design should include these functions:

• add(value): Insert a value into the HashSet.

• contains(value) : Return whether the value exists in the HashSet or not.

• remove(value): Remove a value in the HashSet. If the value does not exist in the HashSet, do nothing.

Solution : (Using adjacency list)

class MyHashSet
{
public:
    /** Initialize your data structure here. */
    vector<int> v[10000];
    MyHashSet()
    {
    }

    void add(int key)
    {

        if (!contains(key))
        {
            int idx = key % 10000;
            v[idx].push_back(key);
        }
    }

    void remove(int key)
    {
        int idx = key % 10000;

        for (auto itr = v[idx].begin(); itr != v[idx].end(); itr++)
        {
            if (*itr == key)
            {
                v[idx].erase(itr);
                break;
            }
        }
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key)
    {
        int idx = key % 10000;

        for (auto itr = v[idx].begin(); itr != v[idx].end(); itr++)
        {
            if (*itr == key)
            {
                return true;
            }
        }
        return false;
    }
};

Solution II : (Using 2d vectors)

class MyHashSet
{
public:
    /** Initialize your data structure here. */
    vector<vector<int>> v{10000};
    MyHashSet()
    {
    }

    void add(int key)
    {

        if (!contains(key))
        {
            int idx = key % 10000;
            vector<int> l = v[idx];
            l.push_back(key);
            v[idx] = l;
        }
    }

    void remove(int key)
    {
        int idx = key % 10000;

        vector<int> l = v[idx];

        int k = 0;

        for (auto itr = l.begin(); itr != l.end(); itr++)
        {
            if (*itr == key)
            {
                l.erase(itr);
                break;
            }
        }
        v[idx] = l;
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key)
    {
        int idx = key % 10000;

        vector<int> l = v[idx];
        for (auto itr = l.begin(); itr != l.end(); itr++)
        {
            if (*itr == key)
            {
                return true;
            }
        }
        return false;
    }
};