[ mod mod [ mod mod [ mod mod = since [ is vacantinsert the key in [ the hash table now becomes - - - searching value using quadratic probing while searching value using the quadratic probing techniquethe 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 the desired key value matches with the key value at that locationthen the element is present in the hash table and the search is said to be successful in this casethe search time is given as ( howeverif the value 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 take - comparisonsand the running time of the search algorithm may be (nthe 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 quadratic probing resolves the primary clustering problem that exists in the linear probing technique quadratic probing provides good memory caching because it preserves some locality of reference but linear probing does this task better and gives better cache performance one of the major drawbacks of quadratic probing is that sequence of successive probes may only explore fraction of the tableand this fraction may be quite small if this happensthen we will not be able to find an empty location in the table despite the fact that the table is by no means full in example try to insert the key and you will encounter this problem although quadratic probing is free from primary clusteringit is still liable to what is known as secondary clustering it means that if there is collision between two keysthen the same probe sequence will be followed for both with quadratic probingthe probability for multiple collisions increases as the table becomes full this situation is usually encountered when the hash table is more than full quadratic probing is widely applied in the berkeley fast file system to allocate free blocks double hashing to start withdouble hashing uses one hash value and then repeatedly steps forward an interval until an empty location is reached the interval is decided using secondindependent hash function