Hashing Collisions - Open Addressing - QuadraticProbing

b) Quadratic Probing We look for i2‘th slot in i’th iteration.

let hash(x) be the slot index computed using hash function.  
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S

    public void put(String key, String val) 

    {                

        int tmp = hash(key);

        int i = tmp, h = 1;

        do

        {

            if (keys[i] == null)

            {

                keys[i] = key;

                vals[i] = val;

                currentSize++;

                return;

            }

            if (keys[i].equals(key)) 

            { 

                vals[i] = val; 

                return; 

            }            

            i = (i + h * h++) % maxSize;            

        } while (i != tmp);       

    }

    /** Function to get value for a given key **/

    public String get(String key) 

    {

        int i = hash(key), h = 1;

        while (keys[i] != null)

        {

            if (keys[i].equals(key))

                return vals[i];

            i = (i + h * h++) % maxSize;

            System.out.println("i "+ i);

        }            

        return null;

    }

    /** Function to remove key and its value **/

    public void remove(String key) 

    {

        if (!contains(key)) 

            return;

        /** find position key and delete **/

        int i = hash(key), h = 1;

        while (!key.equals(keys[i])) 

            i = (i + h * h++) % maxSize;        

        keys[i] = vals[i] = null;

        /** rehash all keys **/        

        for (i = (i + h * h++) % maxSize; keys[i] != null; i = (i + h * h++) % maxSize)

        {

            String tmp1 = keys[i], tmp2 = vals[i];

            keys[i] = vals[i] = null;

            currentSize--;  

            insert(tmp1, tmp2);            

        }

        currentSize--;        

    }