quadratic probing (collision resolution) problem

I have a question about quadratic probing. I am trying to make a open address hashing table.

I have a hashing function but I'm having difficulty resolving collisions. My code is this so far...

Code:

---

#define MAX_TABLE_SIZE 31

bool hashTable::insert( string key ){
    if( count == MAX_TABLE_SIZE )//table is full
        return false;

    int x = 1;
    int index = hash( key );
   
    if( (table[index] == NULL)  ){
        table[index] = new object( key );
        return true;
    }

    else{
          while( (table[index] != NULL) ){
                cout << title << " collided at " << index << endl;
                index = ( hash( key ) + (x*x) ) % MAX_TABLE_SIZE;//generates new index
                x++;
          }
          table[index] = new object( key );
          return true;
    } 
}

---

Every now an then when I am using this code, it gets stuck in the while loop particularly when the table is getting close to being full. This happens all the time if I repeatedly try to fill up my hash table with the same key. This doesn't happen at all when using linear probing. Is there something wrong with my collision resolution? Thanks.

> hash( key ) + (x*x)
Well if the hash returns an even number, then this whole expression will always be even.
You've just made half the hash inaccessible.

Adding
while ( x < MAX_TABLE_SIZE && (table[index] != NULL) )
Would at least stop the code from locking up in a fruitless search.
But you need to detect if the search failed.

Quote:

---

Originally Posted by rakan

Every now an then when I am using this code, it gets stuck in the while loop particularly when the table is getting close to being full. This happens all the time if I repeatedly try to fill up my hash table with the same key. This doesn't happen at all when using linear probing. Is there something wrong with my collision resolution? Thanks.

---

You shouldn't be storing multiple entries with the same key anyway. A lookup will only find the first one. The code should first check if the value has already been inserted, and if it has, you do not add it again.

If you intend to store duplicates for some reason such as duplicate detection, then you should use the seperate chaining method.