Quadratic Probing

[TheSquid]

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.)

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;
}

[swoopy]

> } 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:

    } while(true);

Or you could use:

    } while (!array[val].element.empty());