Quadratic probing Quadratic probing uses a hash function of the form h(k,i)=(h(k)+c1i+c2i2)modm, where h is an auxiliary hash function, c1 and c2 are positive auxiliary constants, and i=0,1,,m1. The initial position probed is T[h(k)]; later positions probed are offset by amounts that depend in a quadratic manner on the probe number i. This method works much better than linear probing, but to make full use of the hash table, the values of c1,c2, and m are constrained. Problem 11-3 shows one way to select these parameters. Also, if two keys have the same initial probe position, then their probe sequences are the same, since h(k1,0)=h(k2,0) implies h(k1,i)=h(k2,i). This property leads to a milder form of clustering, called secondary clustering. As in linear probing, the initial probe determines the entire sequence, and so only m distinct probe sequences are used. 11-3 Quadratic probing Suppose that we are given a key k to search for in a hash table with positions 0,1,,m1, and suppose that we have a hash function h mapping the key space into the set {0,1,,m1}. The search scheme is as follows: 1. Compute the value j=h(k), and set i=0. 2. Probe in position j for the desired key k. If you find it, or if this position is empty, terminate the search. 3. Set i=i+1. If i now equals m, the table is full, so terminate the search. Otherwise, set j=(i+j)modm, and return to step 2 . Assume that m is a power of 2 . a. Show that this scheme is an instance of the general "quadratic probing" scheme by exhibiting the appropriate constants c1 and c2 for equation (11.5). b. Prove that this algorithm examines every table position in the worst case