This method does not use a container per slot in the hash table. Instead, it defines alternative slots in case of a collision. Again, both the key and the value are stored in the hash table.
To use this method, a probe function f is defined. The value of f(k,i) is the i-th alternative hash value for a key k. In all cases, f(k,0) = h(k).
The simplest implementation defines f(k,i) = (h(k) + i) mod n. In this notation n is the capacity of the hash table. This means that all key values that collide will lump (cluster) together (using consecutive slots) in the hash table. This is considered a weak method. However, because f is easy to implement, it is often utilized.
A slightly more complex implementation defines f(k,i) = (h(k) + 0 + 1 + …i) mod n. The closed form is f(k,i) = (h(k) + (i(i + 1))∕2) mod n. This method helps to scatter a chain of collision so that two chains of collisions do not “pile up” to become a bigger contiguous region.
There are other alternatives of f. Regardless of the definition of f, the method still uses the same hash table to resolve collisions. This has impact on the lookup, insertion and removal methods.