data structures using - - - step key ( ( mod mod ( mod = now [ is occupiedso we cannot store the key in [ thereforetry again for the next location thus probei this time key ( ( mod mod ( mod = [ is also occupiedso we cannot store the key in this location the procedure will be repeated until the hash function generates the address of location which is vacant and can be used to store the value in it searching value using linear probing the procedure for searching value in hash table is same as for storing value in hash table while searching for value in hash tablethe array index is re-computed and the key of the element stored at that location is compared with the value that has to be searched if match is foundthen the search operation is successful the search time in this case is given as ( if the key does not matchthen the search function begins sequential search of the array that continues untilthe value is foundor the search function encounters vacant location in the arrayindicating that the value is not presentor the search function terminates because it reaches the end of the table and the value is not present in the worst casethe search operation may have to make - comparisonsand the running time of the search algorithm may take (ntime the worst case will be encountered when after scanning all the - elementsthe value is either present at the last location or not present in the table thuswe see that with the increase in the number of collisionsthe distance between the array index computed by the hash function and the actual location of the element increasesthereby increasing the search time pros and cons linear probing finds an empty location by doing linear search in the array beginning from position (kalthough the algorithm provides good memory caching through good locality of referencethe drawback of this algorithm is that it results in clusteringand thus there is higher risk of more collisions where one collision has already taken place the performance of linear probing is sensitive to the distribution of input values as the hash table fillsclusters of consecutive cells are formed and the time required for search increases with the size of the cluster in addition to thiswhen new value has to be inserted into the table at position which is already occupiedthat value is inserted at the end of the clusterwhich again increases the length of the cluster generallyan insertion is made between two clusters that are separated by one vacant location but with linear probingthere are more chances that subsequent insertions will also end up in one of the clustersthereby potentially increasing the cluster length by an amount much greater than one more the number of collisionshigher the