Quadratic Probing

This is a discussion on Quadratic Probing within the C++ Programming forums, part of the General Programming Boards category; While trying to make a quadratic probing hashtable I decided to test it by adding four words that hash to ...

  1. #1
    Not just a squid...
    Join Date
    Sep 2004
    Posts
    25

    Quadratic Probing

    While trying to make a quadratic probing hashtable I decided to test it by adding four words that hash to the same value so I can see where they are being added. The first word gets added to index 67 and the second gets added to 68 like it should, but the next two words are all added at 68 again instead of 71 and 76. I've fiddled with my code for a while and this makes sense to me, anyone see whats wrong?

    For reference, array is a vector member of HashTable, element is a string, and collision is a bool. (Collision and element have HashTable and vector as friends.)

    Code:
    void HashTable::addWord(const string &key)
    {
        int val = hash(key, array.size()), 
            i = 0;
        
        do {
            if(array[val].element.empty())
                break;
            array[val].collision = true;
            i++;
            val += i * i;
        } while(array[val].collision);
        
        array[val].element = key;
    }

  2. #2
    Registered User
    Join Date
    Oct 2001
    Posts
    2,934
    > } while(array[val].collision);
    This loop will never loop, because you change val right before you check array[val].collision. This should probably be just:
    Code:
        } while(true);
    Or you could use:
    Code:
        } while (!array[val].element.empty());

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. quadratic probing (collision resolution) problem
    By rakan in forum C++ Programming
    Replies: 2
    Last Post: 11-26-2006, 12:30 PM
  2. Quadratic Function
    By abs.emailverify in forum C Programming
    Replies: 5
    Last Post: 11-14-2006, 02:07 PM
  3. Replies: 0
    Last Post: 06-14-2006, 04:45 AM
  4. Quadratic Factoring
    By neandrake in forum C++ Programming
    Replies: 11
    Last Post: 04-15-2002, 05:49 PM
  5. Quadratic Equation Program
    By Ambizzy in forum C Programming
    Replies: 4
    Last Post: 02-19-2002, 09:21 PM

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