Table Hash with quadratic method

Asked

Viewed 207 times

2

I am implementing a hash table with quadratic scanning method. My question is about the position 0 of the vector used for table implementation. Follow the code below:

public boolean inserir(Pessoa item) {
    int valorHash = hash(item.getCelular());
    int contador = 1;
    int inicialHash = valorHash;

    while(bancoDados[valorHash] != null && !(bancoDados[valorHash].getCelular().equals(-1))) {
        valorHash += (contador*contador);
        contador++;
        valorHash %= tamanhoMax;
    }

    bancoDados[valorHash] = item;

    return true;

}

Through this method the 0 position will never be found for an insertion. I must ignore this position in the vector and work with the rest or is there some way to make my Hash value (valorHash) reach position 0?

NOTE: I use a person’s cell number to generate the valorHash in another method. When a person is removed from my table I replace them with another person, only with an invalid cell number (-1), to indicate that that position is available.

java hash

  • I’m probably missing a bit of theoretical background, but I don’t understand why a hash table would want to store an element in a position other than the hash itself, after all, how is one going to find the data reliably afterwards? I also didn’t understand the phone with -1, why not simply assign null? What’s more, I believe you have no problem leaving the first element of the vector unused, but if you want to make use of it, just move the result by subtracting 1 from the hash when storing and when retrieving from the vector.

1 answer

0

The position 0 of your table will be found for insertion smoothly, whenever the hash value of an object is a multiple of the table size, for example, let’s assume that you have a table of 17 positions, and the initial hash has been 12, but there was a collision, then the next hash will be h=(12+1*1)%17=13, if there is also a collision at position 13, the next hash will be h=(13+2*2)%17=0, note that the rest of the division 17 by 17 is 0, the same would happen if at some point the hash was 34 or 51, which are multiples of 17.

Browser other questions tagged java hash

You are not signed in. Login or sign up in order to post.