when an element is inserted into a hash table, the hash algorithm will map it to a particular location. If that location is already occupied, a conflict occurs. In order to resolve this we use linear probing where, we find the next free position from the location returned by the algorithm and place the element there.
When the element is searched again the hash algorithm will return the same position as earlier. But the element will not be present there as it was not free when the element was inserted. So we again perform linear probing and start searching in the consecutive elements until we find it. This will take the same number of iterations as the insertion algorithm did.
For eg: consider a hash table of size 4 and the hash algorthm is modulus 4. The hash table contains the following intial contents.
Now assume 8 is inserted. it will be mapped to index 0 which is already occupied so by linear probing the element will be placed in index 2. This will require 2 iterations.
When element is eight is searched now the hash algorithm will again return index 0. But the element will not be present there and hence linear probing will performed. The element will be found at index 2 and obviously this will require 2 iterations.
So the no of iterations required for insertion is equal to the no of iterations required for searching the element.
