Help with hash tables and quadratic probing in Java

Question

I really need help with inserting into a hash table. I'm just not totally getting it right now. Could someone explain quadratic and linear probing in layman's terms?

public void insert(String key)
{
    int homeLocation = 0;
    int location = 0;
    int count = 0;

    if (find(key).getLocation() == -1)  // make sure key is not already in the table
    {
       //****** ADD YOUR CODE HERE FOR QUADRATIC PROBING  ********
    }
}

This is the code I'm working on. I'm not asking anyone to do it, I just really need help with learning the whole concept

Any help would be greatly appreciated.

Answer 1

First of all we are talking about an open addressing (or closed hashing) approach. You need to handle collisions calculating a new hashcode if the previous one is already used by another one, this because every bucket of the hashamap can contain at most 1 element.

So you have an hashing function with two parameters:

• v, the value of the object used to compute hashcode.
• t, it's i*f where i, called stepsize, is what you add everytime to you hash function if a collision occur and f is the number of collisions reached so far.

Starting from this you have two possible functions:

H(v, t) = (H(v) + t) % n
H(v, t) = (H(v) + c*t + d*t*t) % n

First one is a linear function, while second is a quadratic one (here it comes the names of this tecnique).. where you should know what % n is, c and d are chosen constants to have a better hashfunction..

Practically speaking for linear probing:

• you caculate H(x, 0)
• • if cell is free place the element there
• • if cell is occupied calculate H(x, i)
• • • if cell is free place the element in the new address
• • • if cell is occupied then calculate H(x, i+i)
• • • • continue until you find an empty cell

for the quadratic probing what you do is identical, you start from H(x,0), then H(x,i) then H(x,i+i), what differs is the hashing function involved which will give a different weight to the step size.