Design HashMap

To be specific, your design should include these functions:

• put(key, value) : Insert a (key, value) pair into the HashMap. If the value already exists in the HashMap, update the value.

• get(key): Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.

• remove(key) : Remove the mapping for the value key if this map contains the mapping for the key.

Solution : (Using Adjacency list):

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

    /** value will always be non-negative. */
    void put(int key, int value)
    {

        int idx = key % 10000;
        int k = 0;
        for (auto itr = v[idx].begin(); itr != v[idx].end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                k = 1;
                p.second = value;
                *itr = p;
                break;
            }
        }

        if (k == 0)
        {
            v[idx].push_back(make_pair(key, value));
        }
    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key)
    {

        int idx = key % 10000;

        for (auto itr = v[idx].begin(); itr != v[idx].end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                return p.second;
            }
        }

        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key)
    {

        int idx = key % 10000;

        for (auto itr = v[idx].begin(); itr != v[idx].end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                v[idx].erase(itr);
                break;
            }
        }
    }
};

Solution II: (Using 2D Vectors )

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

    /** value will always be non-negative. */
    void put(int key, int value)
    {

        int idx = key % 10000;
        vector<pair<int, int>> l;
        l = v[idx];
        int k = 0;
        for (auto itr = l.begin(); itr != l.end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                k = 1;
                p.second = value;
                *itr = p;
                break;
            }
        }
        
        if(k == 0){
             l.push_back(make_pair(key, value));
        }
        
       v[idx] = l;

    }

    /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
    int get(int key)
    {

        int idx = key % 10000;
        vector<pair<int, int>> l;
        l = v[idx];

        for (auto itr = l.begin(); itr != l.end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                return p.second;
            }
        }

        return -1;
    }

    /** Removes the mapping of the specified value key if this map contains a mapping for the key */
    void remove(int key)
    {

        int idx = key % 10000;
        vector<pair<int, int>> l;
        l = v[idx];

        for (auto itr = l.begin(); itr != l.end(); itr++)
        {
            pair<int, int> p = *itr;
            if (p.first == key)
            {
                l.erase(itr);
                break;
            }
        }

        v[idx] = l;
    }
};