quadratic probing (collision resolution) problem

This is a discussion on quadratic probing (collision resolution) problem within the C++ Programming forums, part of the General Programming Boards category; I have a question about quadratic probing. I am trying to make a open address hashing table. I have a ...

  1. #1
    Registered User
    Join Date
    Jan 2006
    Posts
    49

    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.

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,553
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. matrixes for collision detection
    By DavidP in forum Game Programming
    Replies: 10
    Last Post: 11-09-2002, 09:31 PM
  2. Problem with Hash Table Linear Probing
    By kirby1024 in forum C Programming
    Replies: 5
    Last Post: 10-23-2002, 06:03 AM
  3. collision detection
    By DavidP in forum Game Programming
    Replies: 2
    Last Post: 05-11-2002, 01:31 PM
  4. Collision with quads?
    By SyntaxBubble in forum Game Programming
    Replies: 6
    Last Post: 01-18-2002, 05:17 PM
  5. problem with output
    By Garfield in forum C Programming
    Replies: 2
    Last Post: 11-18-2001, 07:34 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21