2

Say I have a hash table with 59 elements (each element value is an integer). Index 15 is blank and the rest of the table is full of data. Depending on the number I want to insert, the quadratic probing formula never hits element 15!

Assume I want to insert the number 199 (which should hash to 22 using the hashFunc() function I'm using below.:

public int hashFunc(int key)
{
    return key % arraySize; //199 % 59 = 22
}

public void insert(DataItem item)
{
    int key = item.getKey();      // extract the key (199)
    int hashVal = hashFunc(key);  // hash the key (22)
    int i = 1;

    //The while loop just checks that the array index isn't null and isn't equal to -1 which I defined to be a deleted element

    while(hashArray[hashVal] != null && hashArray[hashVal].getKey() != -1)
    {
        hashVal = hashFunc(key) + (i * i); //This never hits element 15!!!
        i++;
        hashVal %= arraySize;      // wraparound when hashVal is beyond 59
    }

    hashArray[hashVal] = item;    // insert item
}
templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
kevmalek
  • 1,373
  • 2
  • 12
  • 13

1 Answers1

4

This is expected in a quadratic probing hash table. Using some modular arithmetic, you can show that only the first p / 2 probe locations in the probe sequence are guaranteed to be unique, meaning that it's possible that each element's probe sequence will not visit half of the locations in the table.

To fix this, you should probably update your code so that you rehash any time p / 2 or more of the table locations are in-use. Alternatively, you can use the technique suggested on the Wikipedia article of alternating the sign of your probe offset (+1, -4, +9, -16, +25, etc.), which should ensure that you can hit every possible location.

Hope this helps!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065