Thread: 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.

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.