C Language

4. Open addressing is a method for handling collisions in hashing. The three different methods for open addressing are linear probing, quadratic probing, and double hashing. A brief description of the three methods is given below: In linear probing, the function used to calculate the next location during collision is: h(k)= (h(k)+i)modm,i=1,2 In quadratic probing, the function used to calculate the next location during collision is: h(k)= (h(k)+i2)modm,i=1,2 In double hashing scheme, the primary hash function is, h1(k)=kmodN, where N is the table size. The secondary hash function is, h2(k)=R(keymodR) where R is the maximum prime number less than the table size. Double hashing can be done using: (h1(key)+ih2(key)) modN,i=0,1,2. Given a set of keys and the table size, write a program to print the locations at which the keys are stored using the above-mentioned three methods and also print the total number of collisions that occur during mapping for each of the three methods. Input format: - First line of the input contains an integer, the table size. - Second line contains space-separated(single space) integer numbers, the keys to be inserted. Output format: - First line of the output contains space-separated (single space) integers, the locations obtained using linear probing. - Second line contains an integer, the total number of collisions that occurred during linear probing. - Third line of the output contains space-separated (single space) integers, the locations obtained using quadratic probing. - Fourth line contains an integer, the total number of collisions that occurred during quadratic probing. - Fifth line of the output contains space-separated (single space) integers, the locations obtained using double hashing. - Sixth line contains an integer, the total number of collisions that occurred during double hashing