Explain the functionality of linear and quadratic probing with respect to hashing
technique. 

Ans:
Linear Probing: The simplest way to resolve a collision is to start with the hash
address and do a sequential search through the table for an empty location. The idea
is to place the record in the next available position in the array. This method is called
linear probing. An empty record is indicated by a special value called null. The array
should be considered circular, so that when the last location is reached the search
proceeds to the first record of the array. An unoccupied record location is always
found using this method if atleast one is available; otherwise, the search halts
unsuccessfully after scanning all locations. The major drawback of the linear probe
method is that of clustering.
When the table is initially empty, it is equally likely that a new record will be
inserted in any of the empty position but when the list becomes half full, records
start to appear in long strings of adjacent positions with gaps between the strings.
Therefore the search to find an empty position becomes longer

Quadratic probing: In the above case when the first insertion is made the
probability of new element being inserted in a particular position is 1/n where n is
the size of the array. At the time of second insertion the probability becomes 2/n and
so on for the kth insertion the probability is k/n, which is k times as compared to any
other remaining unoccupied position. Thus to overcome the phenomenon of long
sequence of occupied positions to become even longer we use quadratic rehash, in
this method if there is a collision at hash address h, this method probes the array at
locations h+1, h+4, h+9, ... That is (h(key) +i2 % hash size) for i=1,2,... gives the ith HASH