[Solved] Implementing with quadratic probing [closed]

by


With this code you are doing linear probing

    index = hash(entry.key);
    while (!is_vacant(index))
        index = next_index(index);

template <class RecordType>
inline std::size_t table<RecordType>::next_index(std::size_t index) const
// Library facilities used: cstdlib
{
    return ((index+1) % CAPACITY);
}

Say your map is nearly full and hash returns 23, then the next slots you are going to test will be 24, 25, 26, 27, etc.

All that is different about quadratic probing is the pattern of slots to test when a slot is full. Again suppose hash returns 23, then the next slot to test will be 23 + 1 = 24, the next will be 23 + 4 = 27, the next will be 23 + 9 = 32, the next will be 23 + 16 = 39. See the pattern? Each time you are testing 23 + n*n. That is quadratic probing. Of course all values should be mod CAPACITY, like you are doing now.

In other words you don’t need to change the hash function, just the while loop inside insert.

4

solved Implementing with quadratic probing [closed]