Linear Probe

Our first collision resolution method is also the simplest. In a linear probe, when data cannot be stored in the home address, we resolve the collision by adding 1 to the current address. For example, let’s add two more elements to the modulo-division method example. The results are shown in figure 10. When we insert key 070919, we find an empty element and insert it with no collision. When we try to insert key 166703, however, we have a collision at location 001. We try to resolve the collision by adding 1 to the address and inserting the new data at location 002. However, this address is also filled. We therefore add another 1 to the address and this time find an empty location, 003, where we can place the new data.
As an alternative to a simple linear probe, we can add 1, subtract 2, add 3, subtract 4, and so forth until we locate an empty element. In either method, the code for the linear probe must ensure that the next collision resolution address lie